過必經(jīng)點的最短無環(huán)路徑算法
2016-09-10 23:26:35余英瀚
時代金融 2016年24期
余英瀚
【摘要】通過啟發(fā)式算法解決在帶權(quán)有向圖中從某一源點經(jīng)過指定的必經(jīng)點集到達目標終點且節(jié)點不重復的最短無環(huán)路徑問題。隨著復雜網(wǎng)絡(luò)優(yōu)化問題的不斷凸顯，對網(wǎng)絡(luò)分析算法的性能要求也日漸升高。經(jīng)過必經(jīng)點的最短無環(huán)路徑問題的復雜度不亞于旅行商問題（TSP），但并沒有獲得廣泛的關(guān)注。近些年來出現(xiàn)了一種高效的整數(shù)線性規(guī)劃公式（ILP）來解決此類問題，這種ILP算法適用于有節(jié)點不相交約束的最短路徑問題，但是實驗表明在大型復雜網(wǎng)絡(luò)中這種算法的時間開銷過高。因此有了本論文的三種啟發(fā)式算法，大量的實驗表明這些算法在大多數(shù)情況下都能在可接受的時間范圍內(nèi)找出合理解，這些解與最優(yōu)解的誤差都在可接受的范圍內(nèi)，后續(xù)的CPU開銷數(shù)據(jù)也表明此類啟發(fā)式算法的資源消耗遠小于整數(shù)線性規(guī)劃（ILP）算法。
【關(guān)鍵詞】彈性路由 最短路徑問題 必經(jīng)點
作為社會關(guān)鍵基礎(chǔ)設(shè)施，通信網(wǎng)絡(luò)的可伸縮性和生命力是十分重要的。參見通信網(wǎng)絡(luò)中的彈性和生命力結(jié)構(gòu)性框架。根據(jù)路由路徑約束的等級，其通過約束路徑來尋找節(jié)點（或邊）不重復的路由，在某些情況下所尋求的路徑必須滿足經(jīng)過指定的必經(jīng)點點集的約束，這些必經(jīng)點可能是基于某種特性（比如高可靠性）被選出的，也可能是根據(jù)基于運營商之間協(xié)議所產(chǎn)生的參數(shù)來決定的，或者是由于其他網(wǎng)絡(luò)管理的約束條件所制定的。針對諸如此類從某一源點經(jīng)過一系列給定的必經(jīng)點到達另一終點的最短路徑計算問題的算法少之又少，已知的最早的算法是由Saksena和Kumar提出的，他們嘗試運用最佳性原理開發(fā)出一種精確算法來計算經(jīng)過指定點集的最短路徑問題（路徑可能有環(huán)）。
考慮到時間復雜度，Dreyfus在中指出，從某一源點經(jīng)過必經(jīng)點點集到目標節(jié)點的最短路徑算法（可能有環(huán)路）的時間復雜度并不亞于k維旅行商問題（TSP），這里k-2代表必經(jīng)點的個數(shù)。Andrade也提出，如果必經(jīng)點點集是由有向圖中除源點和終點外的所有節(jié)點構(gòu)成的，此類問題相當于尋找最短權(quán)重的漢密爾頓通路，屬于NP-困難問題。
文章的其余部分結(jié)構(gòu)如下。第一部分介紹了該問題模型的數(shù)學公式和數(shù)學方法。第二部分著重敘述了計算經(jīng)過必經(jīng)點的最短無環(huán)路徑的啟發(fā)式算法，包括最早的SK66算法，以及SK66算法的修正版算法。第三部分描述了針對此類最短路徑問題的三種變體型啟發(fā)式算法。第四部分為實驗數(shù)據(jù)結(jié)果。第五部分為總結(jié)。
一、數(shù)學模型
對該問題的數(shù)學建模旨在尋找經(jīng)過給定必經(jīng)點點集的無環(huán)最短路徑，并且滿足要求路徑上沒有交點。一條無環(huán)路徑上每個節(jié)點只能經(jīng)過一次，因此所有的路徑都必須是不存在環(huán)路的。
（一）數(shù)學符號
在本文第二及第三部分用了如下數(shù)學定義。定義有向圖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的一個不同點組成的連續(xù)序列，（s，t∈V），將其定義為p=
二、過指定必經(jīng)點的最短路徑
最初的SK66算法，雖然不能保證計算出最優(yōu)路徑，但是其時間復雜度與必經(jīng)點點集（|Vs|）的規(guī)模成正比；在初始化階段首先計算（|Vs|+2）|Vs|個最短路徑；在之后的每一步需要|Vs|2次計算，該步驟中大部分的時間開銷花費在節(jié)點計算過程中，其最差時間復雜度為|V|log2|V|；因此，SK66算法的最差時間復雜度為O（|Vs+2|2|A|log2|V|+|Vs|2|V|log2|V|），其中假設(shè)最短子路徑計算是基于二叉堆的Dijkstra算法。
（一）Saksena和Kumar提出的算法（SK66）
SK66算法通過在每一次子路徑的選擇中找出當前最短路徑，計算出從某一源點到另一終點并且經(jīng)過制定必經(jīng)點點集的最終最短路徑（可能存環(huán)路）。算法的初始化步驟為：
（1）計算出必經(jīng)點點集|Vs|中任意兩點的最短距離（沒有任何限制），和源點s到點集中每一點的最短距離；
（2）計算出必經(jīng)點點集Vs中每一點到終點的最短距離。
假定D（vi，vl）代表從點vi到vl的最短路徑花費，其中vi∈Vs ∪{s}并且vl∈Vs，f0vi代表從一點vi∈Vs到終點t的最短路徑花費。
（二）SK66算法改進版
此部分算法為SK66算法的改進版本，它可以保證所獲得的路徑是不含環(huán)路的，并且提高了原始算法的性能。此改進版本的算法犧牲了一定空間來同時存儲更多的中間子路徑，來換取時間上的充裕，這種算法暫命名為SK。
為了保證獲得的路徑是無環(huán)的，每一次迭代（12）和（11）進行時必須嚴格保證迭代獲得的子路徑不含環(huán)路。
根據(jù)上述公式，在SK66算法的每一次迭代中，對于每一個必經(jīng)點集Vs中的點vi都要選出一個新的中間點vl（vl∈Vs）放到路徑中。SK66的這個步驟在尋找局部最優(yōu)路徑時也許會提前因為更高的權(quán)重而排除掉本身最優(yōu)路徑解的子路徑，因為局部最優(yōu)并不是全局最優(yōu)解，并且可能造成之后的必經(jīng)節(jié)點無法到達的窘境。此算法主要的改進在于，在每一次迭代η尋找vi到終點t的中間節(jié)點vl時，同時保留所有可能的中間點vl，而不是像SK66中一樣尋找距離最近的中間節(jié)點vl，因此在此改進版本的算法中每一步的迭代需要保留|Vs|-1條路徑。
三、保證路徑上沒有節(jié)點相交的變體型啟發(fā)式算法
此部分著重介紹用于尋找經(jīng)過指定必經(jīng)點點集并且滿足約束條件路徑上節(jié)點互不相交的最短路徑的兩種不同的算法。
（一）主動子路徑選取算法
在此部分著重介紹一種基于2.2章節(jié)SK算法的新算法，它在執(zhí)行SK算法每一步的迭代過程中，每一次尋找子路徑時都加入了嚴格的限制來確保所獲得的子路徑與將來的最終路徑之間是沒有相交節(jié)點的。然而這個過程并不能保證最終當所尋找的子路徑聯(lián)結(jié)起來時能形成一條從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），最多可以得到從節(jié)點vi到終點t的τ條（其中τ=|A|/|V|2|Vs|）該有向圖中的最短路徑（vi，t），其中vi∈Vs；若尋找到第k條最短路徑Pit（k=1，…，τ）時，在圖中移除掉點集（Vpit∪Vs）＼{t}之后仍能使源點s到終點t連通，此時尋找過程停止并保存路徑Pit。
然后運用SK算法并在每一次迭代η中另加入限制，保證去掉子路徑的節(jié)點（Vs∪VPit＼{t}）時源點s到終點t始終可以保持連通；類似的，在最后一步中，只有每一段無環(huán)子路徑之間互相節(jié)點不相交才能保證最終從s到t路徑的存在。
算法的最后一步選擇中首先使用了（13），并且加入限制路徑必須是無環(huán)并且互相之間節(jié)點不相交的。如果一段子路徑p，可以使從源點s到某一點vl的子路徑與從vl到終點t的子路徑聯(lián)合并且不存在環(huán)路，接下來需要驗證這條聯(lián)合路徑是否有從s到t的備用節(jié)點不相交路徑。
需要注意的是，雖然保證了每一段子路徑都是從s到t的節(jié)點不相交路徑，但這并不代表最終路徑的存在。因此，此子路徑主動選取算法仍然有待優(yōu)化并輔以其他算法相配合。
（二）備用路徑優(yōu)先選取算法
在一切特定的網(wǎng)絡(luò)環(huán)境中，3.1中的主動子路徑選取算法選出的子路徑也許并不能構(gòu)成一條完整的路徑。因此產(chǎn)生了與之相對的另一種算法來優(yōu)先尋找備用路徑，然后通過備用路徑來找到對應(yīng)的路徑。
這種算法的原理是嘗試在移除了所有必經(jīng)點及其相關(guān)路徑的有向圖中尋找備用路徑。首先根據(jù)已有的班得瑞算法[11]生成具有最短權(quán)重和的盡量包含最多節(jié)點并且節(jié)點之間互不相交的路徑。然后對于每一條備用路徑（用q代表其所包含的節(jié)點），在有向圖中移除該備用路徑的中間節(jié)點得到網(wǎng)絡(luò)（V＼（Vq＼{s，t}），A），而后在該網(wǎng)絡(luò)中運用SK算法得出其子路徑。
如果之前的步驟出現(xiàn)問題不能找出子路徑，此時需要重新運用公式（8）和（9）來計算在移除了必經(jīng)點點集Vs中的所有點后的有向圖中的最短備用子路徑，然后針對每一條備用最短子路徑使用SK算法計算出其子路徑，重復此過程路徑被找到。
（三）啟發(fā)式算法的結(jié)合
命名3.1中的主動子路徑選取算法為ASK，3.2中的備用路徑優(yōu)先選取為BSK；對于此類問題首先運用ASK算法，當網(wǎng)絡(luò)環(huán)境特殊使用ASK沒有合適解時在其中加入BSK算法，將此混合算法命名為ABSK。
四、結(jié)果
考慮到不同的網(wǎng)絡(luò)環(huán)境做了兩個不同的實驗測試。第一組網(wǎng)絡(luò)模型來自SNDlib[12]，反映的是真實世界中的網(wǎng)絡(luò)，分別用了newyork，norway，india35，pioro40和germany50的網(wǎng)絡(luò)模型；第二組網(wǎng)絡(luò)使用了Georgia Tech Internetwork Topology Models軟件（GT-ITM）生成模型，包含了5組平均出度為7的500節(jié)點網(wǎng)絡(luò)模型。指定的必經(jīng)節(jié)點數(shù)量定為2個4個或6個，完全隨機分配。在每個網(wǎng)絡(luò)中對于每一組必經(jīng)點點集Vs，隨機生成100對點集，產(chǎn)生20組樣例，并以95%的置信區(qū)間為誤差線標注在之后的圖表上。
實驗結(jié)果的衡量是根據(jù)解決問題數(shù)量的占比百分數(shù)來決定并標注的，以CPLEX求解器計算出的結(jié)果予以對比，來評價本文中啟發(fā)式算法的效率。
五、結(jié)論
在某網(wǎng)絡(luò)中從某一源點經(jīng)過指定的必經(jīng)點點集到達目標節(jié)點的路徑的計算需求隨著網(wǎng)絡(luò)管理約束的豐富而日益增多。整數(shù)線性規(guī)劃（ILP）[8]適用于解決此類問題并且滿足限制子路徑之間互相節(jié)點不相交，但時間成本過高。
根據(jù)本文的實驗結(jié)果不難看出，基于啟發(fā)式算法的主動路徑選擇和備用路徑優(yōu)先選擇算法可以廣泛應(yīng)用于各種復雜的網(wǎng)絡(luò)環(huán)境中，并且在可接受的誤差范圍內(nèi)計算出可行解。相比于整數(shù)線性規(guī)劃算法（ILP），該算法在CPU時間開銷方面具有明顯的優(yōu)勢，可以在網(wǎng)絡(luò)拓撲環(huán)境日益復雜的今天被廣泛應(yīng)用。
參考文獻
[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]林瀾，閆春鋼，等.基于穩(wěn)定分支的變權(quán)網(wǎng)絡(luò)最優(yōu)路徑算法[J].電子學報，2006，34（7）：1222-1225.
[4]曹政才，等.面向城市交通網(wǎng)絡(luò)的一種新型動態(tài)路徑尋優(yōu)方法[J].電子學報，2012，40（10）：2043-2067.
