過必經點的最短無環路徑算法

余英瀚

【摘要】通過啟發式算法解決在帶權有向圖中從某一源點經過指定的必經點集到達目標終點且節點不重復的最短無環路徑問題。隨著復雜網絡優化問題的不斷凸顯，對網絡分析算法的性能要求也日漸升高。經過必經點的最短無環路徑問題的復雜度不亞于旅行商問題（TSP），但并沒有獲得廣泛的關注。近些年來出現了一種高效的整數線性規劃公式（ILP）來解決此類問題，這種ILP算法適用于有節點不相交約束的最短路徑問題，但是實驗表明在大型復雜網絡中這種算法的時間開銷過高。因此有了本論文的三種啟發式算法，大量的實驗表明這些算法在大多數情況下都能在可接受的時間范圍內找出合理解，這些解與最優解的誤差都在可接受的范圍內，后續的CPU開銷數據也表明此類啟發式算法的資源消耗遠小于整數線性規劃（ILP）算法。

【關鍵詞】彈性路由 最短路徑問題 必經點

作為社會關鍵基礎設施，通信網絡的可伸縮性和生命力是十分重要的。參見通信網絡中的彈性和生命力結構性框架。根據路由路徑約束的等級，其通過約束路徑來尋找節點（或邊）不重復的路由，在某些情況下所尋求的路徑必須滿足經過指定的必經點點集的約束，這些必經點可能是基于某種特性（比如高可靠性）被選出的，也可能是根據基于運營商之間協議所產生的參數來決定的，或者是由于其他網絡管理的約束條件所制定的。針對諸如此類從某一源點經過一系列給定的必經點到達另一終點的最短路徑計算問題的算法少之又少，已知的最早的算法是由Saksena和Kumar提出的，他們嘗試運用最佳性原理開發出一種精確算法來計算經過指定點集的最短路徑問題（路徑可能有環）。

考慮到時間復雜度，Dreyfus在中指出，從某一源點經過必經點點集到目標節點的最短路徑算法（可能有環路）的時間復雜度并不亞于k維旅行商問題（TSP），這里k-2代表必經點的個數。Andrade也提出，如果必經點點集是由有向圖中除源點和終點外的所有節點構成的，此類問題相當于尋找最短權重的漢密爾頓通路，屬于NP-困難問題。

文章的其余部分結構如下。第一部分介紹了該問題模型的數學公式和數學方法。第二部分著重敘述了計算經過必經點的最短無環路徑的啟發式算法，包括最早的SK66算法，以及SK66算法的修正版算法。第三部分描述了針對此類最短路徑問題的三種變體型啟發式算法。第四部分為實驗數據結果。第五部分為總結。

一、數學模型

對該問題的數學建模旨在尋找經過給定必經點點集的無環最短路徑，并且滿足要求路徑上沒有交點。一條無環路徑上每個節點只能經過一次，因此所有的路徑都必須是不存在環路的。

（一）數學符號

在本文第二及第三部分用了如下數學定義。定義有向圖G=（V，A），其中點集V={v1，...，vn}，有向邊集A={a1，…，am}。定義如果vi，vj∈V，并且vi=vj，ak=（vi，vj）∈A，則vi為邊尾vj為邊頭。邊（vi，vj）定義為從點vi到vj的路徑。邊（vi，vj）和邊（vj，vi）為對稱邊。

一條路徑定義為從源點s開始的到終點t的一個不同點組成的連續序列，（s，t∈V），將其定義為p=，其中（vi，vi+1）∈A，？坌i∈{1，…，k-1}，k為該路徑中節點的個數。由Vp代表路徑p中所有點的點集，Ap代表路徑上所有邊的邊集合，Ap=∪？坌i∈{1，...，k-1}（vi，vi+1）。經過一條邊（vi，vj）∈A的花費（權重）定義為w（vi，vj），假設為大于0的正數。一條路徑的權重為路徑上所有邊權重的代數和，Dp=（vi，vj）∈Ap w（vi，vj）。如果兩點之間不存在通路，則定義其權重為無窮。

二、過指定必經點的最短路徑

最初的SK66算法，雖然不能保證計算出最優路徑，但是其時間復雜度與必經點點集（|Vs|）的規模成正比；在初始化階段首先計算（|Vs|+2）|Vs|個最短路徑；在之后的每一步需要|Vs|2次計算，該步驟中大部分的時間開銷花費在節點計算過程中，其最差時間復雜度為|V|log2|V|；因此，SK66算法的最差時間復雜度為O（|Vs+2|2|A|log2|V|+|Vs|2|V|log2|V|），其中假設最短子路徑計算是基于二叉堆的Dijkstra算法。

（一）Saksena和Kumar提出的算法（SK66）

SK66算法通過在每一次子路徑的選擇中找出當前最短路徑，計算出從某一源點到另一終點并且經過制定必經點點集的最終最短路徑（可能存環路）。算法的初始化步驟為：

（1）計算出必經點點集|Vs|中任意兩點的最短距離（沒有任何限制），和源點s到點集中每一點的最短距離；

（2）計算出必經點點集Vs中每一點到終點的最短距離。

假定D（vi，vl）代表從點vi到vl的最短路徑花費，其中vi∈Vs ∪{s}并且vl∈Vs，f0vi代表從一點vi∈Vs到終點t的最短路徑花費。

（二）SK66算法改進版

此部分算法為SK66算法的改進版本，它可以保證所獲得的路徑是不含環路的，并且提高了原始算法的性能。此改進版本的算法犧牲了一定空間來同時存儲更多的中間子路徑，來換取時間上的充裕，這種算法暫命名為SK。

為了保證獲得的路徑是無環的，每一次迭代（12）和（11）進行時必須嚴格保證迭代獲得的子路徑不含環路。

根據上述公式，在SK66算法的每一次迭代中，對于每一個必經點集Vs中的點vi都要選出一個新的中間點vl（vl∈Vs）放到路徑中。SK66的這個步驟在尋找局部最優路徑時也許會提前因為更高的權重而排除掉本身最優路徑解的子路徑，因為局部最優并不是全局最優解，并且可能造成之后的必經節點無法到達的窘境。此算法主要的改進在于，在每一次迭代η尋找vi到終點t的中間節點vl時，同時保留所有可能的中間點vl，而不是像SK66中一樣尋找距離最近的中間節點vl，因此在此改進版本的算法中每一步的迭代需要保留|Vs|-1條路徑。

三、保證路徑上沒有節點相交的變體型啟發式算法

此部分著重介紹用于尋找經過指定必經點點集并且滿足約束條件路徑上節點互不相交的最短路徑的兩種不同的算法。

（一）主動子路徑選取算法

在此部分著重介紹一種基于2.2章節SK算法的新算法，它在執行SK算法每一步的迭代過程中，每一次尋找子路徑時都加入了嚴格的限制來確保所獲得的子路徑與將來的最終路徑之間是沒有相交節點的。然而這個過程并不能保證最終當所尋找的子路徑聯結起來時能形成一條從s到t的最短路徑。

此算法的初始步驟為：

（1）運用算法（8）和（9），最多可以得到τ條（其中τ=|A|/|V|2 |VS|）該有向圖中的最短路徑（vi，vj），其中vi∈VS ∪ {s}，vj∈VS；若尋找到第k條最短路徑Pij（k=1，…，τ）時，在圖中移除掉點集（Vpij∪Vs）＼{s}之后仍能使源點s到終點t連通，此時尋找過程停止并保存路徑Pij。

（2）運用算法（8）和（9），最多可以得到從節點vi到終點t的τ條（其中τ=|A|/|V|2|Vs|）該有向圖中的最短路徑（vi，t），其中vi∈Vs；若尋找到第k條最短路徑Pit（k=1，…，τ）時，在圖中移除掉點集（Vpit∪Vs）＼{t}之后仍能使源點s到終點t連通，此時尋找過程停止并保存路徑Pit。

然后運用SK算法并在每一次迭代η中另加入限制，保證去掉子路徑的節點（Vs∪VPit＼{t}）時源點s到終點t始終可以保持連通；類似的，在最后一步中，只有每一段無環子路徑之間互相節點不相交才能保證最終從s到t路徑的存在。

算法的最后一步選擇中首先使用了（13），并且加入限制路徑必須是無環并且互相之間節點不相交的。如果一段子路徑p，可以使從源點s到某一點vl的子路徑與從vl到終點t的子路徑聯合并且不存在環路，接下來需要驗證這條聯合路徑是否有從s到t的備用節點不相交路徑。

需要注意的是，雖然保證了每一段子路徑都是從s到t的節點不相交路徑，但這并不代表最終路徑的存在。因此，此子路徑主動選取算法仍然有待優化并輔以其他算法相配合。

（二）備用路徑優先選取算法

在一切特定的網絡環境中，3.1中的主動子路徑選取算法選出的子路徑也許并不能構成一條完整的路徑。因此產生了與之相對的另一種算法來優先尋找備用路徑，然后通過備用路徑來找到對應的路徑。

這種算法的原理是嘗試在移除了所有必經點及其相關路徑的有向圖中尋找備用路徑。首先根據已有的班得瑞算法[11]生成具有最短權重和的盡量包含最多節點并且節點之間互不相交的路徑。然后對于每一條備用路徑（用q代表其所包含的節點），在有向圖中移除該備用路徑的中間節點得到網絡（V＼（Vq＼{s，t}），A），而后在該網絡中運用SK算法得出其子路徑。

如果之前的步驟出現問題不能找出子路徑，此時需要重新運用公式（8）和（9）來計算在移除了必經點點集Vs中的所有點后的有向圖中的最短備用子路徑，然后針對每一條備用最短子路徑使用SK算法計算出其子路徑，重復此過程路徑被找到。

（三）啟發式算法的結合

命名3.1中的主動子路徑選取算法為ASK，3.2中的備用路徑優先選取為BSK；對于此類問題首先運用ASK算法，當網絡環境特殊使用ASK沒有合適解時在其中加入BSK算法，將此混合算法命名為ABSK。

四、結果

考慮到不同的網絡環境做了兩個不同的實驗測試。第一組網絡模型來自SNDlib[12]，反映的是真實世界中的網絡，分別用了newyork，norway，india35，pioro40和germany50的網絡模型；第二組網絡使用了Georgia Tech Internetwork Topology Models軟件（GT-ITM）生成模型，包含了5組平均出度為7的500節點網絡模型。指定的必經節點數量定為2個4個或6個，完全隨機分配。在每個網絡中對于每一組必經點點集Vs，隨機生成100對點集，產生20組樣例，并以95%的置信區間為誤差線標注在之后的圖表上。

實驗結果的衡量是根據解決問題數量的占比百分數來決定并標注的，以CPLEX求解器計算出的結果予以對比，來評價本文中啟發式算法的效率。

五、結論

在某網絡中從某一源點經過指定的必經點點集到達目標節點的路徑的計算需求隨著網絡管理約束的豐富而日益增多。整數線性規劃（ILP）[8]適用于解決此類問題并且滿足限制子路徑之間互相節點不相交，但時間成本過高。

根據本文的實驗結果不難看出，基于啟發式算法的主動路徑選擇和備用路徑優先選擇算法可以廣泛應用于各種復雜的網絡環境中，并且在可接受的誤差范圍內計算出可行解。相比于整數線性規劃算法（ILP），該算法在CPU時間開銷方面具有明顯的優勢，可以在網絡拓撲環境日益復雜的今天被廣泛應用。

參考文獻

[1]J.P.Sterbenz，D.Hutchison，E.K.C？etinkaya，A.Jabbar，J.P.Rohrer， M.Sch¨oller，and P.Smith，“Resilience and survivability in communi- cation networks：Strategies，principles，and survey of disciplines，”Computer Networks，vol.54，no.8，pp.1245-1265，2010.Resilient and Survivable networks.

[2]王實，高文.增強型樸索貝葉斯學習[J].計算機科學，2000，27（4）；46-49.

[3]林瀾，閆春鋼，等.基于穩定分支的變權網絡最優路徑算法[J].電子學報，2006，34（7）：1222-1225.

[4]曹政才，等.面向城市交通網絡的一種新型動態路徑尋優方法[J].電子學報，2012，40（10）：2043-2067.