七图)).ppt

练习 有AOV网如下：给出它的5个拓扑序列。 V1 V4 V3 V6 V5 V2 有图如下：用prim算法画出最小生成树的生长过程及算法执行过程中辅助数组Closedge的变化。(从v1出发） V0 V3 V6 V2 V5 V4 V1 11 6 9 12 10 7 4 16 5 4 8 7.5.2 关键路径(解决第二个问题---估算工期） 为解决第二个问题，通常可用称为AOE网的有向图表示工程流程 用边表示活动，顶点表示事件。 AOE网是一个带权的有向无环图，权值表示活动的持续时间。 1.术语 *事件：前后两组活动的分隔点，表示前面的所有活动已经完成，后继活动可以开始。在AOE网中，只有一个无前驱的顶点，表明工程的开始，称为源点，也只有一个无后继的顶点，表示工程全部完成，成为汇点。 *路径长度：路径上权值的和。 *关键路径：路径长度最长的路径，关键路径的长度为完成整个工程所需要的最短时间，即工期。 *关键活动：关键路径上的活动。 V9 V3 V6 V2 V5 V4 V1 V8 V7 (v5,v7)a7=9,(v5,v8)a8=7,(v6,v8)a9=4, (v7,v9)a10=2,(v8,v9)a11=4 (v1,v2)a1=6,(v1,v3)a2=4,(v1,v4)a3=5, (v2,v5)a4=1,(v3,v5)a5=1,(v4,v6)a6=2 6 1 4 2 1 5 7 9 4 2 4 *事件：图中V1,V2,V3,……为事件。例如：事件V5发生，表示活动a4,a5已经完成，a7,a8可以开始。V1为源点,V9为汇点。 *路径长度： (V1,V2,V5,V7,V9)的路径长度为18 *关键路径: (V1,V2,V5,V7,V9)和(V1,V2,V5,V8,V9) *关键活动：a1,a4,a7,a8,a10,a11 * 记号： Vi---事件；ai----活动。 e(i):ai的最早开始时间；l(i):ai的最迟开始时间 Ve(j)：事件j的最早开始时间；Vl(j):事件j的最迟开始时间 dut(j,k):活动Vj,Vk的持续时间（边上的权值） 2. 事件与活动的关系 1)若活动ai由弧j,k表示，则活动的最早发生时间和最迟发生时间分别为： 由于活动必须在两个事件发生的时间间隔内进行，因此存在如下关系： e(i)=Ve(j); l(i)=Vl(k)-dut(j,k) 因此，要想求活动的最早和最迟发生时间应该首先求出关联的两个事件的最早和最迟发生时间。 那么，如何求图中各个事件的最早和最迟发生时间呢？ 某个事件的最早发生时间应该由它之前的所有活动最迟结束时间确定的,因此，要求事件的最早发生时间必须求出它之前所有活动结束时间最迟的时间。 vj vi1 … … vin 假设所有vi事件最早发生时间确定，那么可以通过vi和vj确定的活动持续时间推知到对应vi,vj结束最迟时间，从而能搞找出结束最迟活动的结束时间，这个结束时间就是vj的最早发生时间。 2)事件j的最早发生时间： Ve(j)=max{Ve(i)+dut(i.,j)} Ve(1)=0 某个事件的最迟开始时间 3) 事件的最迟发生时间： Vl(i)=min{Ve(j)-dut(i.,j)} Vl(n)=Ve(n) vj1 …… vjn vi 4)关键活动的条件：e(i)=l(i) 解题的步骤应该按照如下思路进行： 步骤一：根据第1个事件的最早发生时间，以及各个活动持续的时间，递推方式求出各个事件的最早发生时间； 步骤二：根据整个工程周期可以得到最后一个事件最迟发生的事件，然后根据最后一个事件最迟发生的时间和各个活动持续的时间，逆向求出各个事件最迟发生时间； 步骤三：利用利用各个活动相关联的两个事件最早最迟发生时间判断各个活动是否为关键活动。 3. 关键路径 有了上面的四个条件，有如下计算关键路径的算法： 1)输入e条弧，建立AOE 网。 2)拓扑排序，有环，算法结束。否则： 3)从源点V1出发，令Ve(1)=0,求其余各顶点的ve(j),(2=j=n) 4)从汇点Vn出发，令Vl(n)=Ve(n),反方向求各顶点的Vl(i) (n-1=i=1) 5)由上面的关系式：e(i)=Ve(j); l(i)=Vl(k)-dut(j,k) 求出每个活动的最早开始时间和最