CWYAlpha

Just another WordPress.com site

Thought this was cool: 数据结构重读 – AOV网和关键路径

leave a comment »


与AOV网对应的,还有一个AOE网。

AOE(Activity On Edge)网:顾名思义,用边表示活动的网。

与AOV不同,活动都表示在了边上,如下图所示:

如上所示,共有11项活动(11条边),9个事件(9个顶点)。

整个工程只有一个开始点和一个完成点

即只有一个入度为零的点(源点)和一个出度为零的点(汇点)。

(1) 关键路径:是从开始点到完成点的最长路径的长度。路径的长度是边上活动耗费的时间。

(2) 最早发生时间:v1到vi的最长路径叫做vi的最早发生时间,用ei表示。例如上图中,v5的最早发生时间是max(6+1, 4+1) = 7。

(3) 最迟开始时间:在不推迟整个工程完成的前提下,活动i最迟必须开始进行的时间,用l(i)表示。l(i) – e(i)是活动的时间余量。

(4) 关键活动:l(i)=e(i)的活动称为关键活动。

关键路径上的活动都是关键活动。

提前完成非关键活动并不能加快工程进度(类似木桶效应)。

AOE网的主要活动就是识别出哪些是关键活动,以便争取提高关键活动的工效,缩短整个工期。

求关键路径的算法

 

 

 

 
from 四号程序员四号程序员: http://www.coder4.com/archives/3492

Written by cwyalpha

六月 25, 2012 在 12:55 下午

发表在 Uncategorized

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s

%d 博主赞过: