蛤蟆的数据结构笔记之四十八的有向无环图的应用关键路径

《蛤蟆的数据结构笔记之四十八的有向无环图的应用关键路径》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、48.蛤蟆的数据结构笔记之四十八的有向无环图的应用关键路径本篇名言：“富贵不淫贫贱乐,男儿到此是豪雄。--程颢”这次来看下有向无环图的另一个应用关键路径。1.关键路径与AOV-网相对应的是AOE-网(ActivityOnEdge)即边表示活动的网。AOE-网是一个带权的有向无环图，其中，顶点表示事件(Event)，弧表示活动，权表示活动持续的时间。通常，AOE-网可用来估算工程的完成时间。如下图1关键路径法(CriticalPathMethod,CPM)是一种基于数学计算的项目计划管理方法，是网络图计划方法的一种，属于肯定型的网络图。关键路径法将项目分解成为多个独立的活动

2、并确定每个活动的工期，然后用逻辑关系（结束-开始、结束-结束、开始-开始和开始结束）将活动连接，从而能够计算项目的工期、各个活动时间特点（最早最晚时间、时差）等。在关键路径法的活动上加载资源后，还能够对项目的资源需求和分配进行分析。关键路径法是现代项目管理中最重要的一种分析工具。根据绘制方法的不同，关键路径法可以分为两种，即箭线图（ADM）和前导图（PDM）。箭线图（ADM）法又称为双代号网络图法，它是以横线表示活动而以带编号的节点连接活动，活动间可以有一种逻辑关系，结束-开始型逻辑关系。1.关键路径的若干基本概念下面的阐述中，设AOE网的起点为v0终点为vn.1．关键路

3、径AOE网中，从事件i到j的路径中，加权长度最大者称为i到j的关键路径（CriticalPath），记为cp(i,j)。特别地，始点0到终点n的关键路径cp(0,n)是整个AOE的关键路径。显然，关键路径决定着AOE网的工期，关键路径的长度就是AOE网代表的工程所需的最小工期。2．事件最早/晚发生时间事件vi的最早发生时间ve(i)定义为：从始点到vi的最长（加权）路径长度，即cp(0,i)事件vi的最晚发生时间vl(i)定义为：在不拖延整个工期的条件下，vi的可能的最晚发生时间。即vl(i)=ve(n)-cp(i,n)3．活动最早/晚开始时间活动ak=的最

4、早开始时间e(k)：等于事件vi的最早发生时间，即     e(k)=ve(i)=cp(0,i)活动ak=的最晚开始时间l(k)定义为：在不拖延整个工期的条件下，该活动的允许的最迟开始时间，即        l(k)=vl(j)–len(i,j)这里，vl(j)是事件j的允许的最晚发生时间，len(i,j)是ak的权。活动ak的最大可利用时间：定义为l(k)-e(k) 4．关键活动若活动ak的最大可利用时间等于0（即(l(k)=e(k)），则称ak为关键活动，否则为非关键活动。显然，关键活动的延期，会使整个工程延期。但非关键活动不然，只要它的延期量不超过它的

5、最大可利用时间，就不会影响整个工期。关键路径的概念，也可以用这里的关键活动定义，即有下面的：(一) 基本算法    关键路径算法是一种典型的动态规划法，这点在学了后面的算法设计方法后就会看到。下面就来介绍该算法。设图G=(V,E)是个AOE网，结点编号为1,2,...,n，其中结点1与n分别为始点和终点，ak=∈E是G的一个活动。 根据前面给出的定义，可推出活动的最早及最晚发生时间的计算方法：  e(k)=ve(i)  l(k)=ve(j)-len(i,j)  结点的最早发生时间的计算，需按拓扑次序递推：                 ve(1)=0     

6、            ve(j)=MAX{ve(i)+len(i,j)}　对所有∈E的i  结点的最晚发生时间的计算，需按逆拓扑次序递推：                 vl(n)=ve(n)                 vl(i)=MIN{vl(j)-len(i,j)}　对所有∈E的j 关于 ve与vl的求法，可参阅图215。这种计算方法，依赖于拓扑排序，即计算ve(j)前，应已求得j的各前趋结点的ve值，而计算vl(i)前，应已求得i的各后继结点的vl值。ve的计算可在拓扑排序过程中进行，即在每输出一个结点i后，在删除i的每个出边

7、>（即入度减1）的同时，执行                if(ve[i]+len(i,j))>ve[j])　                ve[j]=ve[i]+len(i,j) 实际上，该操作对i的每个后继j分别进行一次。因此对程序作少量扩充即可求得ve。vl的值可按类似的方法在逆拓扑排序过程（即直接按与拓扑序列相反的次序输出结点的过程）中求得，但一般不必专门这样进行。事实上，通过逆方向使用拓扑序列即可递推出各vl的值，假定拓扑序列是topoSeq，则vl的值的求法为（结点编号为1~n）。求图21-6的AOE网的所有事