データ構造-図-キーパス
1876 ワード
githubアドレス:https://github.com/arkulo56/thought/blob/master/software/dataStruct/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84_%E 5%9 B%BE_%E 5%85%B 3%E 9%94%AE%E 8%A 7%E 5%BE%84.md
データ構造図のキーパス
AOVネットワーク:図があり、頂点で活動を表し、弧で活動の先着順AOEネットワークを表します.図があり、頂点でイベントを表し、弧で活動を表し、活動の消費時間を表します.
名詞の解釈
活動:ビジネスロジック中の行為は、イベントの結果またはトリガ条件の重要なパスを表します.最大パス長(重み)を持つパスは、一つ以上の可能性があります.
活動の2つの属性:e(i)最初の開始時間、l(i)最後の開始時間イベントの2つの属性:ve(j)最初の開始時間、vl(j)最後の開始時間
原理:は、まず各頂点のveとvl値 を求めます.は、この2つの値を通じて、各辺のeとlの値を求めることができる. がe(i)=l(i)の辺を取るのは だけではない.
一、求ve(j)の値前から後ろに向かって、直接前駆ノードのve値+現在ノードの辺の権利値(可能性がある複数の条、最大値をとる) 最初の頂点のveは0 に等しい.
下表は各頂点(イベント)のve値です.
頂点
v 1
v 2
v 3
v 4
v 5
v 6
v 7
ve(j)
0
3
2
6
7
5
10
二、vl(j)の値を求める.は、後から前に向かって、直接にノードのvl値を後継する.現在のノードのエッジの権利値(可能性があり、最小値をとる) .終了点のvlはそのveに等しいです.
頂点
v 1
v 2
v 3
v 4
v 5
v 6
v 7
vl(j)
0
3
3
6
7
6
10
三、e(i)の値を求める
e(i):活動aiは弧によって表されるので、活動の最初の開始時間はイベントvkの最初の発生時間と同じであるべきで、e(i)=ve(k)があります.
a 1(3)
a 2(6)
a 3(2)
a 4(4)
a 5(2)
a 6(1)
a 7(3)
a 8(1)
a 9(3)
a 10(4)
e(i)
0
0
0
3
3
2
2
6
7
5
四、l(i)の値を求める
l(i):活動aiは弧によって表されるので、aiの最終的な発生時間はvjの遅発時間を延長しないようにします.したがって、l(i)=vl(i)-len、すなわち、活動が頂点に達する最も遅い発生時間は、エッジの重みを減算する.
辺
a 1(3)
a 2(6)
a 3(2)
a 4(4)
a 5(2)
a 6(1)
a 7(3)
a 8(1)
a 9(3)
a 10(4)
l(i)
0
0
1
3
4
5
3
6
7
6
五、肝心なところと肝心な経路を求める
a 1 a 2 a 4 a 8 a 9
a 1->a 4->a 9とa 2->a 8->a 9
データ構造図のキーパス
AOVネットワーク:図があり、頂点で活動を表し、弧で活動の先着順AOEネットワークを表します.図があり、頂点でイベントを表し、弧で活動を表し、活動の消費時間を表します.
名詞の解釈
活動:ビジネスロジック中の行為は、イベントの結果またはトリガ条件の重要なパスを表します.最大パス長(重み)を持つパスは、一つ以上の可能性があります.
活動の2つの属性:e(i)最初の開始時間、l(i)最後の開始時間イベントの2つの属性:ve(j)最初の開始時間、vl(j)最後の開始時間
,
重要な経路を計算するプロセス原理:
であり、キーパスは一つの一、求ve(j)の値
下表は各頂点(イベント)のve値です.
頂点
v 1
v 2
v 3
v 4
v 5
v 6
v 7
ve(j)
0
3
2
6
7
5
10
二、vl(j)の値を求める.
頂点
v 1
v 2
v 3
v 4
v 5
v 6
v 7
vl(j)
0
3
3
6
7
6
10
三、e(i)の値を求める
e(i):活動aiは弧によって表されるので、活動の最初の開始時間はイベントvkの最初の発生時間と同じであるべきで、e(i)=ve(k)があります.
( ) ( )
辺a 1(3)
a 2(6)
a 3(2)
a 4(4)
a 5(2)
a 6(1)
a 7(3)
a 8(1)
a 9(3)
a 10(4)
e(i)
0
0
0
3
3
2
2
6
7
5
四、l(i)の値を求める
l(i):活動aiは弧によって表されるので、aiの最終的な発生時間はvjの遅発時間を延長しないようにします.したがって、l(i)=vl(i)-len、すなわち、活動が頂点に達する最も遅い発生時間は、エッジの重みを減算する.
辺
a 1(3)
a 2(6)
a 3(2)
a 4(4)
a 5(2)
a 6(1)
a 7(3)
a 8(1)
a 9(3)
a 10(4)
l(i)
0
0
1
3
4
5
3
6
7
6
五、肝心なところと肝心な経路を求める
e(i)==l(i)
:a 1 a 2 a 4 a 8 a 9
:a 1->a 4->a 9とa 2->a 8->a 9