一種有向概率圖連通性仿真算法＊

馬 睿 朱建沖

（海軍工程大學管理工程系 武漢 430033）

1 引言

圖論是一門很有實用價值的學科，近年來它受計算機科學蓬勃發展的刺激，發展極其迅速，應用范圍不斷拓廣，已滲透到諸如運籌學、邏輯學、物理學、以及數學的其它分支中[1]。特別在運籌學中，在系統效能評估[2]、故障診斷[3]、系統可靠性分析[4]、路徑優化[5]等方面均扮演著重要的角色。圖的連通性是圖論里的一個重要問題，許多人對圖的連通性算法進行了研究。陸鳴盛[6]等提出一種改進的蒙特卡羅法對圖的連通性進行分析，由于蒙特卡羅法是一種隨機抽樣算法，其精度取決于采樣的數量，當網絡規模較大結構復雜時，采樣數量十分龐大，并且計算精度受到影響。厲海濤[7]等總結了貝葉斯網絡推理的一些方法，黃晶[8]等創造性地將貝葉斯網絡應用于路網失效的評估中，尹洪英[9]等使用貝葉斯網絡對公路網脆弱性路段的識別進行了研究。上述基于貝葉斯網的連通性研究具有理論上的嚴格性和一致性，然而也存在許多不足，如處理多連通問題方法復雜，采用條件概率數據之間存在依賴性等。本文提出一種計算圖連通性的精確方法，圖上各條邊的連通性是相互獨立的，適用于多連通問題的分析。由于是精確計算，避免了近似計算中數量龐大的采樣運算，并且可以直接得出各條邊不連通時整個網絡連通的概率以及靈敏度分析結果。

2 基本理論與思路

2.1 基本理論

分析有向圖的連通性，首先要找到連接指定起始點的最小路集合。鄰接終點矩陣法[10]是求最小路集合的有效方法。在已知各條邊連通概率、整個網絡連通概率以及當各條邊失效時網絡連通概率的基礎上，根據貝葉斯概率公式可以求得網絡不連通時各邊失效概率。

2.2 算法思路

圖1 有向概率圖結構1

假設一個由3條邊組成的有向概率圖如圖1所示。

邊1、2、3連通的概率分別為0.6、0.7、0.8，各邊連通情況與路AB連通情況關系及概率如表1，其中1代表連通，0代表不連通。

表1 各邊連通情況與路AB連通情況關系及概率

AB連通的概率為P＝（P1＋P3＋P5）／（P1＋P2＋P3＋P4＋P5＋P6＋P7＋P8）＝0.704

GENIE是匹茲堡大學開發的一款計算概率圖的軟件，可根據上述算法思想進行網絡連通性分析。本文的算法首先通過用MATLAB編程，對有向概率圖進行初步計算，將所得中間結果輸入到GENIE中，就可以對有向概率圖的連通性進行比較全面而且精確的分析。

3 仿真算法

3.1 編碼方案

3.1.1 最小路集矩陣S

對于一個有n條邊、m條最小路的最小路集合，產生m條長度為n的0－1編碼，每條編碼中1的位置表示該條最小路上包含該條邊，否則該位置為0，從而產生一個元素值為0或1的最小路集合矩陣。例如，對于最小路集合[R1R4，R2R5，R1R3R5]，其最小路集合矩陣為：

3.1.2 網絡連通分布碼t

對于有n條邊的最小路集合，產生一個長度為2n的0－1數組，每一位數字代表了n條邊通斷情況下整個網絡的通斷情況，0為不連通，1為連通。稱該數組為該最小路集合的網絡連通分布碼。最小路集合[R1R4，R2R5，R1R3R5]的網絡連通分布碼如圖2所示。

圖2 網絡連通分布碼

3.2 步驟與實現

3.2.1 步驟

1）使用鄰接終點矩陣法求有向概率圖的最小路集矩陣。

2）使用MATLAB編程，以最小路集矩陣為輸入，計算最小路集中各個邊通斷情況下整個網絡連通的情況即網絡連通分布碼t。

3）將步驟2）中的網絡連通分布碼輸入GENIE軟件，得到整個網絡連通的概率以及各個邊失效時整個網絡失效的概率。

4）根據步驟3）的結果，結合條件概率公式（貝葉斯公式），計算整個網絡失效時各邊失效的概率。

5）進行靈敏度分析。

3.2.2 計算網絡連通分布碼t的MATLAB流程

圖3 計算網絡連通分布碼的流程

下面結合計算流程框圖對其基本執行過程給出詳細解釋：

Step1：將最小路集合矩陣S（S為m×n矩陣）作為初始條件輸入程序；

Step2：對于第i條最小路，將最小路矩陣第i行中值為1的元素的下標存入數組K；

Step3：對于數組K的第j個元素，產生一個長度為2n，周期為2（n－K（j）＋1）的1－0數組r（j）；

Step4：判斷是否對數組K的所有元素都進行了Step3的計算，如果是進入Step5，否則返回Step3；

Step5：將得到的第i行所有值為1的元素的r（j）進行與運算，得到第i條最小路的網絡連通分布子碼l（i）；

Step6：判斷是否對全部的最小路都計算了l（i），是則進入Step7，否則返回Step2；

Step7：對全部最小路的網絡連通分布子碼l（i）進行或運算，得到網絡連通分布碼t。

4 算例

在CPU為Pentium1.6G，內存1G的計算機平臺上分析本文的算法。

圖4 有向概率圖結構2

一個由5個點7條邊組成的有向概率圖，結構如圖4所示。

各邊的失效概率如表2所示。

表2 各邊失效概率

A到B的最小路有3條，分別是[R1，R4]，[R2，R6]，[R1，R3，R6]，表示為最小路矩陣：

將最小路集矩陣SAB輸入到MATLAB程序，計算得到：

tAB＝[1 1 1 0 1 1 1 0 1 1 1 0 1 1 0 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0]，用時0.113s。

A到C的最小路有3條，分別是[R1，R5]，[R2，R7]，[R1，R3，R7]，表示為最小路矩陣：

將最小路集矩陣SAC輸入到MATLAB程序，計算得到：

tAC＝[1 1 1 0 1 1 1 0 1 1 1 0 1 1 0 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0]，用時0.105s。

A到B和A到C同時連通的情況有9種，分別是：

[R1，R4，R5]，[R1，R2，R4，R7]，[R1，R3，R4，R7]，[R1，R2，R5，R6]，[R2，R6，R7]，[R1，R2，R3，R6，R7]，[R1，R3，R5，R6]，[R1，R2，R3，R6，R7]，[R1，R3，R6，R7]，表示為最小路矩陣：

將最小路集矩陣S輸入到MATLAB程序，計算得到：

t＝[111111101100110011111010110010001111111 0110011001111000000000000100010001000100010 0010001000100000000000000000000000000000000000]，用時0.521s。

圖5 網絡連通概率

將7條邊失效的概率以及tAB、tAC、t輸入到GENIE2.0得到結果如下：

1）A到B連通的概率為0.986613，A到C連通的概率為0.986915，A到B、C同時連通的概率為0.978761。

2）各邊失效時網絡連通概率

將R1設置為證據變量可以得到當R1失效時A到B，A到C及A到B、C連通的概率。

圖6 R1失效時網絡連通概率

同理可得到R2、R3、R4、R5、R6、R7失效時網絡的連通概率，結果如表3所示。

3）根據貝葉斯公式，計算A與B、C不能同時連通時，各條邊失效的概率，結果如表4所示。

表3 各邊失效時網絡連通概率

表4 網絡不連通時各邊失效的概率

4）靈敏度分析

給R1一個擾動使其連通概率在0.88，0.92，0.96三種情況間變動得到靈敏度分析結果如下：

圖7 R1靈敏度分析結果

在R1連通概率為0.96，0.92，0.88的情況下R，RAB，RAC連通概率如表5所示。

表5 R1靈敏度分析結果

結果表明該方法精度準確，運算速度快，適用于復雜結構的有向概率圖連通性分析。

5 結語

圖論中的網絡連通性具有重要的研究價值，當前對網絡連通性的分析方法大多側重于近似計算和基于條件概率的因果推理。本文從網絡的基本結構出發，提出一種網絡連通性的仿真算法，該算法具有計算結果精確、計算數據相互獨立的特點，適用于結構復雜的網絡系統，可以計算出證據變量的后驗概率并進行靈敏度分析，對網絡連通性的分析比較全面。

[1]卜月華，吳建專，顧國華，等.圖論及其應用[M].南京：東南大學出版社，2000：1～3

[2]秦前付，曹存根，徐洸.基于圖論的作戰計劃軍事效果評估[J].計算機科學，2005，32（7）：148～151

[3]王寶龍，徐赫，蘇林，等.圖論方法在裝備測試與診斷信息建模中的應用[J].彈箭與制導學報，2008，28（4）：241～244

[4]束洪春，劉宗兵，朱文濤.基于圖論的復雜配電網可靠性評估方法[J].電網技術，2006，30（21）：46～49

[5]王朋振，張長根，孔凡成，等.軍品配送網絡優化方法的比較研究[J].物流技術，2010（Z1）：209～211

[6]陸鳴盛，沈成康.圖的連通性快速算法[J].同濟大學學報，2001，29（4）：436～439

[7]厲海濤，金光，周經倫，等.貝葉斯網絡推理算法綜述[J].系統工程與電子技術，2008，30（5）：935～939

[8]黃晶，徐麗群.基于貝葉斯網絡的路網失效程度評估方法研究[J].科學技術與工程，2010，10（9）：2127～2133

[9]尹洪英，徐麗群.基于貝葉斯網絡的路網脆弱路段識別模型[J].系統管理學報，2010，19（6）：656～661

[10]袁亞華，王自果.最小路集的鄰接終點矩陣算法[J].西北工業大學學報，1989，7（4）：473～477