基于節(jié)點壓縮的尋徑優(yōu)化算法

廖志芳 陳亮名 彭志文 李嚴冰

(中南大學軟件學院 湖南 長沙 410075)

基于節(jié)點壓縮的尋徑優(yōu)化算法

廖志芳 陳亮名 彭志文 李嚴冰

(中南大學軟件學院 湖南 長沙 410075)

最短路徑問題是一個經典問題，而目前的研究大多是針對給定起點和終點，選擇從起點到終點的最短路徑，且取得了不少成果。而對于限定時間的最短路徑問題的研究成果相對較少，這類問題在現(xiàn)實生活中卻隨處可見。針對這一問題提出幾種限定時間的尋徑優(yōu)化算法，從對回溯法的改進到不同的節(jié)點壓縮的方法，給出改進的回溯法以及三種基于節(jié)點壓縮的尋徑算法。算法實現(xiàn)在限定的時間內從起點出發(fā)經過給定的節(jié)點集合再到達終點的路徑選擇，并針對不同復雜度的網絡圖有相應合適的算法可以選擇，從而有效地解決這類問題。

最短路徑 限定時間 節(jié)點壓縮 尋徑

0 引 言

圖論中單源最短路徑問題[1-3]是一個經典問題，其在實際生活中應用廣泛，如網絡路由路徑選擇、車載導航、旅行路線等。解決這一問題的經典算法是Dijkstra EW.A于1959年提出的Dijkstra算法。但這一算法不能解決從起點開始必須經過指定的中間節(jié)點再到達終點的問題，然而這類問題實用性更強，比如：

(1) “郵遞員問題”：郵遞員從郵局出發(fā)為有信件的居民送完信件后回家，在給定的時間內為該郵遞員選擇一條行駛距離最短的路線；

(2) “旅行家問題”[4-6]：在指定的時間內為旅行者計算出一條旅行路線，從指定地點出發(fā)，到達指定旅游景點再到達指定目的地，要求路線的總行駛距離或者總行駛開銷最短。

(3) “網絡尋徑問題”[7-9]：在指定的時間內為網絡數(shù)據傳輸尋找一條有效路徑，且這些數(shù)據必須經過某些網絡站點，到達指定的站點，使得網絡開銷最小。

這些問題最終都可以歸納為同一個圖論問題，即在一個帶權有向圖中，從起點經過指定的中間節(jié)點，到達終點，要求在指定時間內，尋找有效路徑，并計算這些路徑的權重，選擇一條權重最低的路徑作為結果路徑。

對于這一類問題，可以采用對整個圖進行遍歷，尋找一條最短路徑。雖然從理論上來說這種遍歷算法最終能夠得到最優(yōu)解，但是其時間復雜度相當高。針對這一問題，本文提出了時間限制的節(jié)點壓縮尋徑算法。該算法通過采用節(jié)點壓縮，將尋徑過程中得到的有用信息使用到搜索條件、調整子節(jié)點順序等方法，改善了傳統(tǒng)算法時間復雜度太高的問題，為這類問題的解決給出了有效的辦法。

1 問題描述

1.1 問題的數(shù)學模型

給定一個帶權有向圖G(V,E),其中:V={1,2,…,n}為頂點集，E={eij=(i,j)|i,j∈V,i≠j}為邊集。dij(i,j∈V,i≠j)為頂點i到j的權重，其中:dij>0且dij≠∞，同時dij和dji可以不相等。V′={1′,2′,…,n′}∈V，給定起點s和終點t，s,t∈V且s，t不屬于V′，要求在給定時間內求序列A={a1,a2,…,an},其中:a1=s,an=t，V′中的所有元素都必須在序列A中出現(xiàn)，并使得以按照序列A在圖中形成的路徑的所有邊的權重之和盡可能小，且路徑中不能出現(xiàn)環(huán)路。該問題的數(shù)學模型定義如下：

(1)

∑i≠jXij=1i∈V

(2)

∑i≠jXij=1j∈V

(3)

∑Xsj=1j∈Vj≠s

(4)

∑Xjs=0j∈Vj≠s

(5)

∑Xit=1i∈Vi≠t

(6)

∑Xti=1i∈Vi≠t

(7)

為了限制路徑中不會出現(xiàn)無關的回路，作如下約束：

∑i,j∈VXij=|A|

(8)

為了方便后續(xù)描述，給出以下兩個定義：

定義1關鍵節(jié)點：問題描述中給定的起始節(jié)點s和終點t以及必經節(jié)點的集合V′為關鍵節(jié)點。

定義2自由節(jié)點：除關鍵節(jié)點以外的所有節(jié)點都是自由節(jié)點。

1.2 簡單樣例

如圖1所示的帶權有向圖G，分別有0、1、2、3共四個節(jié)點，即C={0,1,2,3}，圖中有0、1、2、3、4、5、6七條邊，即E={0,1,2,3,4,5,6}，邊的權重為{d01=1,d02=2,d03=1,d21=3,d31=1,d23=1,d32=1},如果此時需要尋找從0到1的路徑，且必須經過頂點2和3，則V′={2,3}。對于該問題，可以從圖中找到如下兩條可用路徑：0->2->3->1和0->3->2->1。由于第一條路徑各條邊的權重和為4，第二條路徑各條邊的權重和為5，所以此時最優(yōu)解應該為0->2->3->1。

圖1 問題的簡單樣例

2 改進的回溯法(IBA)

使用回溯法求解該問題時，理論上可以得到最優(yōu)解，且可以得到所有解，但是回溯法沒有有效地利用在搜索過程中構造的信息以及已求得的可行解，使其作為下一步搜索的優(yōu)化條件。本節(jié)通過對回溯法進行改進，提出改進的回溯法，在算法每次搜索完上一節(jié)點后，并在搜索下一節(jié)點之前，利用已有的信息和已求出的可行解來添加搜索規(guī)則，從而對搜索方式進行改進，使得算法在運行過程中，利用已有的信息和已求出的可行解來提高搜索效率。

改進回溯法中的添加規(guī)則表示如下：

規(guī)則1如果下一節(jié)點是終點，而當前路徑沒有經過必經節(jié)點集合中的所有節(jié)點，則回溯，繼續(xù)搜索下一節(jié)點。這一規(guī)則可以避免許多無效解的生成，以期提高算法效率。

規(guī)則2如果當前路徑權重加上到達下一節(jié)點的那條邊的權重大于等于當前已求得的權重最小的可行解的路徑，則回溯，繼續(xù)搜索下一節(jié)點。由于當前已經搜索到可行的路徑，如果當前路徑權重加上下一節(jié)點的權重不小于已有路徑權重，那么接下來繼續(xù)搜索就沒有任何意義，因為問題是求解權重盡量小的路徑。

規(guī)則3對于不是終點而且沒有子節(jié)點的節(jié)點，要避免進入搜索。如果某節(jié)點不是終點，又沒有子節(jié)點，到達該節(jié)點后無法繼續(xù)下去，因此這種節(jié)點是沒有必要搜索的，甚至可以在圖中直接刪除。

改進回溯法算法的關鍵偽代碼如下：

Improved-Backtrack(G)

1 node=start

2 while usedtime

3 nodes.add(node)

4 record information include route and weigths

5 for i=1 to children.length

6 add search rule

7 Improvedacktrack(children[i])

8 if result ！=null-B

9 return result and weight

10 else

11 return NA

3 節(jié)點壓縮的搜索算法

雖然改進的回溯算法在一定程度上可以提高搜索效率，但是隨著圖規(guī)模的增大，解空間的增長，改進的回溯法的復雜度也隨之提高。為降低算法復雜度，本文提出了新算法—基于節(jié)點壓縮的搜索算法NCSA(Node Compression based Search Algorithm)。

隨著圖規(guī)模的增大，圖中的路徑也隨之擴大，而所求路徑是從起點到終點且經過中間節(jié)點的路徑，因此可以先將圖進行預處理，對圖的總節(jié)點數(shù)進行壓縮，去掉無關的節(jié)點和價值較低的路徑片段，盡量只保留需要的路徑，從而達到簡化整個圖、縮小解空間、提高搜索效率的目的。

3.1 節(jié)點壓縮算法(NCA)

本算法要解決的問題具有如下情況：如有節(jié)點比較偏僻，只能到達一個其他節(jié)點(即只有一個子節(jié)點)，當算法搜索過程中到達這樣的節(jié)點時，只會往它唯一的子節(jié)點往下走。每經過該節(jié)點一次就要這樣走一次，這樣簡單而又重復的計算是可以避免的。

解決辦法就是采用節(jié)點壓縮的方法，將經過該類型節(jié)點的唯一路徑在搜索算法第一次經過時就記錄下來，并將這一節(jié)點移除，只保留這一路徑信息。當下次搜索到達該節(jié)點時，直接使用已存在的路徑信息，避免重復搜索計算。移除節(jié)點之后的圖總節(jié)點數(shù)目減少，因此經過壓縮之后的圖將更容易搜索出更好的解。

過程如圖2所示。

圖2 壓縮搜索算法的基本思想

圖中節(jié)點1只有1個子節(jié)點2，節(jié)點1到節(jié)點2的權重為2，路徑為“1”，壓縮過程就是將節(jié)點1的信息合并到節(jié)點2上，節(jié)點2成為節(jié)點0的直接子節(jié)點，壓縮之后，節(jié)點0到節(jié)點2的權重就變?yōu)?，節(jié)點0到節(jié)點2的路徑變?yōu)椤?|1”。這樣就有效地將節(jié)點1移除了，并將節(jié)點1到2的路徑保留在節(jié)點2的信息中。當下次搜索算法到達節(jié)點0時，可以直接使用節(jié)點2中保留的信息，而無需再次搜索節(jié)點1。

3.2 完全壓縮算法(CCA)

由于節(jié)點壓縮算法(NCA)的目標是針對只有一個子節(jié)點的自由節(jié)點，如果圖中這樣的節(jié)點個數(shù)較多，那么算法的效率提高就比較明顯。但是如果圖中這樣的節(jié)點很少甚至沒有，那么基本壓縮策略的效果就不明顯，甚至會沒有任何效果，因而利用壓縮方法的搜索算法在這種情況下并沒有效果。

針對NCA算法的這一問題，本文提出了更有效的壓縮策略，針對所有的自由節(jié)點進行壓縮，從而有效地對圖中節(jié)點進行壓縮，降低圖的復雜度，提高搜索效率。

該問題集中在尋找從起點到終點并經過中間節(jié)點集合的不成環(huán)的路徑，使得路徑上各條邊的權重盡可能小。當圖中節(jié)點互相之間的可達關系比較復雜時，從一個節(jié)點到達另一個節(jié)點的可行路徑會很多，由于問題要求必須經過中間節(jié)點集合V′,且中間節(jié)點集合中的各個節(jié)點之間的可達路徑也會有多條。而最終解只會從這些路徑中選擇一條作為它的一個片段，因此，找出所有可達路徑，并盡可能保存權重最小的一條路徑，當搜索算法到達相應的節(jié)點時可以直接使用這些保存好的路徑。而原路徑上的自由節(jié)點則可以從圖中移除，從而減少了圖中的節(jié)點。使用這種壓縮方法壓縮后的圖中，僅存在起點、終點、中間節(jié)點集合以及它們之間互通的路徑信息，這樣就在很大程度上簡化了整個圖，更加有效地進行了壓縮。

3.3 改進的完全壓縮算法(ICCA)

為進一步改善壓縮效果，本文繼續(xù)進行節(jié)點壓縮的調整和改進。

1) 調整子節(jié)點順序使之按照權重大小順序排序

由于在搜索過程中，可以當前可行解的權重為基礎進行搜索(參照基本搜索算法的改進規(guī)則2)，將子節(jié)點的順序按照權重大小從小到大排序，搜索時先搜索權重小的子節(jié)點，則權重較小的路徑就有可能先得到。根據搜索策略就可以跳過一些權重較大的路徑，減少不必要的搜索過程，提高效率。

2) 調整子節(jié)點順序，使之按照經過的節(jié)點的個數(shù)從小到大的順序排序

從概率的角度來講，如果經過的節(jié)點個數(shù)越多，那么新加入一個節(jié)點時產生重復路徑的可能性就越大。因此，在權重相同的基礎上，優(yōu)先選擇那些經過節(jié)點個數(shù)較少的子節(jié)點，在后續(xù)選擇路徑時尋找沒有重復節(jié)點的過程就越簡單，從而更容易尋找符合條件的路徑。

3) 去掉子節(jié)點中權重較大的子節(jié)點

該條件是針對復雜程度很高的圖，壓縮之后剩下的節(jié)點基本可以兩兩形成路徑。針對這樣的情況，為了降低圖的復雜度，對于圖中某些子節(jié)點，因其權重比較大，雖然經過該節(jié)點有能夠到達終點的有效路徑，但由于其權重過大，該路徑可能是結果不太好的路徑。去掉這些權重較高的異常關系，可以降低圖的復雜度，提高搜索效率，另一方面，也避免了搜索這些點耗費的時間，從而更快地搜索權重較低的路徑。

經過分析，IBA的空間復雜度為O(n)，NCA、CCA及ICCA的空間復雜度為O(n2),其中n為圖中總節(jié)點個數(shù)。

4 實驗驗證

4.1 數(shù)據說明及分析

為了不失一般性，實驗數(shù)據采取“2016年華為軟件精英大賽”的多個用例，這些用例來自華為公司在建設網絡時的路由器交換機等網絡元素構成的網絡拓撲圖。

1) 問題描述

給定一個帶權重的有向圖G=(V,E)，V為頂點集，E為有向邊集，每一條有向邊均包含權重。對于給定的頂點s、t，以及V的子集V′，在給定的時間內，尋找從s到t的不成環(huán)有向路徑P，使得P經過V′中所有的頂點(對經過V′中節(jié)點的順序不做要求)，并使得路徑P上的所有有向邊的權重之和盡可能小。

2) 數(shù)據說明

(1) 圖中所有權重均為[1，20]內的整數(shù)；

(2) 任一有向邊的起點不等于終點；

(3) 連接頂點A至頂點B的有向邊可能超過一條，其權重可能一樣，也可能不一樣；

(4) 有向圖的頂點不會超過600個，每個頂點出度(以該點為起點的有向邊數(shù)量)不超過8；

(5)V′中元素個數(shù)不超過50；

(6) 從s到t的不成環(huán)有向路徑P是指，P為由一系列有向邊組成的從s至t的有向連通路徑，且不允許重復經過任一節(jié)點；

(7) 路徑的權重是指所有組成該路徑的所有有向邊的權重之和。

3) 數(shù)據格式

(1) 圖的數(shù)據中，每一行包含如下的信息：{LinkID,SourceID,DestinationID,Cost}，其中LinkID為該有向邊的索引，SourceID為該有向邊的起始頂點的索引，DestinationID為該有向邊的終止頂點的索引，Cost為該有向邊的權重。頂點與有向邊的索引均從0開始 編號(不一定連續(xù)，但用例保證索引不重復)。

(2) 路徑信息中，只有一行如下數(shù)據：SourceID,DestinationID,IncludingSet。其中，SourceID為該路徑的起點，DestinationID為該路徑的終點，IncludingSet表示必須經過的頂點集合V′，其中不同的頂點索引之間用“|”分割。

4) 實驗環(huán)境

Windows7 64位操作系統(tǒng)，處理器為Intel core i5，jre1.6，32位Java虛擬機，可占用的最大內存為2 GB。

4.2 實驗方法及結果分析

1) IBA、NCA、CCA的比較

為了驗證回溯法，IBA、NCA以及CCA之間的效果，將進行四組實驗，求解時間限定為10秒，從實驗1到實驗4將會逐漸增加圖中的總節(jié)點個數(shù)和圖中邊的條數(shù)，而中間節(jié)點個數(shù)保持不變。實驗將從最終結果路徑的權重,找出最終結果的使用時間兩個維度進行比較。

實驗1總節(jié)點個數(shù)10,必經節(jié)點個數(shù)3，圖的邊數(shù)39，如圖3所示。

圖3 實驗1實驗結果

從實驗1的實驗結果可以看出，IBA比Backtrack的效率要高一些，基于節(jié)點壓縮的NCA和CCA效果提高不明顯，這是因為壓縮節(jié)點的過程要耗費一些時間，當圖的復雜度較低時，效率提高就不太明顯了。

實驗2總節(jié)點個數(shù)20,必經節(jié)點個數(shù)5，圖的邊數(shù)55，如圖4所示。

圖4 實驗2實驗結果

從實驗2的實驗結果可以看出，IBA、NCA、CCA相比Backtrack效果有明顯提高，CCA效果則更加明顯；IBA和NCA效果相似，這是因為圖中較偏僻的節(jié)點較少。

實驗3總節(jié)點個數(shù)30,必經節(jié)點個數(shù)10，圖的邊數(shù)135，如圖5所示。

圖5 實驗3實驗結果

從實驗3的實驗結果可以看出當圖的復雜度逐漸提高時，CCA的優(yōu)越性更加明顯地體現(xiàn)出來了。

實驗4總節(jié)點個數(shù)40,必經節(jié)點個數(shù)10，圖的邊數(shù)229，如圖6所示。

圖6 實驗4實驗結果

實驗4的結果表明，當圖的復雜度達到更高時，Backtrack的實用性就不那么好了，而CCA的效率依然很好。

從實驗結果可以看出，IBA無論在得到的結果路徑的權重還是搜索時間上，都比Backtrack要好；NCA比IBA有一定的進步，但效果不明顯，主要原因是實驗中所使用的圖中，存在偏僻節(jié)點的情況不多；而CCA在各個維度上相比前三種算法，都大大地提高了搜索結果的質量和效率，可見CCA是一種很有效解決這一問題的算法。

2) CCA和ICCA的比較

從前4個實驗結果來看，Backtrack、IBA、NCA的效率隨著圖中節(jié)點個數(shù)的增加急劇降低。因此，繼續(xù)增加節(jié)點個數(shù)將變得沒有意義，接下來將只針對CCA和ICCA之間的比較。

實驗環(huán)境和實驗1-實驗4的相同，也將逐漸增加總節(jié)點個數(shù)和圖中邊的條數(shù)，另外還會逐漸增加中間節(jié)點集合的大小，將從以下5個實驗進行比較。

實驗5總節(jié)點個數(shù)60,必經節(jié)點個數(shù)10，圖的邊數(shù)285，如圖7所示。

圖7 實驗5的實驗結果

實驗6總節(jié)點個數(shù)100,必經節(jié)點個數(shù)15，圖的邊數(shù)516，如圖8所示。

圖8 實驗6的實驗結果

實驗7總節(jié)點個數(shù)200,必經節(jié)點個數(shù)20，圖的邊數(shù)997，如圖9所示。

圖9 實驗7的實驗結果

實驗8總節(jié)點個數(shù)400,必經節(jié)點個數(shù)28，圖的邊數(shù)2 178，如圖10所示。

圖10 實驗8的實驗結果

實驗9總節(jié)點個數(shù)600,必經節(jié)點個數(shù)50，圖的邊數(shù)3 418，如圖11所示。

圖11 實驗9的實驗結果

從實驗結果可以看出，ICCA相比CCA，其最終解都要好一些，因此，3.3節(jié)中的改進策略是行之有效的。

5 結 語

無論是“郵遞員問題”、“旅行家問題”、公交車專線設計以及網絡選路問題，還是其他生活中類似問題，都可以抽象為本文研究的尋徑問題。本文提出的IBA和NCA適用于規(guī)模中等的問題。如果圖中有很多相對偏僻的節(jié)點，則建議使用NCA；CCA和ICCA這兩種算法適用于規(guī)模較大的問題，算法實現(xiàn)難度較大，如果問題可以通過調整字節(jié)點的排序規(guī)則來提高搜索效率，則使用ICCA。

由于當問題規(guī)模變得更加龐大時，CCA和ICCA在給定的時間內也無法將整個解空間搜索完全，得不到最優(yōu)解。接下來將會把壓縮思想融入到遺傳算法、蟻群算法等啟發(fā)式算法中，以期獲得更高效的搜索算法，從而解決更大規(guī)模的尋徑問題。

[1] 章登義,吳文李,歐陽黜霏.RDF圖的Top-k最短路徑查詢[J].電子學報,2015,43(8):1531-1537.

[2] 王峰,曼媛,段俊潔.一種改進的求解前N條最短路徑問題的多重標號算法[J].小型微型計算機系統(tǒng),2016,37(7):1482-1487.

[3] 馮琳耀,袁林旺,羅文,等.節(jié)點約束型最短路徑的幾何代數(shù)算法[J].電子學報,2014,42(5):846-851.

[4] 戚遠航,蔡延光,蔡顥,等.旅行商問題的混沌混合離散蝙蝠算法[J].電子學報,2016,44(10):2543-2547.

[5] 王勇臻,陳燕,張金松.求解TSP的學習記憶果蠅算法[J].小型微型計算機系統(tǒng),2016,37(12):2722-2726.

[6] 吳新杰,王靜文,黃國興,等.一種求解旅行商問題的改進蛙跳算法[J].小型微型計算機系統(tǒng),2015,36(5):1078-1081.

[7] 劉大偉,呂元娜,余智華.一種改進的復雜網絡鏈路預測算法[J].小型微型計算機系統(tǒng),2016,37(5):1071-1074.

[8] 安瑩,黃家瑋,羅熹,等.延遲容忍網絡中一種基于節(jié)點介數(shù)的擁塞感知路由算法[J].小型微型計算機系統(tǒng),2014,35(9):2062-2067.

[9] 李曉華,王士猛,楊曉春,等.基于Grid網格劃分的改進路網最短路徑查詢[J].小型微型計算機系統(tǒng),2014,35(9):1937-1942.

SEARCHPATHOPTIMIZATIONALGORITHMBASEDONNODECOMPRESSION

Liao Zhifang Chen Liangming Peng Zhiwen Li Yanbing

(SchoolofSoftware,CentralSouthUniversity,Changsha410075,Hunan,China)

The shortest path problem is a classic problem，while the current study is mostly for a given starting point and end point, choose the shortest path from the starting point to the end, and has achieved a lot of results. For the limit time of the research achievements of the shortest path problem is relatively less, this kind of problem is ubiquitous in real life. In this paper, we propose several optimization algorithms for time-dependent optimization of this problem, from the improvement of backtracking method to the method of different node compression, an improved backtracking method and three algorithms based on node compression are proposed. Implemented in a limited amount of time, starting from the starting point after a given node set to reach the destination path selection, and according to different complexity of network diagram, can choose the appropriate algorithm to deal with, which can effectively solve the problem.

Shortest path Time constrained Node compression Search path

2017-02-12。國家自然科學基金青年項目(61301136)。廖志芳，副教授，主研領域：數(shù)據挖掘，推薦系統(tǒng)。陳亮名，碩士。彭志文，碩士。李嚴冰，碩士。

TP393

A

10.3969/j.issn.1000-386x.2017.11.045