《数据结构与算法分析课件.ppt》由会员分享，可在线阅读，更多相关《数据结构与算法分析课件.ppt（29页珍藏版）》请在三一办公上搜索。
1、数据结构与算法分析,第六章 关键路径（5）,1,谢谢观赏,2019-8-21,6.7 关键路径,如何建立一个工程进度控制模型？如何估算完成整个工程至少需要多少时间(假设网络中没有环)?为缩短完成工程所需的时间, 应当加快哪些活动?人们用AOE网解决这个问题,2,谢谢观赏,2019-8-21,AOE网（Activity On Edge Network）,在带权的有向图中，用结点表示事件：所有入边上进行的活动均已完成的事件用边表示活动：起始结点事件发生后所开展的活动边的上权表示活动的开销（如持续时间）则称此有向图为“边表示活动的网络”,简称AOE网。,3,谢谢观赏,2019-8-21,AOE网的性
2、质,活动开始时间：只有在某个顶点所代表的事件发生后，从该顶点出发的各有向边代表的活动才能开始;事件发生时间：只有在进入某一顶点的各有向边代表的活动已经结束，该顶点所代表的事件才能发生；表示实际工程计划的AOE网应该是无环的，并且存在唯一的入度为0的开始顶点（源点）和唯一的出度为0的结束点（汇点）。,4,谢谢观赏,2019-8-21,AOE网研究的主要问题：,如果用AOE 网表示一项工程，那么仅仅考虑各个子工程之间的优先关系还不够，更多地是关心整个工程完成的最短时间是多少，哪些活动的延迟将影响整个工程进度,而加速这些活动能否提高整个工程的效率,因此AOE网有待研究的问题是:(1) 完成整个工程至
3、少需要多少时间？(2) 哪些活动是影响工程进度的关键活动？,5,谢谢观赏,2019-8-21,路径长度、关键路径、关键活动：,路径长度：是指从源点到汇点路径上所有活动的持续时间之和。关键路径：完成工程的最短时间是从源点到汇点的最大路径长度。因此，把从源点到汇点具有最大长度的路径称为关键路径。一个AOE中，关键路径可能不只一条。关键活动：关键路径上的活动称为关键活动。在关键路径长度的范围内，可以安排并行的活动,6,谢谢观赏,2019-8-21,举例：奥运会竞赛日程,地点：主会场需要考虑的场地：中心、跑道、沙坑需要考虑的项目：短跑、长跑、马拉松、铅球、跳高、跳远。源点：开幕式;终点:闭幕式,7,谢
4、谢观赏,2019-8-21,术语： ve(j),vl(j), e(i), l(i),ve(j):事件vj的最早发生时间。事件用v标识，事件的编号用括号中的数字标识，v的下标区分“最早”和“最晚”。 vl(j):事件vj的最晚发生时间。事件用“发生”描述。e(i):活动ai的最早开始时间。没有v的符号就是表示活动，括号中是活动的编号，e表示最早开始时间，l表示最晚。 l(i):活动ai的最晚开始时间。活动用“开始”,8,谢谢观赏,2019-8-21,Ve(j) ：事件vj的最早发生时间,Ve(j)从源点V1 到顶点Vj 的最长路径长度。,1,3,2,4,a1=8,a2=12,5,6,7,8,a1
5、0=12,a9=6,a8=8,a5=28,a6=8,a7=6,a3=14,a4=10,从源点到顶点Vj的最长路径，可以包括所有以顶点Vj为终点的全部活动所需时间。经过这段路径，事件Vj才有可能发生。Ve(6)是多少？,9,谢谢观赏,2019-8-21,e(i):活动ai 的最早可能开始时间,若活动ai 在边上, 则e(i) 是顶点Vj 最早时间。事件Vj发生，表明以Vj为终点的活动全部结束。所以，以Vj为起点的所有活动ai可以立即开始。,1,3,2,4,a1=8,a2=12,5,6,7,8,a10=12,a9=6,a8=8,a5=28,a6=8,a7=6,a3=14,a4=10,e(i) =
6、Ve(j) .( 1 ),j,ai,10,谢谢观赏,2019-8-21,Vl(k)：事件Vk的最迟发生时间,是在保证汇点Vn在Ve(n)时刻完成的前提下，事件Vk的允许的最迟开始时间。在不推迟工期的情况下，一个事件最迟发生时间Vl(k)应该等于汇点的最早发生时间Ve(n )减去从Vk到Vn的最大路径长度。还有什么含义？以 vk为终点的活动的最迟完成时间。,1,3,2,4,a1=8,a2=12,5,6,7,8,a10=12,a9=6,a8=8,a5=28,a6=8,a7=2,a3=14,a4=10,Ve(n )：58,22,40,24,46,58,Ve(4 )：22Vl(4 )：325826,2
7、6,12,8,20,11,谢谢观赏,2019-8-21,L(i) ：活动ai 的最迟允许开始时间,是指在不会引起工期延误的前提下，活动ai允许的最迟开始时间。因为事件Vk发生表明以Vk为终点的入边所表示的所有活动均已完成，所以事件Vk的最迟发生时间Vl(k)也是所有以Vk为终点的入边所表示的活动ai可以最迟完成时间。显然，为不推迟工期，活动ai的最迟开始时间Ll(i)应该是ai的最迟完成时间Vl(k)减去ai的持续时间，即l(i) = Vl(k) - ACTjk .( 2 ) 其中, ACTjk是活动ai 的持续时间（ 上的权）。,Vk,ai,Vj,12,谢谢观赏,2019-8-21,L(i)
8、 - e(i)表示活动ai 的最早可能开始时间和最迟允许开始时间的时间余量。关键路径上的活动都满足：l(i) = e(i) .( 3 )l(i) = e(i)表示活动是没有时间余量的关键活动。由上述分析知，为找出关键活动，需要求各个活动的e(i)与l(i)，以判别一个活动ai是否满足l(i) = e(i)。Ve(k) 和Vl(k)可由拓扑排序算法得到。e(i)： e(i) Ve(j) l(i)： l(i) = Vl(k) - ACTjk,时间余量l(i) - e(i),j,ai,k,ai,k,j,13,谢谢观赏,2019-8-21,思考：,完成整个工程至少需要多少时间(假设网络中没有环)?为缩
9、短完成工程所需的时间, 应当加快哪些活动?分析：在AOE网络中, 有些活动顺序进行，有些活动并行进行。从源点到各个顶点，以至从源点到汇点的有向路径可能不止一条。这些路径的长度也可能不同。完成不同路径的活动所需的时间虽然不同，但只有各条路径上所有活动都完成了，整个工程才算完成。因此，完成整个工程所需的时间取决于从源点到汇点的最长路径长度，即在这条路径上所有活动的持续时间之和。这条路径长度最长的路径就叫做关键路径(Critical Path)。,14,谢谢观赏,2019-8-21,关键路径与关键活动,复习关键路径概念：完成工程的最短时间是从源点到汇点的最大路径长度。因此，把从源点到汇点具有最大长度
10、的路径称为关键路径要找出关键路径，必须找出关键活动，即不按期完成就会影响整个工程完成的活动。关键活动概念：那些满足l(i) = e(i) 的活动ai关键路径上的所有活动都是关键活动。因此，只要找到了关键活动，就可以找到关键路径.,15,谢谢观赏,2019-8-21,基本思路：,拓扑排序,并求出Ve(k) ， 逆拓扑排序，求Vl(k) 根据公式和权值邻接矩阵ACTNN求e（i），l（i）根据e（i），l（i）求出关键活动根据关键活动求出关键路径,16,谢谢观赏,2019-8-21,数据结构：AOE图,typedef struct nodeint adjvex;int dur;struct nod
11、e *next;edgenode;/边表结点typedef struct vextype vertex;/顶点标识int id;/入度edgenode *link;/指向出边表vexnode;/顶点表结点vexnode dign;/AoE网数据表示,17,谢谢观赏,2019-8-21,数据结构：Ve，Vl，e，l,数组 int vln,ven;int lmaxsize,emaxsize;拓扑：队列： tpordn； int front=-1,rear=-1;,18,谢谢观赏,2019-8-21,初始化,void criticalpath(vexnode dig) int i,j,k,m;int
12、 front=-1,rear=-1;/用队列。顺序队列的首尾指针初值int tpordn,vln,ven;int lmaxsize,emaxsize;edgenode *p;for(i=0;in;i+)初始化，建立入度为0的队列。 vei=0;if(digi.id=0) tpord+rear=i;m=0;/计数拓扑排序的顶点数,19,谢谢观赏,2019-8-21,Step1:求Ve(k),从源点V1出发，令Ve(1) = 0，按拓扑序列次序求出其余各顶点事件的最早发生时间:Ve(k) = max Ve(j)+ACTjk jT 其中T是以顶点Vk为尾的所有边的顶点集合(2kn) 如果网中有回路，
13、不能求出关键路径则算法中止；否则转Step2。,j,k,j2,jn,j1,T,Ve(j),ACTjk,.,.,模型,方法,j,k,jn,while(p)/遍历j的所有出边 k=p-adjvex; digk.id-; if(vej+p-durvek) vek=vej+p-dur; if(digk.id=0) tpord+rear=k; p=p-next;,20,谢谢观赏,2019-8-21,求vek,while(front!=rear) /栈非空循环,拓扑顺序遍历AOE求Vejfront+; j=tpordfront; m+; p=digj.link;while(p)/遍历j的所有出边，修改ve
14、kk=p-adjvex; digk.id-;if(vej+p-durvek) vek=vej+p-dur;if(digk.id=0) tpord+rear=k;p=p-next;if(mn)printf(n the network has a cyclen);,21,谢谢观赏,2019-8-21,正拓扑顺序？,队列变化？最后的front,rear值？,22,谢谢观赏,2019-8-21,求Ve(k),1,3,2,4,a1=8,a2=12,5,6,7,8,a10=12,a9=6,a8=8,a5=28,a6=8,a7=6,a3=14,a4=10,Ve(k),0 1 2 3 4 5 6 7,0,12
15、,8,22,40,28,36,58,3,4,8,7,6,5,2,1,tpord,12,22,58,36,40,28,8,0,46,46,23,谢谢观赏,2019-8-21,Step2(回退阶段)：,从汇点Vn出发，令Vl(n) = Ve(n)，按逆拓扑有序求其余各顶点的最晚发生时间：Vl(j) = min Vl(k)-ACTjk kS 其中S是以顶点Vj为头的所有边的尾顶点的集合(2jn-1)逆序的潜在条件,j,k,kn,k2,k1,ACTjk,S,模型,while(p)/遍历j的所有出边(j,k),改vlj k=p-adjvex; if(vlk-p-durdur; if(digk.id=0)
16、 tpord+rear=k; p=p-next;,24,谢谢观赏,2019-8-21,求Vlk,for(i=0;i=0;i-)/逆拓扑序列取结点j=tpordi;p=digj.link;while(p)/遍历顶点j的所有出边(j,k)，修改vljk=p-adjvex;if(vlk-p-durdur;p=p-next;,25,谢谢观赏,2019-8-21,58,求Vl(k),1,3,2,4,a1=8,a2=12,5,6,7,8,a10=12,a9=6,a8=8,a5=28,a6=8,a7=6,a3=14,a4=10,Vl(k),58,58,58,58,58,58,58,1 2 3 4 5 6 7
17、 8,令“-”=0,0,8,0,7,0,6,0,5,0,4,0,3,0,2,0,1,14,4,28,6,10,4,8,6,6,5,18,7,6,7,12,8,12,3,8,2,58,58,58,58,58,58,58,58,3,4,8,7,6,5,2,1,tpord,46,38,32,12,8,0,46,38,40,8,0,32,12,40,26,谢谢观赏,2019-8-21,Step3：,求每一项活动ai的最早开始时间:e( i ) = Ve( j )最晚开始时间:l( i ) = Vl( k ) - ACTjk若某条边满足e( i ) = l( i )，则它是关键活动。为了简化算法, 可以
18、在求关键路径之前已经对各顶点实现拓扑排序, 并按拓扑有序的顺序对各顶点重新进行了编号。不是任意一个关键活动的加速一定能使整个工程提前。想使整个工程提前，要考虑各个关键路径上所有关键活动。,27,谢谢观赏,2019-8-21,求ei,li,关键活动li-ei,i=0;for(j=0;jadjvex;/ ei+=vej;/边的序号是按操作顺序排的 li=vlk-p-dur; printf(%dt%dt%dt%dt%dt%dt,digj.vertex,digk.vertex,ei,li,li-ei); if(ei=li) printf(关键活动n); p=p-next;,28,谢谢观赏,2019-8-21,求：ei,li,li-ei,1,3,2,4,a1=8,a2=12,5,6,7,8,a10=12,a9=6,a8=8,a5=28,a6=8,a7=6,a3=14,a4=7,Ve(k),1 2 3 4 5 6 7 8,令“-”=0,1,8,2,7,2,6,1,5,2,4,1,3,1,2,0,1,4,7,7,8,0,12,8,22,40,28(38),46,58,29,谢谢观赏,2019-8-21,
