AOVAOE网络动态规划算法.ppt

AOV,AOE网络, 动态规划算法,2010/06/10,2,3,4,5,邻接矩阵：,6,Prim算法：,7,通讯恢复问题，一些同学的思路：,某一条最小生成树的边被摧毁时，其他边不会改变，此时只有vy没有变到达，因此只要找到能够达到vy的边中，权值最小的一条来代替原来的边。 将被摧毁线路置为MAX，做Prim，在结果中找出与原线路同起点及终点的线路，且线路中不含权为MAX的边，则打印线路；否则打印“悲剧”。 用floyd算法，原图生成shortpath结构体后，将vx,vy的shortpath参数改为无穷和不连接，从而在不改变原图的条件下生成最短路径，在打印出vx到vy的最短路径。设全局变量length计算原最小生成树的总路径长度，减去去掉的边，加上生成最短路径的距离值，得到目前通讯线路的代价总和,8,Prim应用 00811124 吴小骥,我的思路：摧毁某条边以后，剩下的边再进行一次prim排序。 排序结果中唯一出现变动的就是我们所要的替代边， 其余边是不会变的（虽然在mst数组中的顺序会变）。 为简化显示结果，把原先prim的中间步骤省去了，不打印出来 为了不直接改掉原来的矩阵，建一个新矩阵 建一个新的存放生成树的数组 再次调用prim函数 倘若无法连通，最后得到的最小生成树中必有MAX， 从这个就可以判断是否能走通了,9,主要内容,拓扑排序 AOV网概念 AOE网与关键路径,10,拓扑排序概念,对一个有向无环图G进行拓扑排序，是指将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若 E(G)，则u在线性序列中出现在v之前。 ABE CFGE ACFGBE CAFBGE,G,F,C,A,B,E,11,拓扑排序思想,（1）从AOV网中选择一个入度为0的顶点将其输出。 （2）在AOV网中删除此顶点及其所有的出边。 反复执行以上两步，直到所有顶点都已经输出为止，此时整个拓扑排序完成；或者直到剩下的顶点的入度都不为0为止，此时说明AOV网中存在回路，拓扑排序无法再进行。,12,拓扑排序算法,拓扑排序前，先调用findInDegree得到所有结点的入度，然后将所有入度为0的顶点压栈。 从栈顶取出一个顶点将其输出，由它的出边表可以得到以该顶点为起点的出边，将这些边终点的入度减1，即删除这些边。 如果某条边终点的入度为0，则将该顶点入栈。 反复进行上述操作，直到栈为空。 如果这时输出的顶点个数小于n，则说明该AOV网中存在回路，否则，拓扑排序正常结束。,13,采用邻接出边表表示： 增加一个indegree维度，存放各顶点的入度。,14,算法复杂度分析,n个顶点，e条边 检查每个顶点的度：O（n+e） 出栈-入栈-删除边： O（n+e）,15,AOV网,顶点活动网络。每一个顶点代表一个活动。顶点之间的有向弧代表活动之间的序关系。,拓扑排序 无有向环 无死锁,16,AOE网,如果在带权的有向图中，用顶点表示事件，用有向边表示活动，边上的权值表示活动的开销，则此带权的有向图称为边活动网 (Activity on edge network) ，简称AOE网。 顶点表示一个事件。 顶点的入边所表示该事件发生所需的的活动。只有所有活动（入边）都完成了，该事件才能发生。 顶点的出边所表示当该事件（顶点）发生后，后续的活动（出边）都可以开展了。,17,AOE网,开工,动工,进材料 3天,打地基 40天,修围墙 16天,拆迁 2年,盖房子 120天,动工：进材料； 打地基；完成。盖房子；可以开始。,18,AOE网,顶点：事件 边： 活动 事件发生：之前的所有活动完成。 活动开始：起点事件必发生。 活动结束：终点事件不一定发生。,AOE网必须是可拓扑排序的。 一般是一个出发点顶点，一个终止顶点。,19,关键路径,AOE网中有些活动可以并行进行，所以完成整个工程的最短时间是从开始顶点到完成顶点的最长路径长度，路径长度为路径上各边的权值之和。把开始顶点到完成顶点的最长路径称为关键路径。,关键路径是：1 - 4 - 3 - 2, 关键路径长度为：2+7+6 = 15，,20,几个相关的概念,ee(j)：事件vj 可能发生的最早时刻。它是从开始顶点v0到vj 的最长路径长度。也代表了从vj出发的所有活动的最早开始时间。 le(i)：在保证不延误整个工期的前提下，事件vi 允许发生的最晚时刻。 e(k)：活动ak = 的最早开始时间。 l(k)：活动ak = 的最晚开始时间。 源点：入度为0的顶点。 汇点：出度为零的顶点。,21,关键活动,关键活动就是e(k) = l(k)的活动。 l(k)e(k)表示完成活动ak的时间余量，是在不延误工期的前提下，活动ak可以延迟的时间。 关键活动是：a2，a4，a5。,22,关键路径算法,(1) 输入e条弧，建立AOE网的存储结构。 (2) 从源点v0出发，令ee(0)=0,求 ee(j) 1 的 最早开始时间e(k) = ee(i) 和 最晚开始时间l(k) = le(j) weight ()， 其中e(k)=l(k)的为关键活动。 求关键路径是在拓扑排序的前提下进行的，不能进行拓扑排序，不能求关键路径。,23,关键路径算法,24,声明四个数组,拓扑排序结果,25,最晚发生时间,26,例子：,27,算法分析：,设AOE网有n个顶点，e条边，在求事件可能的最早发生时间及允许的最迟发生时间，以及活动的最早开始时间和最晚开始时间时，都要对图中所有顶点及每个顶点边表中所有的边结点进行检查，时间花费为O(n+e)，因此，求关键路径算法的时间复杂度为O(n+e)。,28,AOE网研究的问题,完成整个工程至少需要多少时间 哪些活动是影响工程的关键 1956年，美国杜邦公司提出关键路径法，并于1957年首先用于1000万美圆化工厂建设，工期比原计划缩短了4个月。