查看“︁AOE网”︁的源代码

{{Notability|time=2025-03-01T05:57:00+00:00}}
{{noteTA
|G1=IT
}}
{{多個問題|
{{copyedit|time=2011-11-17T11:42:16+00:00}}
{{Unreferenced|time=2007-08-24}}
{{expert|subject=计算机科学|time=2011-11-17T11:42:16+00:00}}
{{Tone|time=2024-07-13T03:08:59+00:00}}
}}
{{Merge |1=项目网络图|time=2022-07-21T02:55:11+00:00}}
'''AOE网'''（Activity On Edge Network）即边表示[[活动]]的网，是一个带权的[[有向无环图]]，其中[[顶点 (图论)|顶点]]表示[[事件]]（Event），每个事件表示在它之前的活动已经完成，在它之后的活动可以开始，[[弧]]表示活动，[[权]]表示活动持续的时间。AOE网可用来估算[[工程]]的完成时间。由于整个工程只有一个开始点和一个完成点，故在正常的情况（无环）下，网中只有一个[[入度]]为零的点（[[源点]]）和一个[[出度]]为零的点（[[汇点]]）。

== AOE网有待研究的问题 ==
#完成整项工程至少需要多少时间？
#哪些活动是影响工程进度的关键？

由于在AOE网中有些活动可以[[并行]]地进行，所以完成工程的最短时间是从开始点到完成点的最长路径的长度（[[路径]]上各活动持续时间之和）。路径长度最长的路径叫做[[关键路径]]。假设开始点是<math>v_1</math>，从<math>v_1</math>到<math>v_i</math>的最长路径长度叫做事件<math>v_i</math>的'''最早发生时间'''，这个时间决定了所有以<math>v_i</math>为尾的[[弧]]所表示的活动的'''最早开始时间'''。用e(i)表示活动<math>a_i</math>的最早开始时间，l(i)为一个活动的'''最迟开始时间'''，这是在不推迟整个工程完成的前提下，活动<math>a_i</math>最迟必须开始进行的时间。两者之差l(i)-e(i)意味着完成活动<math>a_i</math>的'''时间余量'''。l(i)=e(i)的活动叫做'''关键活动'''。关键路径上的所有活动都是'''关键活动'''，提前完成'''非关键活动'''（不在关键路径的活动）并不能加快工程的进度。为了求得AOE网中活动的e(i)和l(i)，首先应求得事件的最早发生时间ve(j)和最迟发生时间vl(j)。如果活动<math>a_i</math>由弧<j, k>表示，其持续时间记为dut(<j, k>)，则有：e(i) = ve(j), l(i) = vl(k) - dut(<j, k>)。求ve(j)和vl(j)需分两步进行：

#从ve(0)=0开始向前递推，其中T是所有以第j个顶点为头的弧的集合。
<math>ve(j) = Max \left \{ ve(i) + dut(<i,j>) \right \} \quad <i,j> \in T, j=1,2,...n </math>
#从vl(n-1)=ve(n-1)起向后递推，其中S是所有以第i个顶点为尾的弧的集合。
<math>vl(i) = Min \left \{ vl(j) - dut(<i,j>) \right \} \quad <i,j> \in S, i=n-2,n-3,...0 </math>

活动<math>a_i</math>的'''最早开始时间'''e[i]
*若活动<math>a_i</math>是由弧<<math>v_i</math>,<math>v_j</math>>表示，根据AOE网的性质，只有事件<math>v_i</math>发生了，活动<math>a_i</math>才能开始。也就是说，活动<math>a_i</math>的最早开始时间应等于事件<math>v_i</math>的最早发生时间。因此，有：e[i]=ve[i] 

活动<math>a_i</math>的'''最晚开始时间'''l[i]
*活动<math>a_i</math>的最晚开始时间指，在不推迟整个工程完成日期的前提下，必须开始的最晚时间。若 由弧< <math>v_i</math>,<math>v_j</math>>>表示，则<math>a_i</math>的最晚开始时间要保证事件<math>v_j</math>的最迟发生时间不拖后。因此，应该有：l[i]=vl[j]-dut(<<math>v_i</math>,<math>v_j</math>>) 

由此得到求'''关键路径'''的算法：
#输入e条[[弧]]<j, k>，建立AOE网的存储结构；
#从[[源点]]出发，令ve[0]=0，按[[拓扑顺序]]求其余各[[顶点 (图论)|顶点]]的最早发生时间ve[i]（<math>1 \leq i \leq n-1</math>）。如果得到的拓扑有序序列中顶点个数小于网中顶点数n，则说明网中存在环，不能求关键路径，算法终止，否则转到步骤（3）；
#从[[汇点]]vn出发，令vl[n-1]=ve[n-1]，按[[逆拓扑顺序]]求其余各顶点的最迟发生时间vl[i]（<math>n-2 \geq i \geq 2</math>）；
#根据各[[顶点 (图论)|顶点]]的ve和vl值，求每条弧s的最早开始时间e(s)和最迟开始时间l(s)。若某[[弧]]满足条件e(s)=l(s)，则为关键活动。

[[Category:数据结构]]
[[Category:需要计算机科学专家关注的页面]]