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経路を構成する辺集合
-
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]<εだったら省略して高速化
-
rec(C)
-
If Cが到達不可能: Y←Y+C、終了
-
If Pr[C]<ε: Z←Z+C、終了
-
AMを探索
-
AMを元に、Cを$$C^1, C^2, \ldots, C^q, C^0$$に分解
-
X←X+C0
-
$$ \textsf{LB}=\sum_{c \in X} \Pr[c] $$
-
$$ \textsf{UB}=1-\sum_{c \in Y} \Pr[c] $$
まとめ
-
古典的な手法に見えるが、最短路を使う所がそうではないんだろうか…。
uncertain graphs ネットワーク信頼性
2015/12/27
最終更新:2015年12月27日 03:47