因为要考软设,所以今天遇到一题有关AOE知识点的题,突然感到以前学习的弊病,对知识点没有去理解,凭感觉,总是认为很简单.已经掌握了,没遇到题目真的不知道其实以前是误解了定义.今天才感觉有点难度哦.主要是活动最早开始时间和最迟开始时间.书上是这样定义的:假设开始点是V1,从V1到Vi的最长路径叫做事件Vi的最早发生时间。这个时间决定了所有以Vi为尾的弧所表示的活动的最早开始时间。而最迟开始时间就是在不推迟整个工程完成的前提下，活动ai最迟必须开始进行的时间。看概念真的有点不知所措。所以具体如下: 最早开始时间：设ve[k]表示vk事件的最早发生时间，ve[j]表示vk的一个前驱事件vj的最早发生时间，dut(<j,k>)表示边<j,k>上的权，p表示vk顶点所有入边的集合，则网中每个事件vk(0≤k≤n-1)的最早发生时间ve可由下式，按照拓扑有序计算出来。      ve(k) = 0 (k = 0)      max{ve[j] +dut(< j,k >)} (l≤k≤n- 1, <j,k>∈p)按照此公式和拓扑有序计算出图所示的AOE网中每个事件的最早发生时间为：ve(0) = 0ve(1) = ve(0) +dut( <0,1 > ) =0+6=6ve(2) = ve(0) + dut( < 0,2 > ) = 0 + 4 = 4ve(3) = ve(0) + dut( <0,3 > ) =0+5 = 5ve(4) = max{ve(1) + dut( < 1,4 > ), ve(2) + dut( < 2,4 > ) }= max{6 + 1,4+ 1} =7ve(5) = ve(3) +dut( < 3,5 > ) = 5 + 2= 7ve(6) = ve(4) +dut( <4,6> ) =7+9= 16ve(7) = max{ve(4) +dut( < 4,7 > ), ve(5) +dut( < 5,7 > )} = max{7 + 7,7 + 4} = 14ve(8) = max{ve(6) + dut( < 6,8 > ), ve(7) + dut( < 7,8 > ) } = max{16+ 2,14+4} = 18最后得到的ve(8)就是汇点的最早发生时间，从而可知整个工程至少需要18天完成。 最迟开始时间：设vl[j]表示待求的vj事件的最迟发生时间，vl[k]表示vj的一个后继事件vk的最迟发生时间，dut(<j，k>)表示边<j，k>上的权，s表示vj顶点的所有出边的集合，则AOE网中每个事件vj(0≤j≤n-1)的最迟发生时间vl[j]=ve[n- 1] (j = n- 1)min{vl[k]-dut(<j,k>)} (0≤j≤n-2, <j,k>∈s)按照此公式和逆拓扑有序计算出图AOE网中每个事件的最迟发生时间为：vl[8] =ve[8] = 18vl[7] = vl[8] -dut( <7,8> ) = 18-4= 14vl[6] =vl[8] - dut(<6,8> ) = 18-2= 16vl[5] = vl[7] -dut( <5,7> ) = 14-4= 10vl[4] = min{vl[7] -dut( <4,7> ), vl[6] -dut( <4,6> )}= min{ 14 - 7,16-9} = 7vl[3] =vl[5] -dut( <3,5> ) = 10-2=8vl[2] = vl[4] - dut( <2,4> ) =7- 1 =6vl[l] = vl[4] - dut( < 1,4> ) =7- 1 =6vl[0] =min{vl[1] -dut(<0,1>), vl[2]-dut(<0,2> ), vl[3] -dut(<0,3>)} = min{6-6,6-4,8-5}= 0  设事件vj的最早发生时间为ve[j]，它的一个后继事件vk的最迟发生时间为vl[k]，则边<j，k>上的活动aj的最早开始时间e[i]和最迟开始时间l[i]的计算公式重新列出如下：e[i]=ve[j]l[i]=vl[k]-dut(<j，k>) 活动最迟开始时间      根据此计算公式可计算出AOE网中每一个活动aj的最早开始时间e[i]，最迟开始时间l[i]和开始时间余量l[i]-e[i]。  参考文章：http://ie.zheou.cn/zy/ds/seven/7.6.htm

评论