図のキーパス
8546 ワード
変換元:http://blog.sina.com.cn/s/blog_51b6521b0100k96i.html
(一)AOEネット
≪イベント｜Events｜ldap≫ 意味
v1 工事を始める
v2 アクティビティa 1が完了し、アクティビティa 4が開始できる
v3 アクティビティa 2が完了し、アクティビティa 5が開始できる
v4 アクティビティa 3が完了し、アクティビティa 6が開始できる
v5 アクティビティa 4とa 5が完了し、アクティビティa 7とa 8が開始され、
v6 アクティビティa 6が完了し、アクティビティa 9が開始できる
v7 アクティビティa 7が完了し、アクティビティa 10が開始する
v8 アクティビティa 8とa 9が完了し、アクティビティa 11が開始できる
v9 アクティビティa 10とa 11が完了し、工事全体が完了した.
エッジ(円弧):アクティビティ(アクション)を表します.
エッジ権:アクティビティの持続時間を表します.エッジak=の重みはlen(ak)またはlen(i,j)である.
ノード:イベント(ステータス)を表します.これは、各エッジが表すアクティビティが完了したことを示し、そのエッジが表すアクティビティが開始できることを示します.
実際、あるノードが表すイベントは、その各入辺が表すアクティビティの共通作用の結果であり、同時にその各出辺が表すアクティビティの起動条件でもある.AOE網に入っていないノードを始点,出ていないノードを終点と呼ぶ.AOEは一般に工事進捗を記述するために用いられ,ノードは工事進捗中の状態を表し,サブタスクを表す.図21‑4はAOE網であり、サブタスク11個と9個の状態を有する仮想エンジニアリングの進捗図とみなすことができる.
(二)AOEネットワークの操作
AOEネットワークに対する操作には、一般的に次のようなものがあります.
クリティカルパスCPM(Critical Path Method).この操作は、修理と建築業界における工期進捗推定に最も早く使用される.
性能推定と再審PERT(P e rformance Evaluation and Review Technique):この操作は最初に北極星式ミサイルシステムの開発のために導入された.
リソース割り当てとマルチエンジニアリングスケジューリングRAMP(Resource Allocation) and Multi-Project Scheduling)
(三) キーパスのいくつかの基本的な概念
以下の説明では、AOE網の始点をv 0終点としてvnとする.
1.キーパス
AOEネットワークでは,イベントiからjへのパスのうち,重み付け長が最も大きいものをiからjへのキーパス(Critical Path)と呼び,cp(i,j)と記す.特に、始点0から終点nまでのキーパスcp(0,n)はAOE全体のキーパスである.
明らかに、キーパスはAOEネットワークの工期を決定し、キーパスの長さはAOEネットワークが代表する工事に必要な最小工期である.
2.イベントの最も早い/遅い発生時間
イベントviの最も早い発生時間ve(i)は、始点からviまでの最長(重み付け)経路長、すなわちcp(0,i)と定義される
イベントviの最後発生時間vl(i)は、工期全体を遅らせない条件下でviの可能な最後発生時間として定義される.すなわちvl(i)=ve(n)−cp(i,n)
3.活動の最も早い/遅い開始時間
アクティビティak=の最初の開始時間e(k):イベントviの最初の発生時間、すなわち
e(k) = ve(i) = cp(0, i)
アクティビティak=の最遅開始時間l(k)は、工期全体を遅延させない条件下で、アクティビティの許容される最遅開始時間、すなわち
l(k) = vl(j) – len(i, j)
ここで、vl(j)はイベントjの許容される最も遅い発生時間であり、len(i,j)はakの重みである.
アクティブakの最大利用可能時間:l(k)-e(k)と定義
4.重要な活動
アクティブakの最大利用可能時間が0(すなわち(l(k)=e(k))に等しい場合、akをキーアクティビティと呼び、そうでない場合は非キーアクティビティと呼ぶ.
明らかに、重要な活動の延期は、工事全体を延期させる.しかし、重要な活動ではない.そうでなければ、その延期量が最大利用可能時間を超えなければ、工期全体に影響を与えない.
キーパスの概念は、ここのキーアクティビティで定義することもできます.次のようになります.
(一) きほんアルゴリズム
クリティカルパスアルゴリズムは典型的な動的計画法であり、これは後のアルゴリズム設計方法を学んだ後に見られる.以下、このアルゴリズムを紹介する.図G=(V,E)はAOE網であり、ノード番号は1,2,...,nであり、ノード1とnはそれぞれ始点と終点であり、ak=∈EはGの活動である.
前述の定義に従って、アクティビティの最も早いおよび最も遅い発生時間の計算方法を提示します.
e(k) = ve(i)
l(k) = ve(j) - len(i,j)
ノードの最初の発生時間の計算は、トポロジー順にプッシュする必要があります.
ve(1) = 0
ve(j) = MAX{ ve(i)+len(i, j) }
すべての∈Eに対するi ノードの最も遅い発生時間の計算は、逆トポロジー順に繰り返す必要があります.
vl(n) = ve(n)
vl(i)=MIN{vl(j)−len(i,j)}全∈Eに対するj
について veとvlの求め方は、図21‑5を参照してください.
この計算方法は、トポロジーソートに依存する.すなわち、ve(j)を計算する前に、jの各順方向ノードのve値を求め、vl(i)を計算する前に、iの各後続ノードのvl値を求めなければならない.veの計算は、トポロジーソートの過程において行うことができ、すなわち、1つのノードiを出力する毎に、iの各アウトエッジ(すなわち入度マイナス1)を削除しながら実行することができる
if ( ve[i]+len(i,j)) > ve[j] )
ve[j] = ve[i] + len(i,j)
実際には、この動作は、iの後続j毎に1回ずつ行われる.したがって,プログラムを少量拡張すればveを求めることができる.
vlの値は、逆トポロジーソートプロセス(すなわち、トポロジーシーケンスとは逆の順序でノードを直接出力するプロセス)で同様の方法で求めることができるが、一般的には特にそうする必要はない.実際,逆方向にトポロジーシーケンスを用いることで各vlの値を繰り出すことができ,トポロジーシーケンスがtopoSeqであると仮定すると,vlの値の求め方は(ノード番号1~n)である.
図21-6のAOEネットのすべての事件の最も早い発生時間ee()を求めます;すべてのイベントの最も遅い発生時間le();各アクティビティaiの最も早い開始時間e()と最も遅い開始時間l()は、この工事を完了するのに少なくとも何日かかりますか?それらは重要な活動であり、速度を上げた後、工事全体を工期短縮する活動があるかどうか.
ストレージ構造およびアルゴリズム設計
1.ノードの定義にeeフィールドとleフィールドを追加して、キーパスと最小工期を同時に取得するイベントの最も早い開始時間と最も遅い開始時間を記録する
2.隣接マトリクスに元の接続フラグ1の代わりにエッジ重みを使用する
3、トポロジーの順序付けを行い、トポロジーシーケンスを形成する
1 2 3 4 5 6 7 8 9
4.トポロジーシーケンス順に、前から後ろへ検索してアクティビティ(すなわちエッジ)を探し、アクティビティが存在する場合、対応するイベントの最初の開始時間を計算します.
5.トポロジーシーケンス順に、後から前へ検索してアクティビティ(すなわちエッジ)を探し、アクティビティが存在する場合、対応するイベントの遅くとも開始時間を計算します.
6、各活動の一番早い開始時間と一番遅い開始時間を計算する
アルゴリズムソース:
(一)AOEネット
≪イベント｜Events｜ldap≫ 意味
v1 工事を始める
v2 アクティビティa 1が完了し、アクティビティa 4が開始できる
v3 アクティビティa 2が完了し、アクティビティa 5が開始できる
v4 アクティビティa 3が完了し、アクティビティa 6が開始できる
v5 アクティビティa 4とa 5が完了し、アクティビティa 7とa 8が開始され、
v6 アクティビティa 6が完了し、アクティビティa 9が開始できる
v7 アクティビティa 7が完了し、アクティビティa 10が開始する
v8 アクティビティa 8とa 9が完了し、アクティビティa 11が開始できる
v9 アクティビティa 10とa 11が完了し、工事全体が完了した.
エッジ(円弧):アクティビティ(アクション)を表します.
エッジ権:アクティビティの持続時間を表します.エッジak=の重みはlen(ak)またはlen(i,j)である.
ノード:イベント(ステータス)を表します.これは、各エッジが表すアクティビティが完了したことを示し、そのエッジが表すアクティビティが開始できることを示します.
実際、あるノードが表すイベントは、その各入辺が表すアクティビティの共通作用の結果であり、同時にその各出辺が表すアクティビティの起動条件でもある.AOE網に入っていないノードを始点,出ていないノードを終点と呼ぶ.AOEは一般に工事進捗を記述するために用いられ,ノードは工事進捗中の状態を表し,サブタスクを表す.図21‑4はAOE網であり、サブタスク11個と9個の状態を有する仮想エンジニアリングの進捗図とみなすことができる.
(二)AOEネットワークの操作
AOEネットワークに対する操作には、一般的に次のようなものがあります.
クリティカルパスCPM(Critical Path Method).この操作は、修理と建築業界における工期進捗推定に最も早く使用される.
性能推定と再審PERT(P e rformance Evaluation and Review Technique):この操作は最初に北極星式ミサイルシステムの開発のために導入された.
リソース割り当てとマルチエンジニアリングスケジューリングRAMP(Resource Allocation) and Multi-Project Scheduling)
(三) キーパスのいくつかの基本的な概念
以下の説明では、AOE網の始点をv 0終点としてvnとする.
1.キーパス
AOEネットワークでは,イベントiからjへのパスのうち,重み付け長が最も大きいものをiからjへのキーパス(Critical Path)と呼び,cp(i,j)と記す.特に、始点0から終点nまでのキーパスcp(0,n)はAOE全体のキーパスである.
明らかに、キーパスはAOEネットワークの工期を決定し、キーパスの長さはAOEネットワークが代表する工事に必要な最小工期である.
2.イベントの最も早い/遅い発生時間
イベントviの最も早い発生時間ve(i)は、始点からviまでの最長(重み付け)経路長、すなわちcp(0,i)と定義される
イベントviの最後発生時間vl(i)は、工期全体を遅らせない条件下でviの可能な最後発生時間として定義される.すなわちvl(i)=ve(n)−cp(i,n)
3.活動の最も早い/遅い開始時間
アクティビティak=の最初の開始時間e(k):イベントviの最初の発生時間、すなわち
e(k) = ve(i) = cp(0, i)
アクティビティak=の最遅開始時間l(k)は、工期全体を遅延させない条件下で、アクティビティの許容される最遅開始時間、すなわち
l(k) = vl(j) – len(i, j)
ここで、vl(j)はイベントjの許容される最も遅い発生時間であり、len(i,j)はakの重みである.
アクティブakの最大利用可能時間:l(k)-e(k)と定義
4.重要な活動
アクティブakの最大利用可能時間が0(すなわち(l(k)=e(k))に等しい場合、akをキーアクティビティと呼び、そうでない場合は非キーアクティビティと呼ぶ.
明らかに、重要な活動の延期は、工事全体を延期させる.しかし、重要な活動ではない.そうでなければ、その延期量が最大利用可能時間を超えなければ、工期全体に影響を与えない.
キーパスの概念は、ここのキーアクティビティで定義することもできます.次のようになります.
(一) きほんアルゴリズム
クリティカルパスアルゴリズムは典型的な動的計画法であり、これは後のアルゴリズム設計方法を学んだ後に見られる.以下、このアルゴリズムを紹介する.図G=(V,E)はAOE網であり、ノード番号は1,2,...,nであり、ノード1とnはそれぞれ始点と終点であり、ak=∈EはGの活動である.
前述の定義に従って、アクティビティの最も早いおよび最も遅い発生時間の計算方法を提示します.
e(k) = ve(i)
l(k) = ve(j) - len(i,j)
ノードの最初の発生時間の計算は、トポロジー順にプッシュする必要があります.
ve(1) = 0
ve(j) = MAX{ ve(i)+len(i, j) }
すべての∈Eに対するi ノードの最も遅い発生時間の計算は、逆トポロジー順に繰り返す必要があります.
vl(n) = ve(n)
vl(i)=MIN{vl(j)−len(i,j)}全∈Eに対するj
について veとvlの求め方は、図21‑5を参照してください.
この計算方法は、トポロジーソートに依存する.すなわち、ve(j)を計算する前に、jの各順方向ノードのve値を求め、vl(i)を計算する前に、iの各後続ノードのvl値を求めなければならない.veの計算は、トポロジーソートの過程において行うことができ、すなわち、1つのノードiを出力する毎に、iの各アウトエッジ(すなわち入度マイナス1)を削除しながら実行することができる
if ( ve[i]+len(i,j)) > ve[j] )
ve[j] = ve[i] + len(i,j)
実際には、この動作は、iの後続j毎に1回ずつ行われる.したがって,プログラムを少量拡張すればveを求めることができる.
vlの値は、逆トポロジーソートプロセス(すなわち、トポロジーシーケンスとは逆の順序でノードを直接出力するプロセス)で同様の方法で求めることができるが、一般的には特にそうする必要はない.実際,逆方向にトポロジーシーケンスを用いることで各vlの値を繰り出すことができ,トポロジーシーケンスがtopoSeqであると仮定すると,vlの値の求め方は(ノード番号1~n)である.
for (k=1; k<=n; k++) vl[k] = ve[n]; //
for ( k=n; k>=1; k--)
{
i=topoSeq[k];
j=（i 1 ）;
while (j )
{
if (vl[j]-len(i,j)図21-6のAOEネットのすべての事件の最も早い発生時間ee()を求めます;すべてのイベントの最も遅い発生時間le();各アクティビティaiの最も早い開始時間e()と最も遅い開始時間l()は、この工事を完了するのに少なくとも何日かかりますか?それらは重要な活動であり、速度を上げた後、工事全体を工期短縮する活動があるかどうか.
ストレージ構造およびアルゴリズム設計
1.ノードの定義にeeフィールドとleフィールドを追加して、キーパスと最小工期を同時に取得するイベントの最も早い開始時間と最も遅い開始時間を記録する
2.隣接マトリクスに元の接続フラグ1の代わりにエッジ重みを使用する
3、トポロジーの順序付けを行い、トポロジーシーケンスを形成する
1 2 3 4 5 6 7 8 9
4.トポロジーシーケンス順に、前から後ろへ検索してアクティビティ(すなわちエッジ)を探し、アクティビティが存在する場合、対応するイベントの最初の開始時間を計算します.
5.トポロジーシーケンス順に、後から前へ検索してアクティビティ(すなわちエッジ)を探し、アクティビティが存在する場合、対応するイベントの遅くとも開始時間を計算します.
6、各活動の一番早い開始時間と一番遅い開始時間を計算する
アルゴリズムソース:
#include
#include
#define MaxVerNum 20
int visited[MaxVerNum];
typedef char VertexType;
typedef struct ArcNode
{
int adjvex; //
struct ArcNode * nextarc; //
int info; //
}ArcNode; //
typedef struct VNode
{
VertexType data;
int indegree;
ArcNode * firstarc;
}VNode, Adjlist[MaxVerNum];
typedef struct
{
Adjlist vertices; //
int vernum, arcnum; //
}ALGraph;
//
int LocateVer(ALGraph G, char u)
{
int i;
for(i = 0; i < G.vernum; i++)
{
if(u == G.vertices[i].data)
return i;
}
if(i == G.vernum)
{
printf("Error u!
");
exit(1);
}
return 0;
}
//
void CreateALGraph(ALGraph &G)
{
int i, j, k, w;
char v1, v2;
ArcNode * p;
printf(" : ");
scanf("%d %d", &G.vernum, &G.arcnum);
printf(" !
");
for(i = 0; i < G.vernum; i++)
{
printf(" %d :
", i);
fflush(stdin);
scanf("%c", &G.vertices[i].data);
G.vertices[i].firstarc = NULL;
G.vertices[i].indegree = 0;
}
for(k = 0; k < G.arcnum; k++)
{
printf(" (v1, v2, w):
");
//
fflush(stdin);
scanf("%c %c %d", &v1, &v2, &w);
i = LocateVer(G, v1);
j = LocateVer(G, v2);
p = (ArcNode *)malloc(sizeof(ArcNode));
p->adjvex = j;
p->info = w;
p->nextarc = G.vertices[i].firstarc;
G.vertices[i].firstarc = p;
G.vertices[j].indegree++; //vi->vj, vj 1
}
return;
}
//
void CriticalPath(ALGraph G)
{
int i, k, e, l;
int * Ve, * Vl;
ArcNode * p;
//*****************************************
//
//*****************************************
Ve = new int [G.vernum];
Vl = new int [G.vernum];
for(i = 0; i < G.vernum; i++) //
Ve[i] = 0;
for(i = 0; i < G.vernum; i++)
{
ArcNode * p = G.vertices[i].firstarc;
while(p != NULL)
{
k = p->adjvex;
if(Ve[i] + p->info > Ve[k])
Ve[k] = Ve[i]+p->info;
p = p->nextarc;
}
}
//*****************************************
//
//*****************************************
for(i = 0; i < G.vernum; i++)
Vl[i] = Ve[G.vernum-1];
for(i = G.vernum-2; i >= 0; i--) //
{
p = G.vertices[i].firstarc;
while(p != NULL)
{
k = p->adjvex;
if(Vl[k] - p->info < Vl[i])
Vl[i] = Vl[k] - p->info;
p = p->nextarc;
}
}
//******************************************
for(i = 0; i < G.vernum; i++)
{
p = G.vertices[i].firstarc;
while(p != NULL)
{
k = p->adjvex;
e = Ve[i]; // vi
l = Vl[k] - p->info; //
char tag = (e == l) ? '*' : ' '; //
printf("(%c, %c), e = %2d, l = %2d, %c
", G.vertices[i].data, G.vertices[k].data, e, l, tag);
p = p->nextarc;
}
}
delete [] Ve;
delete [] Vl;
}
void main()
{
ALGraph G;
printf(" 。
");
CreateALGraph(G);
CriticalPath(G);
}