データ構造-図-キーパス

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
    五、肝心なところと肝心な経路を求める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