动态规划算法

《动态规划算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、12013/05/28Lesson20动态规划DynamicProgramming2有向图相关算法主要内容AOV网与拓扑排序AOE网与关键路径最小树形图3拓扑排序概念对一个有向无环图G进行拓扑排序，是指将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若∈E(G)，则u在线性序列中出现在v之前。ABECFGEACFGBECAFBGEGFCABE4拓扑排序思想（1）从AOV网中选择一个入度为0的顶点将其输出。（2）在AOV网中删除此顶点及其所有的出边。反复执行以上两步，直到所有顶点都已经输出为止，此时整个拓扑排序完成；或者直到剩下的顶点的入度都不为0为

2、止，此时说明AOV网中存在回路，拓扑排序无法再进行。5拓扑排序算法拓扑排序前，先调用findInDegree得到所有结点的入度，然后将所有入度为0的顶点压栈。从栈顶取出一个顶点将其输出，由它的出边表可以得到以该顶点为起点的出边，将这些边终点的入度减1，即删除这些边。如果某条边终点的入度为0，则将该顶点入栈。反复进行上述操作，直到栈为空。如果这时输出的顶点个数小于n，则说明该AOV网中存在回路，否则，拓扑排序正常结束。66采用邻接出边表表示：增加一个indegree维度，存放各顶点的入度。77算法复杂度分析n个顶点，e条边检查每个顶点的度：O（n+e）出栈-入栈-删除边

3、：O（n+e）88AOV网顶点活动网络。每一个顶点代表一个活动。顶点之间的有向弧代表活动之间的序关系。拓扑排序–无有向环–无死锁9AOE网如果在带权的有向图中，用顶点表示事件，用有向边表示活动，边上的权值表示活动的开销，则此带权的有向图称为边活动网(Activityonedgenetwork)，简称AOE网。顶点表示一个事件。顶点的入边所表示该事件发生所需的的活动。只有所有活动（入边）都完成了，该事件才能发生。顶点的出边所表示当该事件（顶点）发生后，后续的活动（出边）都可以开展了。10AOE网开工动工进材料3天打地基40天修围墙16天拆迁2年盖房子120天动工：进材料；

4、打地基；完成。盖房子；可以开始。11AOE网顶点：事件边：活动事件发生：之前的所有活动完成。活动开始：起点事件必发生。活动结束：终点事件不一定发生。AOE网必须是可拓扑排序的。一般是一个出发点顶点，一个终止顶点。1212关键路径AOE网中有些活动可以并行进行，所以完成整个工程的最短时间是从开始顶点到完成顶点的最长路径长度，路径长度为路径上各边的权值之和。把开始顶点到完成顶点的最长路径称为关键路径。关键路径是：1->4->3->2,关键路径长度为：2+7+6=15，1313几个相关的概念ee(j)：事件vj可能发生的最早时刻。它是从开始顶点v0到vj的最长路径长度。也代表

5、了从vj出发的所有活动的最早开始时间。le(i)：在保证不延误整个工期的前提下，事件vi允许发生的最晚时刻。e(k)：活动ak=的最早开始时间。l(k)：活动ak=的最晚开始时间。源点：入度为0的顶点。汇点：出度为零的顶点。1414关键活动关键活动就是e(k)=l(k)的活动。l(k)－e(k)表示完成活动ak的时间余量，是在不延误工期的前提下，活动ak可以延迟的时间。关键活动是：a2，a4，a5。1515关键路径算法(1)输入e条弧，建立AOE网的存储结构。(2)从源点v0出发，令ee(0)=0,求ee(j)  1<=j<=n-1

6、。(3)从汇点n-1出发，令le(n-1)=ee(n-1),求le(i)  0<=i<=n-2。(4)根据各顶点的ee和le值，求每条弧ak的最早开始时间e(k)=ee(i)和最晚开始时间l(k)=le(j)–weight()，其中e(k)=l(k)的为关键活动。求关键路径是在拓扑排序的前提下进行的，不能进行拓扑排序，不能求关键路径。1616关键路径算法1717声明四个数组拓扑排序结果1818最晚发生时间1919例子：2020算法分析：设AOE网有n个顶点，e条边，在求事件可能的最早发生时间及允许的最迟发生时间，以及活动的最早开始时间和最晚

7、开始时间时，都要对图中所有顶点及每个顶点边表中所有的边结点进行检查，时间花费为O(n+e)，因此，求关键路径算法的时间复杂度为O(n+e)。2121AOE网研究的问题完成整个工程至少需要多少时间哪些活动是影响工程的关键1956年，美国杜邦公司提出关键路径法，并于1957年首先用于1000万美圆化工厂建设，工期比原计划缩短了4个月。杜邦公司在采用关键路径法的一年中，节省了100万美圆。2222动态规划算法dynamicprogramming2323简介起源：运筹学中的规划论，Bellman的最优化原理。多阶段决策问题：问题可以按顺序分解成若