软件设计师考试重点解析——关键路径[2]

软件设计师 责任编辑:糯米团子 2015-08-22

添加老师微信

备考咨询

加我微信

摘要:对于前面的两个概念很多人不能理解:从源点开始到汇点递推以后,我们已经得到了关键路径的长度,按理把这些点记录下来,就得到了关键路径,为什么在此时,还要从汇点到源点进行递推,来求关键路径,这样岂不多此一举?其实不是这样的,一个AOE网络中可能有多条关键路径,若我们只正推过去,只能求得一条关键路径,而不能找出所有的关键路径。   要求一个AOE的关键路径,一般需要根据以上变量列出一张表格,逐个检查。

  点击进入>>>>>

    对于前面的两个概念很多人不能理解:从源点开始到汇点递推以后,我们已经得到了关键路径的长度,按理把这些点记录下来,就得到了关键路径,为什么在此时,还要从汇点到源点进行递推,来求关键路径,这样岂不多此一举?其实不是这样的,一个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,其余的依次类推。

    最迟发生时间和最迟开始时间要先求出关键路径的长度后,再进行逆推。通过上面求最早发生时间,我们可以求得关键路径长度为10。

    现在可以开始逆推了。

    首先由于关键路径长度为10,所以V7的最迟发生时间是10,再看V6,V6到V7有a10,长度为4,所以V6的最迟发生时间是10-4=6,同样V5到V7有a9,长度为3,所以V5的最迟发生时间是10-3=7,依次类推,此项值对应表1中的Vl(j)。

    接下来求最迟开始时间。

    V7的最迟开始时间为10,a9,a10都指向V7,a9=3,a10=4,所以a9的最迟开始时间为10-3=7,a10的最迟开始时间为10-4=6。V6的最迟开始时间为6,a7指向V6,a7=3,所以a7的最迟开始时间为6-3=3。此项值对应表1中的l(i)。

   相关推荐:

   希赛软件设计师题库

   软件设计师考试必看如何应考?

   2015年下半年软件设计师考试报名指南

   软件设计师级考试大纲(2004年新版)

   


更多资料
更多课程
更多真题
温馨提示:因考试政策、内容不断变化与调整,本网站提供的以上信息仅供参考,如有异议,请考生以权威部门公布的内容为准!

软考备考资料免费领取

去领取