潘竹生， 李聞白， 林飛龍

(1.浙江師范大學 數(shù)學與計算機科學學院,浙江 金華 321004;2.浙江師范大學 經(jīng)濟與管理學院,浙江 金華 321004)

0 引 言

二元決策圖即BDD(binary decision diagram)及其擴展型在電路驗證[1]、緊湊馬爾可夫鏈表達式[2-4]、編程中對大型元組集的有效處理[5]、符號模型檢驗[6-8]和各種類型系統(tǒng)[9-11]的可靠性分析等領(lǐng)域有著廣泛的應(yīng)用，因此，快速高效地構(gòu)建BDD模型成為最近20年的一個研究熱點，內(nèi)容主要包括變量排序研究和模型構(gòu)建方法研究.

變量排序[12]嚴重影響B(tài)DD模型大小.在極端情況下，不同質(zhì)量的變量排序?qū)?yīng)的BDD模型大小可以跨越幾個數(shù)量級[13].所以，尋找優(yōu)質(zhì)排序是一個非常重要的問題.然而，尋找最優(yōu)排序是一個NP完全問題[13].在實際應(yīng)用中，只能采用啟發(fā)式排序[14-15]策略，如基于廣度優(yōu)先搜索BFS(breadth-first-search)和深度優(yōu)先搜索DFS(depth-first-search)[16-18]的排序.在網(wǎng)絡(luò)可靠性分析領(lǐng)域，文獻[19]指出，對于規(guī)則網(wǎng)絡(luò),BFS策略優(yōu)于DFS.文獻[15,17]指出，對于一般網(wǎng)絡(luò),BFS具有較好性能；就BFS排序策略而言，排序起點對排序結(jié)果有重大影響.文獻[20]指出：1)源點(默認排序起點)一般不是最佳排序起點；2)Square Lattice網(wǎng)絡(luò)的最佳排序起點分布在4個角上.在考慮節(jié)點和邊都可能隨機失效的情況下，文獻[21-22]提出了新的啟發(fā)式排序策略，在規(guī)則網(wǎng)絡(luò)中的大量實驗表明，新的策略優(yōu)于BFS和DFS.文獻[23]針對帶社區(qū)結(jié)構(gòu)的物聯(lián)網(wǎng)，提出帶權(quán)重的BFS和DFS排序.文獻[24]結(jié)合網(wǎng)絡(luò)結(jié)構(gòu)特征提出了一種排序策略選擇方法，用于構(gòu)建精簡BDD模型.文獻[25]重點研究指標數(shù)據(jù)，用于指導設(shè)計排序策略.在模型構(gòu)建方面，Kuo等[15]提出了基于邊擴展圖的自底向上的BDD構(gòu)建方法;Hardy等[17]提出了基于邊界集的自頂向下的BDD構(gòu)建方法.這2種方法適合處理節(jié)點完好的網(wǎng)絡(luò)可靠性分析.在節(jié)點和邊都可能隨機獨立失效時，Pan等[26]提出了基于依賴集的模型構(gòu)建方法;Kawahara 等[27]考慮節(jié)點失效時依賴于該節(jié)點的邊都失效的實際提出了更為高效的BDD構(gòu)建方法;Yeh等[28]提出二叉加法樹(binary addition tree,BAT)算法評估二元狀態(tài)網(wǎng)絡(luò)的可靠性.

最近20年，盡管學界在BDD模型構(gòu)建方法上取得了一些進展，但在啟發(fā)式排序上鮮有成果.本文考慮節(jié)點完好的應(yīng)用場景，從分析基于邊界集的BDD模型構(gòu)建方法入手，分析影響B(tài)DD模型大小的因素，研究排序起點選擇方法和啟發(fā)式排序策略，建立新的啟發(fā)式排序方法.

1 可靠性網(wǎng)絡(luò)和BDD模型

1.1 可靠性網(wǎng)絡(luò)

可靠性網(wǎng)絡(luò)通常表示為一個無向圖G=(V,E,K)，其中V是節(jié)點集，表示網(wǎng)絡(luò)系統(tǒng)中的實體；E是邊集，表示實體之間的連接；K?V是網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(|K|≥2)，表示網(wǎng)絡(luò)中的關(guān)鍵實體,|K|和|V|分別表示關(guān)鍵節(jié)點集K和節(jié)點集V的大小.所謂網(wǎng)絡(luò)可靠性，是指K中節(jié)點能正常通信(如存在一條連通路徑)的可能性.根據(jù)集合K大小的不同，將可靠性網(wǎng)絡(luò)分為3類：2-端可靠性網(wǎng)絡(luò)(|K|=2)、K-端可靠性網(wǎng)絡(luò)(2<|K|<|V|)和All-端可靠性網(wǎng)絡(luò)(|K|=|V|).本文考慮2-端可靠性網(wǎng)絡(luò)，也稱(s,t)網(wǎng)絡(luò)，其中稱s為源點，t為匯點，研究節(jié)點s和t之間的連通性.如圖1所示，其網(wǎng)絡(luò)可表示為G=({s,n1,n2,t}，{e1,e2,e3,e4,e5}，{s,t}).

圖1 橋接網(wǎng)絡(luò)

1.2 BDD模型

在可靠性網(wǎng)絡(luò)中，網(wǎng)絡(luò)可靠性問題可以表示為一個等價的布爾函數(shù).BDD是一個有向無環(huán)圖，通常用來編碼布爾函數(shù).基本編碼規(guī)則如圖2所示，其中x為函數(shù)f的一個布爾變量，表示網(wǎng)絡(luò)中的一個部件，fx=0是x=0時的孩子節(jié)點(記為左孩子)，表示部件失效時的布爾函數(shù)，fx=1是x=1時的孩子節(jié)點(記為右孩子)，表示部件正常工作時的布爾函數(shù).即根據(jù)部件失效與否，函數(shù)f可以表示為f=p·fx=1+(1-p)·fx=0.其中:p表示部件x正常工作時的概率；fx=0和fx=1仍為布爾函數(shù)，可以持續(xù)向下分解，直到所有部件考慮完畢，從而得到最終的BDD模型.

圖2 BDD和布爾函數(shù)f=p·fx=1+(1-p)·fx=0

顯然，在自頂向下的分解過程中，所考慮部件的出現(xiàn)順序可以不同.設(shè)有布爾函數(shù)f=x1x2+x3x4+x5x6，若按部件序x1

(a)低質(zhì)量排序 (b)高質(zhì)量排序

2 基于邊界集的BDD模型構(gòu)建方法

2.1 邊界集和分區(qū)

定義1(邊界集，boundary set) 對于網(wǎng)絡(luò)G=(V,E,K),假設(shè)用邊序o=e1≤e2≤…≤e|E|,ei∈E,i∈[1,|E|]來指導生成BDD模型，|E|表示邊的數(shù)目.當處理第k條邊ek時，對應(yīng)的邊界集Fk可定義為

Fk={v|v是ei和ej的一個公共端點，并且ei∈Ek和ej∈E-Ek}，Ek={e1,e2,…,ek}.

集合Fi中節(jié)點的數(shù)目定義為第i層邊界集的長度，記Fmax為最大邊界集的長度，即

Fmax= max{|Fi|，i= 1,2,3，…,|E|}.

表1 排序o的各層邊界集及邊界集長度

如圖1所示的橋接網(wǎng)絡(luò)，設(shè)有邊序o=e1≤e2≤e3≤e4≤e5，則各層邊界集及邊界集長度如表1所示.因此，最大邊界集長度Fmax為2.

定義2(分區(qū)，partition) 在用BDD編碼網(wǎng)絡(luò)時，需要建立分區(qū)[15]來標記網(wǎng)絡(luò)特征.分區(qū)由若干塊構(gòu)成，塊由邊界集中的節(jié)點構(gòu)成.具體構(gòu)建規(guī)則如下：

1)若邊界集中的2個節(jié)點vi和vj通過已經(jīng)處理的邊能夠連接在一起，則它們在同一塊中，記為[vi，vj]，否則處在不同的塊中，記為[vi][vj]；

2)若某一塊中的節(jié)點通過已經(jīng)處理的邊能夠和至少1個來自集合K的節(jié)點連通，則該塊標記為帶“*”(稱為塊加星操作),如[vi，vj]*表示塊[vi，vj]與集合K中的某點連通.

分區(qū)能有效表征網(wǎng)絡(luò)[15]，如圖1所示網(wǎng)絡(luò)，約定邊序o=e1≤e2≤e3≤e4≤e5.顯然，考慮邊e1時，分區(qū)[s,n1]*和[s]*[n1]有效區(qū)分了e1正常工作和失效這2種狀態(tài)，即表征了對應(yīng)的子網(wǎng)，如圖4所示.另外，利用分區(qū)標識技術(shù)，還可以高效地識別出其中存在的同構(gòu)，如圖4中L2所示，基于分區(qū)[n1,n2]*,[n1]*[n2] 和[n1][n2]*,在邊e3正常工作時，都得到新的分區(qū)[n1,n2]*，識別出了同構(gòu)，這也符合實際.在同一邊序下，分區(qū)相同的2個子網(wǎng)同構(gòu).

圖4 邊界集、分區(qū)和BDD模型生成過程

2.2 BDD模型構(gòu)建

引入分區(qū)后，可以通過操作分區(qū)，在指定邊序的約束下，按自上向下方式一層一層構(gòu)建BDD模型.具體算法如下：

算法1

1)創(chuàng)建BDD模型的根節(jié)點分區(qū)root，初始化為空

2)初始化哈希表hash,用于記錄當前層的所有可能分區(qū),初始化隊列preQueue，curQueue用于存放分區(qū)

3)preQueue.push(root)

4)fork=1 to |E| do

5) while preQueue do

6)Pk=preQueue.pop()

7)tp=genThenPartition(Pk,ek)

8)ep=genElsePartition(Pk,ek)

9) if所有關(guān)鍵點已在tp的一個塊中thenPk.getBDD().then = true

10) else if 有一個關(guān)鍵點被孤立thenPk.getBDD().then = false

11) else

12) iftp不在哈希表hash中 then

13) curQueue.push(tp)

14) hash.put(tp)

15)Pk.getBDD().then=tp.getBDD()

16) if所有關(guān)鍵點已在ep的一個塊中thenPk.getBDD().else = true

17) else if 有一個關(guān)鍵點被孤立thenPk.getBDD().else = false

18) else

19) ifep不在哈希表hash中 then

20) curQueue.push(ep)

21) hash.put(ep)

22)Pk.getBDD().else=ep.getBDD()

23) end while

24) preQueue=curQueue;

25) curQueue.clear()

26)end for

27)return root

如圖1所示的橋接網(wǎng)絡(luò)，約定邊序為e1

第1層，邊為e1=(s,n1)，其中“s”為關(guān)鍵點，邊界集F1={s,n1}.當邊正常工作時，節(jié)點“s”和“n1”合并到一個塊，得分區(qū)[s,n1]*；當邊失效時，節(jié)點“s”和“n1”分屬2個塊，得分區(qū)[s]*[n1].

第2層，邊為e2=(s,n2),由于關(guān)聯(lián)于節(jié)點“s”的邊即將全部處理完成，所以邊界集F2={n1,n2}.考慮第1層分區(qū)[s,n1]*,當邊e2正常工作時，得分區(qū)[n1,n2]*,失效時，得分區(qū)[n1]*[n2];考慮分區(qū)[s]*[n1],當邊e2正常工作時，得分區(qū)[n1][n2]*, 失效時，關(guān)鍵節(jié)點“s”被隔離，所以指向false.

第3層，邊為e3=(1,n2),邊界集F3={n1,n2}.當邊正常工作時，基于第2層的各分區(qū)都生成了相同的分區(qū)[n1,n2]*,所以共享之；當邊失效時，分別指向各自的分區(qū)[n1,n2]*,[n1]*[n2]和[n1][n2]*.

利用相同的規(guī)則，計算邊界集，生成分區(qū)，得到完成的BDD模型.

2.3 BDD模型大小分析

分區(qū)有效表征了網(wǎng)絡(luò)狀態(tài)，如圖4所示，每個網(wǎng)絡(luò)代表一個BDD節(jié)點.因此，計算出分區(qū)的數(shù)目，也就得到了BDD模型的大小.首先從邊界集入手，討論邊界集大小與分區(qū)數(shù)目的關(guān)系.根據(jù)定義2，在給定第i層邊界集Fi和不考慮塊加“*”操作的前提下，包含j個塊的分區(qū)數(shù)目是一個第二類斯特林數(shù)S(|Fi|,j),而包含任意塊數(shù)的分區(qū)總數(shù)是一個貝爾數(shù)B|Fi|.表2列舉了邊界集大小和貝爾數(shù)之間的關(guān)系.

(1)

(2)

表2 邊界集大小、斯特林數(shù)和貝爾數(shù)之間的關(guān)系

顯然，隨著邊界集的增大，貝爾數(shù)急劇增大，且速率遠大于成倍增長速率.若能控制住邊界集大小，就能有效控制住貝爾數(shù).

定義3(BDD寬度W) 設(shè)用Wi表示第i層BDD節(jié)點數(shù)目的最大理論值，則BDD模型的寬度W定義為

(3)

考慮塊加“*”操作.在可靠性網(wǎng)絡(luò)G=(V,E,K)中，由于最多有|K|個關(guān)鍵節(jié)點，所以分區(qū)中最多包含|K|個帶“*”塊.關(guān)鍵節(jié)點單獨成塊時，取得最大值|K|.此時，第i層邊界集Fi所對應(yīng)的分區(qū)數(shù)目，即第i層BDD節(jié)點數(shù)目的最大理論值Wi可以按式(4)計算.

(4)

例如，邊界集F={1,2,3}且|K|=2時的所有可能分區(qū)：[1,2,3],[1,2,3]*,[1,2][3],[1,2]*[3],[1,2][3]*,[1,2]*[3]*,[1,3][2],[1,3]*[2],[1,3][2]*,[1,3]*[2]*,[1][2,3],[1]*[2,3],[1][2,3]*,[1]*[2,3]*,[1][2][3],[1]*[2][3],[1][2]*[3],[1][2][3]*,[1]*[2]*[3],[1]*[2][3]*,[1][2]*[3]*,[1]*[2]*[3]*.

顯然，引入加“*”操作后，分區(qū)總數(shù)目大大增加.

比較式(2)和式(4)，引入帶“*”操作后，隨著邊界集的增大，BDD節(jié)點數(shù)目的最大理論值以更大的速率快速增長.從最大理論值角度看，在排序過程中，越晚引入關(guān)鍵節(jié)點到邊界集就越有利于控制最大理論值.

另一方面，深入研究本文所述BDD模型的生成過程，發(fā)現(xiàn)某一層實際BDD節(jié)點數(shù)目的實際值和已經(jīng)處理的邊數(shù)及網(wǎng)絡(luò)結(jié)構(gòu)特征有關(guān).最好情況，第i層BDD節(jié)點數(shù)為1；最壞情況，第i層BDD節(jié)點數(shù)為2i，如圖5所示.由于同構(gòu)子網(wǎng)的存在及網(wǎng)絡(luò)結(jié)構(gòu)特征的差異，一般情況下，第i層BDD節(jié)點數(shù)目的實際值大于1而小于2i，如圖4所示.所以，如果能找到一種排序,使得每層邊界集足夠小，從而使得BDD節(jié)點數(shù)目最大理論值大大小于該層BDD數(shù)目的最壞情況，那么此排序?qū)且环N優(yōu)秀的排序.

(a)最好情況 (b)最壞情況

3 基于邊界集的啟發(fā)式排序策略

基于邊界集的啟發(fā)式排序采用貪心策略，在排序過程中盡可能優(yōu)先選擇使邊界集足夠小的邊.

3.1 排序策略設(shè)計

根據(jù)本文的BDD模型構(gòu)建方法，第k層分區(qū)以第k-1層分區(qū)為基礎(chǔ)，結(jié)合第k條邊ek在網(wǎng)絡(luò)中的連接情況而建立，即由Fk-1構(gòu)建Fk.為表述方便，設(shè)邊ek的2個端點分別為u和v，根據(jù)u和v在Fk-1和Fk的存在性得邊界集大小變化的所有情況，見表3.

表3 邊界集大小變化

由表3所示，新的邊界集Fk，其大小滿足式(5)，且不失一般性.所以，在設(shè)計邊選擇策略時，可以優(yōu)先考慮2個端點都在當前邊界集中的邊，然后考慮有一個端點不在邊界集中的邊，這樣才能使當前邊界集最小.2個端點都不在邊界集的情形不用考慮，因為該情形下不可能得到最小的邊界集.

|Fk-1|-2≤|Fk|≤|Fk-1|+2.

(5)

策略1優(yōu)先選擇2個端點u和v都在邊界集中的邊.若存在多條滿足條件的邊，則選擇節(jié)點度和小的邊.若節(jié)點度和也相同，則先選擇與先進入邊界集的節(jié)點相關(guān)聯(lián)的邊.如圖6所示，候選邊ex和ey，由于邊ex的節(jié)點度和小于邊ey，所以邊ex先排.

策略2選擇一個端點u在邊界集中的邊，且該端點度最小，另一端點v有更多的邊關(guān)聯(lián)于當前邊界集.否則，選擇邊e=(u，v)，u在邊界集中，v有最小的度.如圖7所示，節(jié)點i和w的度最小，但節(jié)點y有2條邊關(guān)聯(lián)于邊界集，所以邊ey先排.之后節(jié)點y加入新的邊界集，邊ez的選擇適用策略1.

圖6 策略1示意圖 圖7 策略2示意圖

關(guān)鍵節(jié)點的引入時機也是一個重要影響因素，所以當候選邊關(guān)聯(lián)于關(guān)鍵節(jié)點時，該邊延遲排序.

3.2 排序起點選擇

基于邊界集的啟發(fā)式排序，其最終排序結(jié)果除了和排序策略相關(guān)外，還與排序的初始條件有關(guān).

定義4(邊界集總長度) 對于給定K-端網(wǎng)絡(luò)G=(V,E,K),設(shè)有一個邊序列o=e1≤e2≤e3≤…≤e|E|,ci∈E,i∈[1,|E|]，則關(guān)于序列o的邊界集總長度(記為LTBS(o))定義為

其中,|Fi|為序列o的第i層邊界集長度.在確定排序起點之前，先計算不同排序起點的邊界集總長度LTBS(O(vi)),其中O(vi)表示以vi為排序起點的一種排序結(jié)果，選取邊界集總長度值最小的那個節(jié)點作為排序起點.NS(V)表示在節(jié)點集V中取排序起點.

NS(V)=vi?LTBS(O(vi))=min{LTBS(O(vi)),vi∈V}.

3.3 基于邊界集的啟發(fā)式排序算法

基于邊界集的啟發(fā)式排序主要包含2個部分：1)排序起點選擇；2)排序過程推進.在過程推進中，采用貪心策略，確保每層生成的邊界集長度盡可能小.具體算法如下：

算法2

1)選擇一個節(jié)點v∈V，節(jié)點v擁有最小的邊界集總長度

2)初始化邊界集F0={v}

3)whileFk≠? do

//策略1：

4) for alle(u,v)∈E-Ek,u,v∈Fkdo

5) order.add(e),G.delete(e),update(Fk)

6) end for

//策略2：

7) 選擇一點u∈Fk且u的度最小，在u的鄰接點中選擇一點v，且v擁有最多的未排序邊關(guān)聯(lián)于Fk

8) order.add(e(u，v)),G.delete(e(u，v)),update(Fk)

9) 選擇一點u∈Fk且deg(u)最小，在u的鄰接點中選擇一點v，且v的度最小

10) order.add(e(u，v)),G.delete(e(u，v)),update(Fk)

11) end while

12) return order

4 實驗和結(jié)論

選擇星型網(wǎng)絡(luò)和De-Bruijn網(wǎng)絡(luò)分別驗證本文提出的啟發(fā)式排序策略和排序起點選擇方法，搜集相關(guān)文獻的樣本網(wǎng)絡(luò),用來比較常用啟發(fā)式排序的性能，并在工程實際網(wǎng)絡(luò)中進一步驗證本文提出的啟發(fā)式排序方法.

4.1 Star網(wǎng)絡(luò)

Star網(wǎng)絡(luò)(見圖8)中的節(jié)點(除去中心節(jié)點)具有相似的結(jié)構(gòu)特征，可以最大限度地降低對排序策略的影響.為了更好地說明排序策略，建立了4類排序：1)以快速最大化邊界集(MaxBS)的方式建立邊排序，即優(yōu)先選擇節(jié)點不在邊界集中的邊進行排序；2)以深度優(yōu)先搜索(DFS)方式建立邊排序，理論上邊界集長度每次增1，直到所有節(jié)點都加入邊界集；3)以廣度優(yōu)先搜索方式(BFS)建立邊排序；4)以最小化邊界集方式(本文方法)建立邊排序.

圖8 Star網(wǎng)絡(luò)

實驗步驟如下，實驗結(jié)果如表4所示.

1)隨機選擇一個排序起點，根據(jù)4種不同排序策略建立邊排序；

2)隨機選擇節(jié)點對，建立BDD模型，計算BDD模型大小和BDD寬度.

表4 Star網(wǎng)絡(luò)的BDD模型大小和寬度

4種排序中，MaxBS的排序結(jié)果與排序起點無關(guān)，其余3種與排序起點的選擇有關(guān).在相同的排序策略下，可以建立不同的排序結(jié)果，而不同的排序結(jié)果指導生成不同大小的BDD模型，如表4，即使求解相同的問題(計算節(jié)點對{0,7}的可靠度)，也能生成不同大小的BDD模型.比較BDD模型寬度和模型大小的關(guān)系，所得結(jié)果見圖9.由圖9可得，對于不同的排序策略，當BDD模型寬度較小時，對應(yīng)的模型大小也較小；反之，當模型寬度較大時，模型大小較大.控制BDD模型寬度，有利于控制BDD模型大小.

(a)模型大小 (b)模型寬度

4.2 De-Bruijn網(wǎng)絡(luò)

在De-Bruijn網(wǎng)絡(luò)(見圖10)中，不同排序起點有不同的邊界集總長度.采用本文提出的啟發(fā)式排序策略時，各排序起點對應(yīng)的邊界集總長度如表5所示，節(jié)點“0”“1”和“8”擁有最小的邊界集總長度.

圖10 De-Bruijn網(wǎng)絡(luò)(Order=4)

表5 各排序起點的邊界集總長度

以下實驗說明選擇排序起點的必要性，實驗過程如下，實驗數(shù)據(jù)如表6、表7所示.

表6 BDD模型大小位序分布 表7 邊界集總長度大小位序分布

1)采用本文啟發(fā)式排序策略，根據(jù)不同排序起點建立不同的邊排序(共16種)；

2)根據(jù)16種排序分別為每個節(jié)點對(共120對)生成等價的BDD模型；

3)選擇擁有最小邊界集總長度的節(jié)點作為起點時，統(tǒng)計對應(yīng)的BDD模型大小位序的分布；

4)選定最小BDD模型時，統(tǒng)計邊界集總長度大小的分布.

由表6和表7看出：當選擇擁有最小邊界集總長度的節(jié)點作為排序起點時，最小BDD模型占18.6%，前4小BDD模型占比高達91.7%.對應(yīng)地，當取最小BDD模型時，最小邊界集總長度占55.8%，前4小BDD模型占88.3%.由此可得，選擇擁有最小邊界集總長度的節(jié)點作為排序起點時，可以大概率提升排序質(zhì)量，從而指導生成更小的BDD模型.

4.3 樣本網(wǎng)絡(luò)

本文在相關(guān)文獻中搜集了22個2-端可靠性網(wǎng)絡(luò)，如圖11所示，采用基于邊界集的BDD構(gòu)建方法，結(jié)合本文提出的啟發(fā)式排序，生成等價BDD模型，計算可靠度值和模型大小，實驗結(jié)果如表8所示，其中DFS和BFS的數(shù)據(jù)來自文獻[15]，“*”表示原BDD構(gòu)建方法無法生成BDD模型.

圖11 樣本網(wǎng)絡(luò)

表8 DFS,BFS和本文方法性能比較

表8數(shù)據(jù)表明，BFS略優(yōu)于DFS，而本文提出的啟發(fā)式排序全面優(yōu)于BFS和DFS.

5 結(jié) 語

BDD模型大小嚴重影響基于BDD的網(wǎng)絡(luò)可靠性分析方法性能，而BDD模型大小由所采用的變量大小決定，所以尋找優(yōu)質(zhì)排序是所有基于BDD分析方法的核心問題.本文從研究基于邊界集的BDD構(gòu)建方法入手，深入分析各層BDD節(jié)點的產(chǎn)生過程，總結(jié)啟發(fā)式數(shù)據(jù)：BDD寬度和邊界集總長度，提出排序起點選擇方法和盡可能確保BDD寬度小的排序策略.大量實驗表明，本文提出的啟發(fā)式排序方法優(yōu)于BFS，具有很好的應(yīng)用價值.在今后的工作中，將進一步研究關(guān)鍵節(jié)點和網(wǎng)絡(luò)結(jié)構(gòu)特征對排序質(zhì)量的影響，尋找更為優(yōu)秀的啟發(fā)式排序.