余英瀚

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

【關(guān)鍵詞】彈性路由 最短路徑問題 必經(jīng)點(diǎn)

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

考慮到時(shí)間復(fù)雜度，Dreyfus在中指出，從某一源點(diǎn)經(jīng)過必經(jīng)點(diǎn)點(diǎn)集到目標(biāo)節(jié)點(diǎn)的最短路徑算法（可能有環(huán)路）的時(shí)間復(fù)雜度并不亞于k維旅行商問題（TSP），這里k-2代表必經(jīng)點(diǎn)的個(gè)數(shù)。Andrade也提出，如果必經(jīng)點(diǎn)點(diǎn)集是由有向圖中除源點(diǎn)和終點(diǎn)外的所有節(jié)點(diǎn)構(gòu)成的，此類問題相當(dāng)于尋找最短權(quán)重的漢密爾頓通路，屬于NP-困難問題。

文章的其余部分結(jié)構(gòu)如下。第一部分介紹了該問題模型的數(shù)學(xué)公式和數(shù)學(xué)方法。第二部分著重?cái)⑹隽擞?jì)算經(jīng)過必經(jīng)點(diǎn)的最短無環(huán)路徑的啟發(fā)式算法，包括最早的SK66算法，以及SK66算法的修正版算法。第三部分描述了針對此類最短路徑問題的三種變體型啟發(fā)式算法。第四部分為實(shí)驗(yàn)數(shù)據(jù)結(jié)果。第五部分為總結(jié)。

一、數(shù)學(xué)模型

對該問題的數(shù)學(xué)建模旨在尋找經(jīng)過給定必經(jīng)點(diǎn)點(diǎn)集的無環(huán)最短路徑，并且滿足要求路徑上沒有交點(diǎn)。一條無環(huán)路徑上每個(gè)節(jié)點(diǎn)只能經(jīng)過一次，因此所有的路徑都必須是不存在環(huán)路的。

（一）數(shù)學(xué)符號

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

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

二、過指定必經(jīng)點(diǎn)的最短路徑

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

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

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

（1）計(jì)算出必經(jīng)點(diǎn)點(diǎn)集|Vs|中任意兩點(diǎn)的最短距離（沒有任何限制），和源點(diǎn)s到點(diǎn)集中每一點(diǎn)的最短距離；

（2）計(jì)算出必經(jīng)點(diǎn)點(diǎn)集Vs中每一點(diǎn)到終點(diǎn)的最短距離。

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

（二）SK66算法改進(jìn)版

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

為了保證獲得的路徑是無環(huán)的，每一次迭代（12）和（11）進(jìn)行時(shí)必須嚴(yán)格保證迭代獲得的子路徑不含環(huán)路。

根據(jù)上述公式，在SK66算法的每一次迭代中，對于每一個(gè)必經(jīng)點(diǎn)集Vs中的點(diǎn)vi都要選出一個(gè)新的中間點(diǎn)vl（vl∈Vs）放到路徑中。SK66的這個(gè)步驟在尋找局部最優(yōu)路徑時(shí)也許會提前因?yàn)楦叩臋?quán)重而排除掉本身最優(yōu)路徑解的子路徑，因?yàn)榫植孔顑?yōu)并不是全局最優(yōu)解，并且可能造成之后的必經(jīng)節(jié)點(diǎn)無法到達(dá)的窘境。此算法主要的改進(jìn)在于，在每一次迭代η尋找vi到終點(diǎn)t的中間節(jié)點(diǎn)vl時(shí)，同時(shí)保留所有可能的中間點(diǎn)vl，而不是像SK66中一樣尋找距離最近的中間節(jié)點(diǎn)vl，因此在此改進(jìn)版本的算法中每一步的迭代需要保留|Vs|-1條路徑。

三、保證路徑上沒有節(jié)點(diǎn)相交的變體型啟發(fā)式算法

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

（一）主動(dòng)子路徑選取算法

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

此算法的初始步驟為：

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

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

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

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

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

（二）備用路徑優(yōu)先選取算法

在一切特定的網(wǎng)絡(luò)環(huán)境中，3.1中的主動(dòng)子路徑選取算法選出的子路徑也許并不能構(gòu)成一條完整的路徑。因此產(chǎn)生了與之相對的另一種算法來優(yōu)先尋找備用路徑，然后通過備用路徑來找到對應(yīng)的路徑。

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

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

（三）啟發(fā)式算法的結(jié)合

命名3.1中的主動(dòng)子路徑選取算法為ASK，3.2中的備用路徑優(yōu)先選取為BSK；對于此類問題首先運(yùn)用ASK算法，當(dāng)網(wǎng)絡(luò)環(huán)境特殊使用ASK沒有合適解時(shí)在其中加入BSK算法，將此混合算法命名為ABSK。

四、結(jié)果

考慮到不同的網(wǎng)絡(luò)環(huán)境做了兩個(gè)不同的實(shí)驗(yàn)測試。第一組網(wǎng)絡(luò)模型來自SNDlib[12]，反映的是真實(shí)世界中的網(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é)點(diǎn)網(wǎng)絡(luò)模型。指定的必經(jīng)節(jié)點(diǎn)數(shù)量定為2個(gè)4個(gè)或6個(gè)，完全隨機(jī)分配。在每個(gè)網(wǎng)絡(luò)中對于每一組必經(jīng)點(diǎn)點(diǎn)集Vs，隨機(jī)生成100對點(diǎn)集，產(chǎn)生20組樣例，并以95%的置信區(qū)間為誤差線標(biāo)注在之后的圖表上。

實(shí)驗(yàn)結(jié)果的衡量是根據(jù)解決問題數(shù)量的占比百分?jǐn)?shù)來決定并標(biāo)注的，以CPLEX求解器計(jì)算出的結(jié)果予以對比，來評價(jià)本文中啟發(fā)式算法的效率。

五、結(jié)論

在某網(wǎng)絡(luò)中從某一源點(diǎn)經(jīng)過指定的必經(jīng)點(diǎn)點(diǎn)集到達(dá)目標(biāo)節(jié)點(diǎn)的路徑的計(jì)算需求隨著網(wǎng)絡(luò)管理約束的豐富而日益增多。整數(shù)線性規(guī)劃（ILP）[8]適用于解決此類問題并且滿足限制子路徑之間互相節(jié)點(diǎn)不相交，但時(shí)間成本過高。

根據(jù)本文的實(shí)驗(yàn)結(jié)果不難看出，基于啟發(fā)式算法的主動(dòng)路徑選擇和備用路徑優(yōu)先選擇算法可以廣泛應(yīng)用于各種復(fù)雜的網(wǎng)絡(luò)環(huán)境中，并且在可接受的誤差范圍內(nèi)計(jì)算出可行解。相比于整數(shù)線性規(guī)劃算法（ILP），該算法在CPU時(shí)間開銷方面具有明顯的優(yōu)勢，可以在網(wǎng)絡(luò)拓?fù)洵h(huán)境日益復(fù)雜的今天被廣泛應(yīng)用。

參考文獻(xiàn)

[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]王實(shí)，高文.增強(qiáng)型樸索貝葉斯學(xué)習(xí)[J].計(jì)算機(jī)科學(xué)，2000，27（4）；46-49.

[3]林瀾，閆春鋼，等.基于穩(wěn)定分支的變權(quán)網(wǎng)絡(luò)最優(yōu)路徑算法[J].電子學(xué)報(bào)，2006，34（7）：1222-1225.

[4]曹政才，等.面向城市交通網(wǎng)絡(luò)的一種新型動(dòng)態(tài)路徑尋優(yōu)方法[J].電子學(xué)報(bào)，2012，40（10）：2043-2067.