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

48. 蛤蟆的数据结构笔记之四十八的有向无环图的应用关键路径 本篇名言：“富贵不淫贫贱乐 , 男儿到此是豪雄。-- 程颢” 这次来看下有向无环图的另一个应用关键路径。 1. 关键路径 与AOV-网相对应的是AOE-网(Activity On Edge)即边表示活动的网。AOE-网是一个带权的有向无环图，其中，顶点表示事件(Event)，弧表示活动，权表示活动持续的时间。通常，AOE-网可用来估算工程的完成时间。 如下图1 关键路径法(Critical Path Method, CPM)是一种基于数学计算的项目计划管理方法，是网络图计划方法的一种，属于肯定型的网络图。关键路径法将项目分解成为多个独立的活动并确定每个活动的工期，然后用逻辑关系（结束-开始、结束-结束、开始-开始和开始结束）将活动连接，从而能够计算项目的工期、各个活动时间特点（最早最晚时间、时差）等。在关键路径法的活动上加载资源后，还能够对项目的资源需求和分配进行分析。关键路径法是现代项目管理中最重要的一种分析工具。 根据绘制方法的不同，关键路径法可以分为两种，即箭线图（ADM）和前导图（PDM）。 箭线图（ADM）法又称为双代号网络图法，它是以横线表示活动而以带编号的节点连接活动，活动间可以有一种逻辑关系，结束-开始型逻辑关系。 2. 关键路径的若干基本概念 下面的阐述中，设AOE网的起点为v0终点为vn. 1．关键路径 AOE网中，从事件i到j的路径中，加权长度最大者称为i到j的关键路径（Critical Path），记为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=vi, vj的最早开始时间e(k)：等于事件vi的最早发生时间，即 ?????e(k) = ve(i) = cp(0, i) 活动ak=vi, vj的最晚开始时间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 为关键活动，否则为非关键活动。 显然，关键活动的延期，会使整个工程延期。但非关键活动不然，只要它的延期量不超过它的最大可利用时间，就不会影响整个工期。 关键路径的概念，也可以用这里的关键活动定义，即有下面的： (一)?基本算法 ????关键路径算法是一种典型的动态规划法，这点在学了后面的算法设计方法后就会看到。下面就来介绍该算法。设图G=(V, E)是个AOE网，结点编号为1,2,...,n，其中结点1与n 分别为始点和终点，ak=i, j∈E是G的一个活动。 ? 根据前面给出的定义，可推出活动的最早及最晚发生时间的计算方法： ??e(k) = ve(i) ??l(k) = ve(j) - len(i,j)?? 结点的最早发生时间的计算，需按拓扑次序递推： ?????????????????ve(1) = 0 ?????????????????ve(j) = MAX{ ve(i)+len(i, j) }　 对所有i,j ∈E的i??结点的最晚发生时间的计算，需按逆拓扑次序递推： ?????????????????vl(n) = ve(n) ?????????????????vl(i) = MIN{vl(j) - len(i, j)}　对所有i,j∈E的j? 关于?ve与vl的求法，可参阅图 215。 这种计算方法， 依赖于拓扑排序， 即计算ve( j) 前，应已求得j 的各前趋结点的ve值，而计算vl(i)前，应已求得i的各后继结点的vl值。ve的计算可在拓扑排序过程中进行，即在每输出一个结点i后，在删除i的每个出边i,j（即入度减1）的同时，执行 ????????????????if ( ve[i]+len(i,j)) ve[j] )　 ????????????????ve[j] = ve[i] + len(i,j)? 实际上，该操作对i的每个后继j分别进行一次。因此对程序作少量扩充即可求得ve。 vl的值可按类似的方法在逆拓扑排序过程（即直接按与拓扑序列相反