数据结构与算法分析.ppt

《数据结构与算法分析.ppt》由会员分享，可在线阅读，更多相关《数据结构与算法分析.ppt（29页珍藏版）》请在课桌文档上搜索。

1、数据结构与算法分析,第六章 关键路径（5）,6.7 关键路径,如何建立一个工程进度控制模型？如何估算完成整个工程至少需要多少时间(假设网络中没有环)?为缩短完成工程所需的时间,应当加快哪些活动?人们用AOE网解决这个问题,AOE网（Activity On Edge Network）,在带权的有向图中，用结点表示事件：所有入边上进行的活动均已完成的事件用边表示活动：起始结点事件发生后所开展的活动边的上权表示活动的开销（如持续时间）则称此有向图为“边表示活动的网络”,简称AOE网。,AOE网的性质,活动开始时间：只有在某个顶点所代表的事件发生后，从该顶点出发的各有向边代表的活动才能开始;事件发生时

2、间：只有在进入某一顶点的各有向边代表的活动已经结束，该顶点所代表的事件才能发生；表示实际工程计划的AOE网应该是无环的，并且存在唯一的入度为0的开始顶点（源点）和唯一的出度为0的结束点（汇点）。,AOE网研究的主要问题：,如果用AOE 网表示一项工程，那么仅仅考虑各个子工程之间的优先关系还不够，更多地是关心整个工程完成的最短时间是多少，哪些活动的延迟将影响整个工程进度,而加速这些活动能否提高整个工程的效率,因此AOE网有待研究的问题是:(1)完成整个工程至少需要多少时间？(2)哪些活动是影响工程进度的关键活动？,路径长度、关键路径、关键活动：,路径长度：是指从源点到汇点路径上所有活动的持续时间

3、之和。关键路径：完成工程的最短时间是从源点到汇点的最大路径长度。因此，把从源点到汇点具有最大长度的路径称为关键路径。一个AOE中，关键路径可能不只一条。关键活动：关键路径上的活动称为关键活动。在关键路径长度的范围内，可以安排并行的活动,举例：奥运会竞赛日程,地点：主会场需要考虑的场地：中心、跑道、沙坑需要考虑的项目：短跑、长跑、马拉松、铅球、跳高、跳远。源点：开幕式;终点:闭幕式,术语：ve(j),vl(j),e(i),l(i),ve(j):事件vj的最早发生时间。事件用v标识，事件的编号用括号中的数字标识，v的下标区分“最早”和“最晚”。vl(j):事件vj的最晚发生时间。事件用“发生”描述

4、。e(i):活动ai的最早开始时间。没有v的符号就是表示活动，括号中是活动的编号，e表示最早开始时间，l表示最晚。l(i):活动ai的最晚开始时间。活动用“开始”,Ve(j)：事件vj的最早发生时间,Ve(j)从源点V1 到顶点Vj 的最长路径长度。,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,从源点到顶点Vj的最长路径，可以包括所有以顶点Vj为终点的全部活动所需时间。经过这段路径，事件Vj才有可能发生。Ve(6)是多少？,e(i):活动ai 的最早可能开始时间,若活动ai 在边上,则e(i)是

5、顶点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)=Ve(j).(1),j,ai,Vl(k)：事件Vk的最迟发生时间,是在保证汇点Vn在Ve(n)时刻完成的前提下，事件Vk的允许的最迟开始时间。在不推迟工期的情况下，一个事件最迟发生时间Vl(k)应该等于汇点的最早发生时间Ve(n)减去从Vk到Vn的最大路径长度。还有什么含义？以 vk为终点的活动的最迟完成时间。,1,3,2,4,a

6、1=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,26,12,8,20,L(i)：活动ai 的最迟允许开始时间,是指在不会引起工期延误的前提下，活动ai允许的最迟开始时间。因为事件Vk发生表明以Vk为终点的入边所表示的所有活动均已完成，所以事件Vk的最迟发生时间Vl(k)也是所有以Vk为终点的入边所表示的活动ai可以最迟完成时间。显然，为不推迟工期，活动ai的最迟开始时间Ll(i)应该是ai的最迟完成时间Vl(k)减去ai的持续时

7、间，即l(i)=Vl(k)-ACTjk.(2)其中,ACTjk是活动ai 的持续时间（上的权）。,Vk,ai,Vj,L(i)-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,思考：,完成整个工

8、程至少需要多少时间(假设网络中没有环)?为缩短完成工程所需的时间,应当加快哪些活动?分析：在AOE网络中,有些活动顺序进行，有些活动并行进行。从源点到各个顶点，以至从源点到汇点的有向路径可能不止一条。这些路径的长度也可能不同。完成不同路径的活动所需的时间虽然不同，但只有各条路径上所有活动都完成了，整个工程才算完成。因此，完成整个工程所需的时间取决于从源点到汇点的最长路径长度，即在这条路径上所有活动的持续时间之和。这条路径长度最长的路径就叫做关键路径(Critical Path)。,关键路径与关键活动,复习关键路径概念：完成工程的最短时间是从源点到汇点的最大路径长度。因此，把从源点到汇点具有最大

9、长度的路径称为关键路径要找出关键路径，必须找出关键活动，即不按期完成就会影响整个工程完成的活动。关键活动概念：那些满足l(i)=e(i)的活动ai关键路径上的所有活动都是关键活动。因此，只要找到了关键活动，就可以找到关键路径.,基本思路：,拓扑排序,并求出Ve(k)，逆拓扑排序，求Vl(k)根据公式和权值邻接矩阵ACTNN求e（i），l（i）根据e（i），l（i）求出关键活动根据关键活动求出关键路径,数据结构：AOE图,typedef struct nodeint adjvex;int dur;struct node*next;edgenode;/边表结点typedef struct vext

10、ype vertex;/顶点标识int id;/入度edgenode*link;/指向出边表vexnode;/顶点表结点vexnode dign;/AoE网数据表示,数据结构：Ve，Vl，e，l,数组 int vln,ven;int lmaxsize,emaxsize;拓扑：队列：tpordn；int front=-1,rear=-1;,初始化,void criticalpath(vexnode dig)int i,j,k,m;int front=-1,rear=-1;/用队列。顺序队列的首尾指针初值int tpordn,vln,ven;int lmaxsize,emaxsize;edgeno

11、de*p;for(i=0;in;i+)初始化，建立入度为0的队列。vei=0;if(digi.id=0)tpord+rear=i;m=0;/计数拓扑排序的顶点数,Step1:求Ve(k),从源点V1出发，令Ve(1)=0，按拓扑序列次序求出其余各顶点事件的最早发生时间:Ve(k)=max Ve(j)+ACTjk jT 其中T是以顶点Vk为尾的所有边的顶点集合(2kn)如果网中有回路，不能求出关键路径则算法中止；否则转Step2。,j,k,j2,jn,j1,T,Ve(j),ACTjk,.,.,模型,方法,j,k,jn,while(p)/遍历j的所有出边 k=p-adjvex;digk.id-;i

12、f(vej+p-durvek)vek=vej+p-dur;if(digk.id=0)tpord+rear=k;p=p-next;,求vek,while(front!=rear)/栈非空循环,拓扑顺序遍历AOE求Vejfront+;j=tpordfront;m+;p=digj.link;while(p)/遍历j的所有出边，修改vekk=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);,正拓扑顺序？,

13、队列变化？最后的front,rear值？,求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,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,Step2(回退阶段)：,从汇点Vn出发，令Vl(n)=Ve(n)，按逆拓扑有序求其余各顶点的最晚发生时间：Vl(j)=min Vl(k)-ACTjk kS 其中S是以顶点Vj为头的所有边的尾顶点的集合(2jn-

14、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)tpord+rear=k;p=p-next;,求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;,58,求Vl(k),1,3,2,4,a1=8,a2=12,5,6,7,8,a10=12,a9=6,a8=8,a5=2

15、8,a6=8,a7=6,a3=14,a4=10,Vl(k),58,58,58,58,58,58,58,1 2 3 4 5 6 7 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,Step3：,求每一项活动ai的最早开始时间:e(i)=Ve(j)最晚开始时间:l(i)=Vl(k)-ACTjk若某条边满足e(

16、i)=l(i)，则它是关键活动。为了简化算法,可以在求关键路径之前已经对各顶点实现拓扑排序,并按拓扑有序的顺序对各顶点重新进行了编号。不是任意一个关键活动的加速一定能使整个工程提前。想使整个工程提前，要考虑各个关键路径上所有关键活动。,求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;,求：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,