- 1、本文档共6页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
[2018年必威体育精装版整理]2016年软件设计师教程重难点精讲(二)
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,其余的依次类推。
? ? ? 最迟发生时
您可能关注的文档
- [2018年必威体育精装版整理]2016年中考预测题(选择题五)MicrosoftPowerPoint演示文稿.ppt
- [2018年必威体育精装版整理]2016年中医执业医师针灸学考试大纲.docx
- [2018年必威体育精装版整理]2016年中考题平方根.ppt
- [2018年必威体育精装版整理]2016年中西医执业医师考试大纲-中医基础理论.doc
- [2018年必威体育精装版整理]2016年中西医执业医师考试大纲-实践技能.doc
- [2018年必威体育精装版整理]2016年临床执业医师考试大纲-卫生法规.docx
- [2018年必威体育精装版整理]2016年九江学院专升本《高等数学Ⅰ》考试大纲.docx
- [2018年必威体育精装版整理]2016年会计继续教育模考2.docx
- [2018年必威体育精装版整理]2016年全国卫生系列正高级职称临床医学检验临床微生物技术复习题.doc
- [2018年必威体育精装版整理]2016年公务员培训考试-新发展理念公务员读本.docx
最近下载
- LEGO乐高积木拼砌说明书42126,Ford®F-150Raptor皮卡,LEGO®Technic(年份2021)安装指南_第2份共2份.pdf
- 继电保护和安全自动装置技术规程.pdf VIP
- 2023版反假考试复习题库-上(单选题部分).pdf VIP
- (完整)2018年严重精神障碍知识技能竞赛题库.pdf VIP
- 诗词大会网络答题竞赛题库200题(含答案).pdf
- 弗洛姆的人本主义精神分析理论.ppt VIP
- 整本书阅读 会飞的教室(课件)四年级上册语文部编版.pptx
- 2024年江西司法警官职业学院单招数学考试题库及答案解析.docx
- HAIER 海尔 海尔Haier冷柜 BC BD-519HCZ 说明书.pdf
- 消防安全标志设置要求.docx VIP
文档评论(0)