数据结构 图 |
您所在的位置:网站首页 › AOV和AOE网的概念 › 数据结构 图 |
AOE定义
在带权有向图中,以顶点表示事件,有向边表示活动,边上的权值表示完成该活动的开销(如完成活动所需的时间),即用边表示活动的网络称为AOE网络。 注: AOE网络一定是有向无环图。
事件最迟发生时间:,记为Vl(i).注意这里有一个很重要的前提:保证时间不推迟的前提下(就是这个人走到V6的时间和上面的V(6)时间必须相同)。不明白可以通过下面例子找出规律。 如首先在上表中找到v6的值,如下: V1V2V3V4V5V6vl(i)08接着计算顶点V5,V5 = V6 - v5的权值 :8 - 1 = 7 ,填入表中: V1V2V3V4V5V6v(i)78接着计算V4 = V6 - V4的权值 :8 - 2 = 6,填入表中: V1V2V3V4V5V6vl(i)678接着计算V3,注意V3指向V4和V6,V3与V6:V6- V3权值:8-3=5 而V6与V4: V4 - V3权值: 6-4=2,取出V3的最小值 2 填入表中: V1V2V3V4V5V6vl(i)2678依照上面的规律完成关键活动表如下: V1V2V3V4V5V6ve(i)032668vl(i)042678 各活动计算对题目中的活动进行一个编号 同理可以依次完成各个弧的e(i)表: a1a2a3a4a5a6a7a8e(i)00332266l(i):活动a(i)的最迟开始时间,如活动a1可以写成弧即V1指向V2,那么根据下表l(1) = vl(2)- 3(a1弧的权值)= 1,即当前活动的弧尾顶点vl(i)-权值。 V1V2V3V4V5V6vl(i)042678根据上面的规律可以完成活动表: a1a2a3a4a5a6a7a8e(i)00332266l(i)10442567 关键活动计算上面计算出活动表,根据活动表筛选出关键活动,条件就是e(i)=l(i),如下: a1a2a3a4a5a6a7a8e(i)00332266l(i)10442567e(i)-l(i)10110301筛选出的关键活动就是: a2, a5, a7 关键路径 v1,v3,v4,v6 总结 |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |