《动态规划求LCS课件》由会员分享，可在线阅读，更多相关《动态规划求LCS课件（36页珍藏版）》请在金锄头文库上搜索。
1、1,图 AOV,AOE网络,2009/05/26,2,3,4,动态规划求LCS,5,输出LCS结果 00711032 金晨,6,7,8,9,by 00720002周天逸,10,11,背包问题 Knapsack Problem,Given n items of （n个物体） integer weights: w1 w2 wn values: v1 v2 vn a knapsack of integer capacity W find most valuable subset of the items that fit into the knapsack Consider instance def
2、ined by first i items and capacity j (j W). Let Vi,j be optimal value of such instance. Then max Vi-1, j, V i-1, j- wi + vi if j- wi 0 Vi,j = Vi-1,j if j- wi 0 Initial conditions: V0,j = 0 and Vi,0 = 0,12,背包问题 （示例）,Example: Knapsack of capacity W = 5 item weight value 1 2 $12 2 1 $10 3 3 $20 4 2 $15
3、 capacity j 0 1 2 3 4 5 0 w1 = 2, v1= 12 1 w2 = 1, v2= 10 2 w3 = 3, v3= 20 3 w4 = 2, v4= 15 4 ?,0 0 0 0 0 12 0 10 12,22 22 22 0 10 12 22 30 32 0 10 15 25 30 37,Backtracing finds the actual optimal subset, i.e. solution.,max Vi-1, j, V i-1, j- wi + vi,13,14,为了提高这类解的检索效率，分枝界限法在剪枝的技术方面增加了智能的成分。 这种方法对树中
4、的每个结点定义了一对界，分别给出沿着该结点继续搜索可能得到的解的收益上界（用u表示）和收益下界（用l表示）。这两个值给得越精确，剪枝的控制就越有效。,15,思考题（选作 31日前提交）：,如果串中每个字母（token）的权重是不一样的，要求两个串的加权最大公共子串能否实现？ 如果不能，主要难点在哪里？ 如果能，基本算法思路及实现方案如何?算法复杂度是多少？ (可以加入一个 字母-全重 对照表，按占字典厚度大概估算)。,16,主要内容,AOV网与拓扑排序概念 AOE网与关键路径,17,AOV网,顶点活动网络。每一个顶点代表一个活动。顶点之间的有向弧代表活动之间的序关系。,18,AOV网与拓扑排序
5、概念,对一个有向无环图G进行拓扑排序，是指将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若 E(G)，则u在线性序列中出现在v之前。 ABE CFGE ACFGBE CAFBGE,G,F,C,A,B,E,19,拓扑排序思想,（1）从AOV网中选择一个入度为0的顶点将其输出。 （2）在AOV网中删除此顶点及其所有的出边。 反复执行以上两步，直到所有顶点都已经输出为止，此时整个拓扑排序完成；或者直到剩下的顶点的入度都不为0为止，此时说明AOV网中存在回路，拓扑排序无法再进行。 拓扑排序 无有向环 无死锁,20,拓扑排序算法,拓扑排序前，先调用findInDegree得到所有结点的入度
6、，然后将所有入度为0的顶点压栈。 从栈顶取出一个顶点将其输出，由它的出边表可以得到以该顶点为起点的出边，将这些边终点的入度减1，即删除这些边。 如果某条边终点的入度为0，则将该顶点入栈。 反复进行上述操作，直到栈为空。 如果这时输出的顶点个数小于n，则说明该AOV网中存在回路，否则，拓扑排序正常结束。,21,采用邻接出边表表示： 增加一个indegree维度，存放各顶点的入度。,22,算法复杂度分析,n个顶点，e条边 检查每个顶点的度：O（n+e） 出栈-入栈-删除边： O（n+e）,23,AOE网,如果在带权的有向图中，用顶点表示事件，用有向边表示活动，边上的权值表示活动的开销，则此带权的有
7、向图称为边活动网 (Activity on edge network) ，简称AOE网。 顶点表示一个事件。 顶点的入边所表示该事件发生所需的的活动 顶点的出边所表示当该事件发生后，后续的活动都可以开展了。,24,AOE网,开工,动工,进材料 3天,打地基 40天,修围墙 16天,拆迁 2年,盖房子 120天,动工：进材料； 打地基；完成。盖房子；可以开始。,25,AOE网,顶点：事件 边： 活动 事件发生：之前的所有活动完成。 活动开始：起点事件必发生。 活动结束：终点事件不一定发生。,AOE网必须是可拓扑排序的。 一般是一个出发点顶点，一个终止顶点。,26,关键路径,AOE网中有些活动可以
8、并行进行，所以完成整个工程的最短时间是从开始顶点到完成顶点的最长路径长度，路径长度为路径上各边的权值之和。把开始顶点到完成顶点的最长路径称为关键路径。,关键路径是：1 - 4 - 3 - 2, 关键路径长度为：2+7+6 = 15，,27,几个相关的概念,ee(j)：事件vj 可能发生的最早时刻。它是从开始顶点v0到vj 的最长路径长度。也代表了从vj出发的所有活动的最早开始时间。 le(i)：在保证不延误整个工期的前提下，事件vi 允许发生的最晚时刻。 e(k)：活动ak = 的最早开始时间。 l(k)：活动ak = 的最晚开始时间。 源点：入度为0的顶点。 汇点：出度为零的顶点。,28,关
9、键活动,关键活动就是e(k) = l(k)的活动。 l(k)e(k)表示完成活动ak的时间余量，是在不延误工期的前提下，活动ak可以延迟的时间。 关键活动是：a2，a4，a5。,29,关键路径算法,(1)输入e条弧，建立AOE网的存储结构。(2)从源点v0出发，令ee(0)=0,求 ee(j) 1 的 最早开始时间e(k) = ee(i) 和 最晚开始时间l(k) = le(j) weight ()， 其中e(k)=l(k)的为关键活动。求关键路径是在拓扑排序的前提下进行的，不能进行拓扑排序，不能求关键路径。,30,关键路径算法,31,32,33,例子：,34,算法分析：,设AOE网有n个顶点，e条边，在求事件可能的最早发生时间及允许的最迟发生时间，以及活动的最早开始时间和最晚开始时间时，都要对图中所有顶点及每个顶点边表中所有的边结点进行检查，时间花费为O(n+e)，因此，求关键路径算法的时间复杂度为O(n+e)。,35,AOE网研究的问题,完成整个工程至少需要多少时间 哪些活动是影响工程的关键1956年，美国杜邦公司提出关键路径法，并于1957年首先用于1000万美圆化工厂建设，工期比原计划缩短了4个月。杜邦公司在采用关键路径法的一年中，节省了100万美圆。,36,作业：,上机布置。,
