(2016年软件设计师教程重难点精讲二.docVIP

2016年软件设计师教程重难点精讲（二） ? ? ? 2016下半年软考软件设计师报名即将开始，下面是希赛软考学院整理的软件设计师教程重点难点精讲，希望对大家有所帮助。?? ? ? ? ? ? ??关键路径这个知识点在软件设计师考试中，是一个难点。 ? ? ? 说到关键路径这个概念，大家应该多少有些印象，可能都知道它是“最长路径”而不是“最短路径”，但说到它为什么是最长路径，提出这个概念的用意何在，它有什么应用，在计算机中关键路径是如何求的等问题却没有几个人能真正搞清楚，甚至书上给出了完整的例子，都有很多人看不懂。下面我先会简单的说明基本概念，然后以一个例子，结合平时学员的疑问，对这个知识点进行详细的分析。 ? ? ? 在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-gt;V2-gt;Vk。因为这条路径最长，只要这条路径到目的地Vk时其他的都已经到达Vk。而在这条关键路径上的活动a2，a5称为关键活动。 ? ? ? 为了找出给定的AOE网络的关键活动，从而找出关键路径，先定义几个重要的量： ? ? ? Ve(j)、Vl(j)：顶点j事件最早、最迟发生时间。 ? ? ? e(i)、l(i)：活动i最早、最迟开始时间。 ? ? ? 从源点V1到某顶点Vj的最长路径长度称为事件Vj的最早发生时间，记为Ve(j)。Ve(j)也是以Vj为起点的出边所表示的活动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的最迟发生时间，e(i)表示的是活动i的最早开始时间，l(i)表示的是活动i的最迟开始时间。总的来说填这个表有以下四个步骤。 ? ? ? —由源点开始递推计算出表1-1中的Ve(j)列; ? ? ? —由Ve(7)=10，回算Vl(j)列; ? ? ? —Vl(j)列算出后用公式l(i)=Vl(j)-(ai所需要的时间); ? ? ? —由l(i)=e(i)找出关键活动，求出关键路径。 ? ? ? 下面来填写表格，首先我们来填最早发生时间和最早开始时间。 ? ? ? 因为由源点V1到顶点V2的最长路径长度是3(到V2只有一条路径，长度为3，这个很好判断)，所以V2的最早发生时间是3，从V2出发的活动有a4，a5，所以a4，a5的最早开始时间也是3。又比如，到顶点V4的最长路径长度是6，所以V4的最早发生时间是6，从V4出发的活动有a8，a8的最早开始时间也是6，其余的依次类推。 ?