数据结构与算法分析课件.ppt
数据结构与算法分析数据结构与算法分析第六章第六章 关键路径（关键路径（5）1谢谢观赏2019-8-216.7 关键路径关键路径(1)(1)如何建立一个工程进度控制模型？如何估算完成整个工如何建立一个工程进度控制模型？如何估算完成整个工程至少需要多少时间程至少需要多少时间(假设网络中没有环假设网络中没有环)?)?(2)(2)为缩短完成工程所需的时间为缩短完成工程所需的时间,应当加快哪些活动应当加快哪些活动?(3)(3)人们用人们用AOEAOE网解决这个问题网解决这个问题2谢谢观赏2019-8-21AOE网（网（Activity On Edge Network）在带权的有向图中，n用结点表示事件：所有入边上进行的活动均已完成的事件n用边表示活动：起始结点事件发生后所开展的活动n边的上权表示活动的开销（如持续时间）则称此有向图为“边表示活动的网络”,简称AOE网。1324a1=8a2=125678a10=12a9=6a8=8a5=28a6=8a7=6a3=14a4=103谢谢观赏2019-8-21AOE网的性质网的性质n活动开始时间：只有在某个顶点所代表的事件发生后，从该顶点出发的各有向边代表的活动才能开始;n事件发生时间：只有在进入某一顶点的各有向边代表的活动已经结束，该顶点所代表的事件才能发生；n表示实际工程计划的AOE网应该是无环的，并且存在唯一的入度为0的开始顶点（源点）和唯一的出度为0的结束点（汇点）。4谢谢观赏2019-8-21AOE网研究的主要问题：网研究的主要问题：如果用AOE 网表示一项工程，那么仅仅考虑各个子工程之间的优先关系还不够，更多地是关心整个工程完成的最短时间是多少，哪些活动的延迟将影响整个工程进度,而加速这些活动能否提高整个工程的效率,因此AOE网有待研究的问题是:(1)完成整个工程至少需要多少时间？(2)哪些活动是影响工程进度的关键活动？5谢谢观赏2019-8-21路径长度、关键路径、关键活动：路径长度、关键路径、关键活动：n路径长度：是指从源点到汇点路径上所有活动的持续时间之和。n关键路径：完成工程的最短时间是从源点到汇点的最大路径长度。因此，把从源点到汇点具有最大长度的路径称为关键路径。n一个AOE中，关键路径可能不只一条。n关键活动：关键路径上的活动称为关键活动。n在关键路径长度的范围内，可以安排并行的活动6谢谢观赏2019-8-21举例：奥运会竞赛日程举例：奥运会竞赛日程n地点：主会场n需要考虑的场地：中心、跑道、沙坑n需要考虑的项目：短跑、长跑、马拉松、铅球、跳高、跳远。n源点：开幕式;终点:闭幕式7谢谢观赏2019-8-21术语：术语：ve(j),vl(j),e(i),l(i),nve(j):事件vj的最早发生时间。事件用v标识，事件的编号用括号中的数字标识，v的下标区分“最早”和“最晚”。vl(j):事件vj的最晚发生时间。n事件用“发生”描述。ne(i):活动ai的最早开始时间。没有v的符号就是表示活动，括号中是活动的编号，e表示最早开始时间，l表示最晚。l(i):活动ai的最晚开始时间。n活动用“开始”8谢谢观赏2019-8-21Ve(j)：事件事件vj的最早发生时间的最早发生时间Ve(j)从源点V1 到顶点Vj 的最长路径长度。1324a1=8a2=125678a10=12a9=6a8=8a5=28a6=8a7=6a3=14a4=10从源点到顶点Vj的最长路径，可以包括所有以顶点Vj为终点的全部活动所需时间。经过这段路径，事件Vj才有可能发生。Ve(6)是多少？9谢谢观赏2019-8-21e(i):活动活动ai 的最早可能开始时间的最早可能开始时间 若活动ai 在边上,则e(i)是顶点Vj 最早时间。事件Vj发生，表明以Vj为终点的活动全部结束。所以，以Vj为起点的所有活动ai可以立即开始。1324a1=8a2=125678a10=12a9=6a8=8a5=28a6=8a7=6a3=14a4=10e(i)=Ve(j).(1)jai10谢谢观赏2019-8-21Vl(k)：事件事件Vk的最迟发生时间的最迟发生时间n是在保证汇点Vn在Ve(n)时刻完成的前提下，事件Vk的允许的最迟开始时间。在不推迟工期的情况下，一个事件最迟发生时间Vl(k)应该等于汇点的最早发生时间Ve(n)减去从Vk到Vn的最大路径长度。n还有什么含义？以 vk为终点的活动的最迟完成时间。1324a1=8a2=125678a10=12a9=6a8=8a5=28a6=8a7=2a3=14a4=10Ve(n)：582240244658Ve(4)：22Vl(4)：325826261282011谢谢观赏2019-8-21L(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 的持续时间（上的权）。VkaiVj12谢谢观赏2019-8-21nL(i)-e(i)表示活动ai 的最早可能开始时间和最迟允许开始时间的时间余量。关键路径上的活动都满足：l(i)=e(i).(3)nl(i)=e(i)表示活动是没有时间余量的关键活动。由上述分析知，为找出关键活动，需要求各个活动的e(i)与l(i)，以判别一个活动ai是否满足l(i)=e(i)。nVe(k)和Vl(k)可由拓扑排序算法得到。ne(i)：e(i)Ve(j)nl(i)：l(i)=Vl(k)-ACTjk时间余量时间余量l(i)-e(i)jaikaikj13谢谢观赏2019-8-21思考：(1)完成整个工程至少需要多少时间(假设网络中没有环)?(2)为缩短完成工程所需的时间,应当加快哪些活动?分析：n在AOE网络中,有些活动顺序进行顺序进行，有些活动并行进行并行进行。n从源点到各个顶点，以至从源点到汇点的有向路径可能不止一条。这些路径的长度也可能不同。完成不同路径的活动所需的时间虽然不同，但只有各条路径上所有活动都完成了，整个工程才算完成。n因此，完成整个工程所需的时间取决于从源点到汇点的最长路径长度，即在这条路径上所有活动的持续时间之和。这条路径长度最长的路径就叫做关键路径(Critical Path)。14谢谢观赏2019-8-21关键路径与关键活动n复习关键路径概念：完成工程的最短时间是从源点到汇点的最大路径长度。因此，把从源点到汇点具有最大长度的路径称为关键路径n要找出关键路径，必须找出关键活动，即不按期完成就会影响整个工程完成的活动。n关键活动概念：那些满足l(i)=e(i)的活动ain关键路径上的所有活动都是关键活动。因此，只要找到了关键活动，就可以找到关键路径.15谢谢观赏2019-8-21基本思路：基本思路：1.拓扑排序,并求出Ve(k)，2.逆拓扑排序，求Vl(k)3.根据公式和权值邻接矩阵ACTNN求e（i），l（i）4.根据e（i），l（i）求出关键活动5.根据关键活动求出关键路径1324a1=8a2=125678a10=12a9=6a8=8a5=28a6=8a7=6a3=14a4=1016谢谢观赏2019-8-21数据结构：数据结构：AOE图图typedef struct node int adjvex;int dur;struct node*next;edgenode;/边表结点typedef struct vextype vertex;/顶点标识int id;/入度edgenode*link;/指向出边表vexnode;/顶点表结点vexnode dign;/AoE网数据表示1324a1=8a2=125678a10=12a9=6a8=8a5=28a6=8a7=6a3=14a4=1017谢谢观赏2019-8-21数据结构：数据结构：Ve，Vl，e，ln数组 int vln,ven;int lmaxsize,emaxsize;n拓扑：队列：tpordn；int front=-1,rear=-1;18谢谢观赏2019-8-21初始化初始化 void criticalpath(vexnode dig)int i,j,k,m;int front=-1,rear=-1;/用队列。顺序队列的首尾指针初值int tpordn,vln,ven;int lmaxsize,emaxsize;edgenode*p;for(i=0;iadjvex;digk.id-;if(vej+p-durvek)vek=vej+p-dur;if(digk.id=0)tpord+rear=k;p=p-next;20谢谢观赏2019-8-21求求vekwhile(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(madjvex;if(vlk-p-durdur;if(digk.id=0)tpord+rear=k;p=p-next;24谢谢观赏2019-8-21求求Vlkfor(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-2158求求Vl(k)1324a1=8a2=125678a10=12a9=6a8=8a5=28a6=8a7=6a3=14a4=10Vl(k)585858585858581 2 3 4 5 6 7 8令“-”=0080706050403020114428610486651876712812382585858585858585834876521tpord46383212804638408032124026谢谢观赏2019-8-21Step3：n求每一项活动ai的最早开始时间:e(i)=Ve(j)n最晚开始时间:l(i)=Vl(k)-ACTjkn若某条边满足e(i)=l(i)，则它是关键活动。n为了简化算法,可以在求关键路径之前已经对各顶点实现拓扑排序,并按拓扑有序的顺序对各顶点重新进行了编号。n不是任意一个关键活动的加速一定能使整个工程提前。n想使整个工程提前，要考虑各个关键路径上所有关键活动。27谢谢观赏2019-8-21求求ei,li,关键活动关键活动li-eii=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-ei1324a1=8a2=125678a10=12a9=6a8=8a5=28a6=8a7=6a3=14a4=7Ve(k)122258464028801 2 3 4 5 6 7 8令“-”=0182726152413120146465778320128224028(38)465829谢谢观赏2019-8-21
