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