A practical bounding algorithm for computing two-terminal reliability based ...

A practical bounding algorithm for computing two-terminal reliability based on decomposition technique

  • Yi-feng Niu, Fang-Ming Shao
  • Computers and Mathematics with Applications 2011

概要

  • 2端子信頼性計算のアルゴリズム
  • 実験なし
  • (某イベントで知った)

提案手法

  • C: 事象の集合
    • 事象=各辺の状態
  • A1(C): Cでの状態が生の辺集合
  • A2(C): Cでの状態が死の辺集合
  • A1(C)がs-t経路を構成→必ず到達可能
  • A2(C)がs-tカットを構成→必ず到達不可能
  • 良く分からない(必ず到達可能でも不可能でもない)Cがある時に、イイ感じに再帰したい
    • AM={x1,x2,…,xq}: AM∪A1(C)がs-t経路を構成する辺集合
      • A1(C)とA2(C)には含まれない
    • AMを元にCを下のように分割
      $$x_1$$ $$x_2$$ $$x_3$$ $$\cdots$$ $$x_{q-1}$$ $$x_q$$
      $$C^1$$ 0 * * $$\cdots$$ * *
      $$C^2$$ 1 0 * $$\cdots$$ * *
      $$C^{q-1}$$ 1 1 1 $$\cdots$$ 0 *
      $$C^q$$ 1 1 1 $$\cdots$$ 1 0
      $$C^0$$ 1 1 1 $$\cdots$$ 1 1
    • AMが最小なら、C^0だけがs-t経路を構成する
      • 具体的には、A1(C)を縮約、A2(C)を削除したグラフでの最短路で良い
    • 他は、1を縮約、0を削除して再帰
  • これは厳密計算、Pr[C]<εだったら省略して高速化
  1. rec(C)
  2. If Cが到達不可能: Y←Y+C、終了
  3. If Pr[C]<ε: Z←Z+C、終了
  4. AMを探索
  5. AMを元に、Cを$$C^1, C^2, \ldots, C^q, C^0$$に分解
  6. X←X+C0
  7. $$ \textsf{LB}=\sum_{c \in X} \Pr[c] $$
  8. $$ \textsf{UB}=1-\sum_{c \in Y} \Pr[c] $$

まとめ

  • 古典的な手法に見えるが、最短路を使う所がそうではないんだろうか…。

uncertain graphs ネットワーク信頼性

2015/12/27

最終更新:2015年12月27日 03:47