一種新的生成樹組隨機求取算法

董張卓，羅 輝，齊 洋

(1.西安石油大學(xué) 電子工程學(xué)院，陜西 西安 710065； 2.西安科技大學(xué) 電氣與控制工程學(xué)院，陜西 西安 710054)

引 言

在電力[1-2]、通信、管網(wǎng)、公路網(wǎng)、醫(yī)療[3-4]等實際問題以及優(yōu)化設(shè)計中，通過一定方法將問題等效成一個平面圖，用不包括環(huán)路能達到每一個節(jié)點的連通圖，即對圖的生成樹的求解[5]，得到工程問題的可行解是一個典型的方法。

此類問題均可歸為針對無向圖和有向圖求生成樹的問題，求解該類問題目前有數(shù)種方法。第一種方法是BST算法[6]，用子樹集的概念從空集出發(fā)，按節(jié)點的編號順序，逐一向集合中添加至少在有向圖G的一顆以r為根的生成樹上的支路，直至得到該圖的某個生成樹為止。第二種方法是在G-M算法[7]的基礎(chǔ)上，從根出發(fā)，找到以r為根的圖G的每棵生成樹中都存在的支路e，確定搜索時間和搜索空間后，采用基于深度優(yōu)先搜索方法[8]得到生成樹，提高方法的運行效率。第三種方法是給有向圖賦權(quán)后以權(quán)值為參考生成最小生成樹[1]。

以上算法僅適用于求解節(jié)點數(shù)和支路數(shù)較少的圖的生成樹，且隨著圖的規(guī)模增大，求解效率逐漸變低，同時，這些算法一般應(yīng)用于求解一棵生成樹，并不適合于求解一組生成樹。為此，本文提出一種基于簡化圖的生成樹算法。為了減小問題的規(guī)模，首先定義簡化規(guī)則將圖進行簡化，在簡化圖的基礎(chǔ)上，提出一種隨機生成樹組求解算法得到生成樹的集合，即建立一種通過對原圖和對應(yīng)的樹圖通過輪盤賭的方式隨機選擇支路進行遷移的算法，生成連通圖。通過多次應(yīng)用生成樹計算方法，生成不同的樹，得到生成樹組。

1 生成樹計算模型

定義1 大規(guī)模復(fù)雜連通圖GF∷=，其中BF為支路集合，NF為節(jié)點集合。

計算連通圖GF的生成樹組時，為了減小生成樹的計算量，首先對不涉及到生成樹的支路圖部分進行簡化得到簡化圖，針對簡化圖G計算得到的生成樹組加上簡化的部分即為原連通圖的樹組。不失一般性，在圖的簡化過程中，只給出簡化方法；計算過程中，只針對簡化圖進行計算。

1.1 復(fù)雜連通圖的簡化

為了減小復(fù)雜圖的規(guī)模，對其進行簡化得到簡化圖。將圖中不涉及環(huán)路的輻射支路、節(jié)點以及直接串聯(lián)的支路進行化簡。為此給出以下概念的定義：

定義2 輻射通路，不包含在任何環(huán)路中的通路稱為輻射通路；

定義3 互斥支路，由度為2的節(jié)點連接的兩條支路稱為互斥支路。

定義4 互斥支路集，集合{bi|i=1,2，…，nb}，若bi和bi+1互斥，且bi+1和bi+2互斥，i=1,2，…，nb-2，稱集合為互斥支路集

輻射通路不存在于任何環(huán)路中，所以不參與生成樹的生成過程。同時由定義3知，互斥支路集在求取開環(huán)圖時最多只需打開一條支路。因此，將互斥支路進行合并。故根據(jù)圖論的相關(guān)概念和上述定義，給出復(fù)雜圖的簡化規(guī)則：①刪除復(fù)雜圖中所有輻射通路；②將復(fù)雜圖中的互斥支路集等效為一條支路。

1.2 簡化圖生成樹算法

1.2.1 過渡圖的定義

定義5 簡化圖，圖G為圖GF經(jīng)過簡化后得到的圖：

G∷=。

(1)

其中：B為圖中的支路集合，B={bi|i=1,2，…，nb}，bi為圖中支路的編號，nb為圖中支路個數(shù)，N為圖中的節(jié)點集合，N={ni|i=1,2，…，nn}，ni為圖中節(jié)點的編號，nn為圖中節(jié)點個數(shù)。

定義6 生成樹圖GT，圖G的生成樹定義為含有圖G所有節(jié)點連通的無環(huán)路的一個子圖：

GT∷=。

(2)

其中：BT為圖中的支路集合，BT={bTi|i=1,2，…，nTb}，bTi為支路的編號，nTb為生成樹中支路個數(shù)；NT為圖中的節(jié)點集合NT={nTi|i=1,2，…，nTn}，nTi為節(jié)點的編號，nTn為生成樹節(jié)點個數(shù)。

定義7 過渡圖GB，生成樹圖過程中的一個臨時圖，初始時由簡化圖G生成，完全等值于簡化圖G，按照算法生成樹的過程中，逐漸遷出一些支路，完成生成樹計算后，圖GB中為圖G的連支，

GB∷=。

(3)

其中：BB為圖中的支路集合；NB為圖中的節(jié)點集合。

1.2.2 生成樹組樹支未選中概率

為保證生成樹組計算過程中樹的多樣性，以及考慮生成樹組在后期計算過程中效率降低問題，在第一次計算完成得到第一個生成樹后，對化簡圖G以及過渡圖GB的支路加入選中作為樹支的計數(shù)值iNoc_T，即某一支路在一棵生成樹中出現(xiàn)一次，該支路的計數(shù)值iNoc_T+1，當(dāng)計算完成的樹的總數(shù)為iTn_T時，某條支路作為樹支的概率為

(4)

則支路未選中作為樹支的概率

Pn_t=1-Pt。

(5)

1.2.3 隨機生成樹計算原理

一顆隨機生成樹的計算過程分為3個部分，初始化部分，支路遷移循環(huán)部分、線索支路搜索部分。

初始化部分：過渡圖GB的生成、生成樹圖GT初始化以及在生成樹計算過程中記錄當(dāng)前支路和當(dāng)前處理節(jié)點的變量的定義。過渡圖GB初始化為原圖G，生成樹圖GT的支路集合和節(jié)點集合為空集。在圖GB中用輪盤賭算法隨機選擇的一條支路bk，取支路bk關(guān)聯(lián)的節(jié)點j。在圖GB中移除bk,圖GT中添加支路bk及支路兩端的節(jié)點i,j，即圖GT的BT={bk},NT={i,j},當(dāng)前節(jié)點C_n=j。

支路遷移循環(huán)部分：在圖GB以當(dāng)前節(jié)點C_n為線索，得到其關(guān)聯(lián)的支路集Bsel={bj|j=1,2,…,nb}，用輪盤賭算法隨機從支路集Bsel中選中一條支路bk，得到其對端節(jié)點j,如果j?NT,C_b=bk，C_n=j,圖GB中移除C_b=bk,圖GT中添加支路C_b、節(jié)點C_j，重開始支路遷移部分；否則，轉(zhuǎn)執(zhí)行線索支路搜索。

線索支路搜索部分：遍歷GB中支路，取支路bk的對應(yīng)節(jié)點i,j，如果i?NT∨j?NT成立，得到C_b=bk，C_n=i?NTi:j,轉(zhuǎn)支路遷移循環(huán),否則，計算完成。

在每次計算得到新的生成樹后，更新圖G中支路計數(shù)值iNoc_T以及生成樹數(shù)目iTn_T，并在下一次生成樹的計算過程中以Pn_t為基準(zhǔn)采用輪盤賭的方式對當(dāng)前節(jié)點的待選支路集中的支路進行選擇。

1.2.4 隨機生成樹組的形成

為了得到一組完全的生成樹，需多次應(yīng)用上述隨機生成樹算法形成生成樹組。將得到的生成樹存入生成樹組時，將支路按序號從小到大排序，逐一對已有生成樹方案中的支路進行對比，判別該生成樹是否與已有的方案相同，若相同，移除該方案并重新生成新的生成樹；若不同，則存入生成樹組。

2 隨機生成樹算法實現(xiàn)

以圖1為例，包含28個節(jié)點和32條支路，對隨機生成樹計算過程進行說明，給出隨機生成樹的計算方法。

圖1 復(fù)雜無向連通圖Fig.1 Complex undirected connected graph

2.1 簡化過程

按照上述簡化規(guī)則對該圖進行簡化得對應(yīng)的簡化圖圖2。

圖2 復(fù)雜圖對應(yīng)的簡化圖Fig.2 Simplified graph corresponding to complex graph

2.2 隨機生成樹計算過程

以圖2所示化簡圖為例，進行生成樹的計算過程說明，過程如圖3所示。

圖3 生成樹生成過程圖Fig.3 Generation process of spanning tree

2.3 算法過程中節(jié)點與支路的數(shù)據(jù)表示

根據(jù)圖的特點，使用關(guān)系表的形式描述節(jié)點和支路的連接關(guān)系，見表1。

表1 節(jié)點與支路的連接關(guān)系表Tab.1 Connection relationship between nodes and branches

數(shù)組A分3個域：A1域為節(jié)點編號，A2域、A3域分別為節(jié)點度和節(jié)點連接的支路的編號序列。

將等效后的支路與等效前的支路進行對應(yīng)，對應(yīng)關(guān)系見表2。

表2 支路與互斥支路集的對應(yīng)關(guān)系表Tab.2 Correspondence between branch and mutually exclusive branch set

B的元素分2個域：B1域為簡化圖中支路編號，B2域為復(fù)雜圖中對應(yīng)的互斥支路組中的支路編號。表3即為復(fù)雜圖1中互斥支路集與簡化圖2中支路的對應(yīng)關(guān)系表。

表3 支路與互斥支路組對應(yīng)表Tab.3 Correspondence between branches and mutually exclusive branch sets

在圖GB中的支路屬性中，加入一個選中為樹支的計數(shù)器，用來記錄支路選中為樹支的次數(shù)。生成樹組的存貯采用結(jié)構(gòu)見表4。

表4 生成樹的支路對應(yīng)關(guān)系表Tab.4 Correspondence among branches of spanning tree

數(shù)組C分3個域：C1域為樹的編號，C2域、C3域分別為支路的編號和樹支的編號序列。

2.4 隨機生成樹組計算過程

隨機生成樹組計算步驟及流程如圖4所示。

步驟1：初始化圖G中各支路的未選中計數(shù)值iNoc_T=0，樹個數(shù)iTn_T=0。

步驟2：初始化建立GT

(1)建立支路和節(jié)點集合BT={}，NT={}；建立當(dāng)前支路變量C_b,以及當(dāng)前節(jié)點變量C_n。

(2)隨機選取圖GB中支路BB中的一條支路bk，得到支路兩端的節(jié)點i,j，圖GT中添加支路bk，及支路兩端的節(jié)點，即圖GT的BT={bk},NT={i,j}。

(3)從GB中將支路bk移除，BB=BB-{bk}。

(4)C_b=bk，C_n=j。

步驟3：對當(dāng)前節(jié)點、以及當(dāng)前支路的處理。

(1)從圖GB中，得到當(dāng)前節(jié)點C_n連接的支

路集合Bsel,如果Bsel=?，轉(zhuǎn)(6)。

(2)基于Pn_t采用輪盤賭的方式從Bsel中選擇一條支路bk，(a)得到bk對應(yīng)另一側(cè)節(jié)點j,判斷節(jié)點j?NT，即不為GT的節(jié)點，轉(zhuǎn)(3)。否則Bsel=Bsel-{bk}并隨機選取一支路bk，為空轉(zhuǎn)(6)，否則轉(zhuǎn)(a)。

(3)C_b=bk，C_n=j。

(4)GT中加入bk，即BT=BT+bk}，NT=NT+j}。

(5)GB中移除支路bk，即BB=B-{bk}，轉(zhuǎn)(1)。

(6)遍歷GB中支路，取支路bk節(jié)點i,j，如果i?NT∨j?NT成立，得到C_b=bk，C_n=i?NTi:j,轉(zhuǎn)(1),否則，轉(zhuǎn)步驟3。

步驟4：輸出GB,GT中支路集合BB、BT。

圖4 隨機生成樹算法流程圖Fig.4 Flow chart of random spanning tree algorithm

步驟5：判別新生成的生成樹GT成與生成樹組中已有的生成樹是否相同，相同轉(zhuǎn)步驟1，不相同則存入生成樹組，同時圖G更新支路計數(shù)值iNoc_T++；樹個數(shù)iTn_T++。

步驟6：判斷是否達到設(shè)定循環(huán)次數(shù)，即生成樹的個數(shù)iTn_T是否達到設(shè)定的值，若達到則退出運行，否則，轉(zhuǎn)步驟2。

3 算 例

在VS2015平臺下用VC++編制了提出的生成樹算法，分別用圖1中的復(fù)雜圖和圖7中的PG & E69節(jié)點電力系統(tǒng)圖為例對提出的算法進行了驗證。

3.1 算例1

對圖1中的復(fù)雜圖簡化后得簡化圖2，對簡化圖2中的節(jié)點和支路進行分類并處理，使用文中提出的方法共生成291個簡化圖對應(yīng)生成樹圖，表5為圖的生成樹連支組(僅列出10組)；生成2 227個圖1對應(yīng)生成樹，表6為復(fù)雜圖的生成樹連支組(僅列出10組)。

表5 簡化圖生成樹對應(yīng)連支組Tab.5 Connected branch group corresponding to spanning tree of simplified graph

從表5結(jié)果可以看出，本文中方法可以生成簡化圖對應(yīng)的生成樹圖，方法正確有效。圖5為簡化圖2斷開支路集{2,4,7,8,9}得到的一個生成樹圖。

圖5 簡化圖2對應(yīng)的一種生成樹圖Fig.5 A spanning tree graph corresponding to simplified graph in Fig.2

針對圖5中的生成樹圖逆用簡化規(guī)則，將簡化圖中斷開的支路對應(yīng)的互斥支路集任一支路打開，并將刪除得輻射式支路重新添加即可得復(fù)雜圖對應(yīng)的生成樹圖。圖6為圖1中復(fù)雜圖斷開支路集{4,12,25,23,27}得到的一個生成樹圖，表6為復(fù)雜圖1對應(yīng)生成樹的結(jié)果。

圖6 復(fù)雜圖1對應(yīng)的一種生成樹圖Fig.6 A spanning tree graph corresponding to complex graph in Fig.1

表6 復(fù)雜圖1的生成樹對應(yīng)連支組Tab.6 Connected branch group corresponding to spanning tree of complex graph in Fig.1

從表6中結(jié)果和圖6可以看出，本文中方法可以生成復(fù)雜圖對應(yīng)的生成樹，方法正確有效。

3.2 算例2

圖7為PG & E69節(jié)點電力系統(tǒng)圖，包含支路73條，節(jié)點69個。

對圖7中的圖簡化后進行生成樹組的計算，共生成6 296組對應(yīng)的生成樹圖。圖7的生成樹連支組見表7(僅列出10組)。如圖8所示，列出圖7對應(yīng)的一種生成樹圖。

表7 69節(jié)點系統(tǒng)生成樹對應(yīng)連支組Tab.7 Connected branch groups corresponding to 69 node system spanning tree

圖8 PG & E69節(jié)點系統(tǒng)圖對應(yīng)生成樹圖Fig.8 Spanning tree graph corresponding to PG & E69 node system diagram

從表7中結(jié)果和圖8可以看出，本文中方法可以正確有效地生成重構(gòu)可行解圖。

3.3 方法性能對比

在相同的連通性判斷方法下，分別采用本文中方法和文獻[2]的BST算法對圖1和圖7生成500棵生成樹。平均生成一棵生成樹計算時間見表8。

表8 同一算例下不同方法平均計算時間對比Tab.8 Average calculation time of the same example using different methods

從表8可知：針對包含28個節(jié)點和32條支路的圖1，本文方法的平均計算時間為0.57 ms，文獻[2]中的BST算法平均計算時間為8.43 ms,本文方法計算效率為BST算法的14.79倍。針對包含支路73條，節(jié)點69個的PG & E69節(jié)點電力系統(tǒng)圖，本文方法的平均計算時間為1.46 ms，文獻[2]中的BST算法平均計算時間為34.90 ms,本文方法計算效率為BST算法的23.90倍。且隨著圖的規(guī)模增加，優(yōu)勢愈發(fā)明顯。

4 結(jié) 論

本文對復(fù)雜連通圖中得到生成樹的算法進行了研究。將復(fù)雜圖按照簡化規(guī)則簡化后得到簡化圖。在簡化圖的基礎(chǔ)上，利用提出的生成樹算法得到對應(yīng)的生成樹圖，進而生成復(fù)雜圖對應(yīng)的生成樹圖。算例表明，方法具有以下特點：

(1)該方法可正確生成復(fù)雜連通圖對應(yīng)的簡化圖。

(2)該方法針對簡化單圖后可正確地、快速地求其所有的對應(yīng)生成樹圖。

(3)針對簡化圖對應(yīng)生成樹圖，可逆向使用簡化規(guī)則得到復(fù)雜圖對應(yīng)的所有生成樹圖。

(4)該方法相比其他方法，能大幅度提高復(fù)雜圖對應(yīng)生成樹搜尋過程中的速度，且隨著連通圖規(guī)模的增大，該優(yōu)勢越發(fā)明顯。