软件设计师重点难点-关键路径.doc

软件设计师重点难点——关键路径关键路径这个知识点在软件设计师考试中,是一个难点。   说到关键路径这个概念,大家应该多少有些印象,可能都知道它是“最长路径”而不是“最短路径”,但说到它为什么是最长路径,提出这个概念的用意何在,它有什么应用,在计算机中关键路径是如何求的等问题却没有几个人能真正搞清楚,甚至书上给出了完整的例子,都有很多人看不懂。下面我先会简单的说明基本概念,然后以一个例子,结合平时希赛教育学员的疑问,对这个知识点进行详细的分析。在AOV网络中,如果边上的权表示完成该活动所需的时间,则称这样的AOV为AOE网络。例如,图1表示一个具有10个活动的某个工程的AOE网络。图中有7个顶点,分别表示事件1~7,其中1表示工程开始状态,7表示工程结束状态,边上的权表示完成该活动所需的时间。下面我们来理解一下关键路径的思想,图1虽节点不多,但是为了让问题变得更为简单、直观,我们画另一个AOE网络,如图2所示。从图2中我们可以看出,关键路路径实际上是从源点到目的地的最长路径。为什么是最长路径呢?因为图中的某些事件是可以并发执行的。如图2所示,当到达V1后,可以同时往V2,V3,V4三个方向走,而V2,V3,V4都有到Vk的路径,且长度都为1,并且Vk是终点,则关键路径是V1->V2->Vk。因为这条路径最长,只要这条路径到目的地Vk时其他的都已经到达Vk。而在这条关键路径上的活动a2,a5称为关键活动。为了找出给定的AOE网络的关键活动,从而找出关键路径,先定义几个重要的量: Ve(j)、Vl(j):顶点j事件最早、最迟发生时间。 e(i)、l(i):活动i最早、最迟开始时间。从源点V1到某顶点Vj的最长路径长度称为事件Vj的最早发生时间,记为Ve(j)。Ve(j)也是以Vj为起点的出边<Vj,Vk>所表示的活动ai的最早开始时间e(i)。在不推迟整个工程完成的前提下,一个事件Vj允许的最迟发生时间记为Vl(j)。显然,l(i)=Vl(j)-(ai所需时间),其中j为ai活动的终点。满足条件l(i)=e(i)的活动为关键活动。求顶点Vj的Ve(j)和Vl(j)可按以下两步来做。(1)由源点开始向汇点递推。其中,E1是网络中以Vj为终点的入边集合。(2)由汇点开始向源点递推。其中,E2是网络中以Vj为起点的出边集合。对于前面的两个概念很多人不能理解:从源点开始到汇点递推以后,我们已经得到了关键路径的长度,按理把这些点记录下来,就得到了关键路径,为什么在此时,还要从汇点到源点进行递推,来求关键路径,这样岂不多此一举?其实不是这样的,一个AOE网络中可能有多条关键路径,若我们只正推过去,只能求得一条关键路径,而不能找出所有的关键路径。要求一个AOE的关键路径,一般需要根据以上变量列出一张表格,逐个检查。例如,求图1所示的求AOE关键路径的过程如表1所示。因此,图1的关键活动为a1,a2,a4,a8和a9,其对应的关键路径有两条,分别为(V1,V2,V5,V7)和(V1,V4,V5,V7),长度都是10。其实从学员的疑问可以看出,最关键的问题就在于此表如何填写。首先值得我们注意的一点是,对于顶点的V1,V2等事件,有最早,最迟发生时间;对于边a1,a2,a3,等活动,有最早,最迟开始时间。Ve(j)表示的是顶点j的最早发生时间,Vl(j)表示的是顶点j的最迟发