過必經點的最短無環(huán)路徑算法4900字

1、過必經點的最短無環(huán)途徑算法4900字 通過啟發(fā)式算法解決在帶權有向圖中從某一源點經過指定的必經點集到達目的終點且節(jié)點不重復的最短無環(huán)途徑問題。隨著復雜網絡優(yōu)化問題的不斷凸顯，對網絡分析算法的性能要求也日漸升高。經過必經點的最短無環(huán)途徑問題的復雜度不亞于旅行商問題TSP，但并沒有獲得廣泛的關注。近些年來出現(xiàn)了一種高效的整數(shù)線性規(guī)劃公式ILP來解決此類問題，這種ILP算法適用于有節(jié)點不相交約束的最短途徑問題，但是實驗說明在大型復雜網絡中這種算法的時間開銷過高。因此有了本論文的三種啟發(fā)式算法，大量的實驗說明這些算法在大多數(shù)情況下都能在可承受的時間范圍內找出合理解，這些解與最優(yōu)解的誤差都在可承受的范圍

2、內，后續(xù)的CPU開銷數(shù)據(jù)也說明此類啟發(fā)式算法的資源消耗遠小于整數(shù)線性規(guī)劃ILP算法。 彈性路由 最短途徑問題 必經點作為社會關鍵根底設施，通信網絡的可伸縮性和生命力是非常重要的。參見通信網絡中的彈性和生命力構造性框架。根據(jù)路由途徑約束的等級，其通過約束途徑來尋找節(jié)點或邊不重復的路由，在某些情況下所尋求的途徑必須滿足經過指定的必經點點集的約束，這些必經點可能是基于某種特性比方高可靠性被選出的，也可能是根據(jù)基于運營商之間協(xié)議所產生的參數(shù)來決定的，或者是由于其他網絡管理的約束條件所制定的。針對諸如此類從某一源點經過一系列給定的必經點到達另一終點的最短途徑計算問題的算法少之又少，的最早的算法是由Sak

3、sena和Kumar提出的，他們嘗試運用最正確性原理開發(fā)出一種準確算法來計算經過指定點集的最短途徑問題途徑可能有環(huán)?？紤]到時間復雜度，Dreyfus在中指出，從某一源點經過必經點點集到目的節(jié)點的最短途徑算法可能有環(huán)路的時間復雜度并不亞于k維旅行商問題TSP，這里k-2代表必經點的個數(shù)。Andrade也提出，假如必經點點集是由有向圖中除源點和終點外的所有節(jié)點構成的，此類問題相當于尋找最短權重的漢密爾頓通路，屬于NP-困難問題。文章的其余部分構造如下。第一部分介紹了該問題模型的數(shù)學公式和數(shù)學方法。第二部分著重表達了計算經過必經點的最短無環(huán)途徑的啟發(fā)式算法，包括最早的SK66算法，以及SK66算法的

4、修正版算法。第三部分描繪了針對此類最短途徑問題的三種變體型啟發(fā)式算法。第四部分為實驗數(shù)據(jù)結果。第五部分為總結。一、數(shù)學模型對該問題的數(shù)學建模旨在尋找經過給定必經點點集的無環(huán)最短途徑，并且滿足要求途徑上沒有交點。一條無環(huán)途徑上每個節(jié)點只能經過一次，因此所有的途徑都必須是不存在環(huán)路的。一數(shù)學符號在本文第二及第三部分用了如下數(shù)學定義。定義有向圖G=V，A，其中點集V=v1，.，vn，有向邊集A=a1，am。定義假如vi，vjV，并且vi=vj，ak=vi，vjA，那么vi為邊尾vj為邊頭。邊vi，vj定義為從點vi到vj的途徑。邊vi，vj和邊vj，vi為對稱邊。一條途徑定義為從源點s開場的到終點t

5、的一個不同點組成的連續(xù)序列，s，tV，將其定義為p=，其中vi，vi+1A，？坌i1，k-1，k為該途徑中節(jié)點的個數(shù)。由Vp代表途徑p中所有點的點集，Ap代表途徑上所有邊的邊集合，Ap=？坌i1，.，k-1vi，vi+1。經過一條邊vi，vjA的花費權重定義為wvi，vj，假設為大于0的正數(shù)。一條途徑的權重為途徑上所有邊權重的代數(shù)和，Dp=vi，vjAp wvi，vj。假如兩點之間不存在通路，那么定義其權重為無窮。二、過指定必經點的最短途徑最初的SK66算法，雖然不能保證計算出最優(yōu)途徑，但是其時間復雜度與必經點點集|Vs|的規(guī)模成正比；在初始化階段首先計算|Vs|+2|Vs|個最短途徑；在之后

6、的每一步需要|Vs|2次計算，該步驟中大部分的時間開銷花費在節(jié)點計算過程中，其最差時間復雜度為|V|log2|V|；因此，SK66算法的最差時間復雜度為O|Vs+2|2|A|log2|V|+|Vs|2|V|log2|V|，其中假設最短子途徑計算是基于二叉堆的Dijkstra算法。一Saksena和Kumar提出的算法SK66SK66算法通過在每一次子途徑的選擇中找出當前最短途徑，計算出從某一源點到另一終點并且經過制定必經點點集的最終最短途徑可能存環(huán)路。算法的初始化步驟為：1計算出必經點點集|Vs|中任意兩點的最短間隔 沒有任何限制，和源點s到點集中每一點的最短間隔 ；2計算出必經點點集Vs中每

7、一點到終點的最短間隔 。假定Dvi，vl代表從點vi到vl的最短途徑花費，其中viVs s并且vlVs，f0vi代表從一點viVs到終點t的最短途徑花費。二SK66算法改良版此部分算法為SK66算法的改良版本，它可以保證所獲得的途徑是不含環(huán)路的，并且進步了原始算法的性能。此改良版本的算法犧牲了一定空間來同時存儲更多的中間子途徑，來換取時間上的充裕，這種算法暫命名為SK。為了保證獲得的途徑是無環(huán)的，每一次迭代12和11進展時必須嚴格保證迭代獲得的子途徑不含環(huán)路。根據(jù)上述公式，在SK66算法的每一次迭代中，對于每一個必經點集Vs中的點vi都要選出一個新的中間點vlvlVs放到途徑中。SK66的這個

8、步驟在尋找部分最優(yōu)途徑時也許會提早因為更高的權重而排除掉本身最優(yōu)途徑解的子途徑，因為部分最優(yōu)并不是全局最優(yōu)解，并且可能造成之后的必經節(jié)點無法到達的窘境。此算法主要的改良在于，在每一次迭代尋找vi到終點t的中間節(jié)點vl時，同時保存所有可能的中間點vl，而不是像SK66中一樣尋找間隔 最近的中間節(jié)點vl，因此在此改良版本的算法中每一步的迭代需要保存|Vs|-1條途徑。 三、保證途徑上沒有節(jié)點相交的變體型啟發(fā)式算法此部分著重介紹用于尋找經過指定必經點點集并且滿足約束條件途徑上節(jié)點互不相交的最短途徑的兩種不同的算法。一主動子途徑選取算法在此部分著重介紹一種基于2.2章節(jié)SK算法的新算法，它在執(zhí)行SK算

9、法每一步的迭代過程中，每一次尋找子途徑時都參加了嚴格的限制來確保所獲得的子途徑與將來的最終途徑之間是沒有相交節(jié)點的。然而這個過程并不能保證最終當所尋找的子途徑聯(lián)結起來時能形成一條從s到t的最短途徑。此算法的初始步驟為：1運用算法8和9，最多可以得到條其中=|A|/|V|2 |VS|該有向圖中的最短途徑vi，vj，其中viVS s，vjVS；假設尋找到第k條最短途徑Pijk=1，時，在圖中移除掉點集VpijVss之后仍能使源點s到終點t連通，此時尋找過程停頓并保存途徑Pij。2運用算法8和9，最多可以得到從節(jié)點vi到終點t的條其中=|A|/|V|2|Vs|該有向圖中的最短途徑vi，t，其中viV

10、s；假設尋找到第k條最短途徑Pitk=1，時，在圖中移除掉點集VpitVst之后仍能使源點s到終點t連通，此時尋找過程停頓并保存途徑Pit。然后運用SK算法并在每一次迭代中另參加限制，保證去掉子途徑的節(jié)點VsVPitt時源點s到終點t始終可以保持連通；類似的，在最后一步中，只有每一段無環(huán)子途徑之間互相節(jié)點不相交才能保證最終從s到t途徑的存在。算法的最后一步選擇中首先使用了13，并且參加限制途徑必須是無環(huán)并且互相之間節(jié)點不相交的。假如一段子途徑p，可以使從源點s到某一點vl的子途徑與從vl到終點t的子途徑結合并且不存在環(huán)路，接下來需要驗證這條結合途徑是否有從s到t的備用節(jié)點不相交途徑。需要注意的

11、是，雖然保證了每一段子途徑都是從s到t的節(jié)點不相交途徑，但這并不代表最終途徑的存在。因此，此子途徑主動選取算法仍然有待優(yōu)化并輔以其他算法相配合。二備用途徑優(yōu)先選取算法在一切特定的網絡環(huán)境中，3.1中的主動子途徑選取算法選出的子途徑也許并不能構成一條完好的途徑。因此產生了與之相對的另一種算法來優(yōu)先尋找備用途徑，然后通過備用途徑來找到對應的途徑。這種算法的原理是嘗試在移除了所有必經點及其相關途徑的有向圖中尋找備用途徑。首先根據(jù)已有的班得瑞算法11生成具有最短權重和的盡量包含最多節(jié)點并且節(jié)點之間互不相交的途徑。然后對于每一條備用途徑用q代表其所包含的節(jié)點，在有向圖中移除該備用途徑的中間節(jié)點得到網絡V

12、Vqs，t，A，而后在該網絡中運用SK算法得出其子途徑。假如之前的步驟出現(xiàn)問題不能找出子途徑，此時需要重新運用公式8和9來計算在移除了必經點點集Vs中的所有點后的有向圖中的最短備用子途徑，然后針對每一條備用最短子途徑使用SK算法計算出其子途徑，重復此過程途徑被找到。三啟發(fā)式算法的結合命名3.1中的主動子途徑選取算法為ASK，3.2中的備用途徑優(yōu)先選取為BSK；對于此類問題首先運用ASK算法，當網絡環(huán)境特殊使用ASK沒有適宜解時在其中參加BSK算法，將此混合算法命名為ABSK。四、結果考慮到不同的網絡環(huán)境做了兩個不同的實驗測試。第一組網絡模型來自SNDlib12，反映的是真實世界中的網絡，分別用

13、了newyork，norway，india35，pioro40和germany50的網絡模型；第二組網絡使用了Georgia Tech Internetwork Topology Models軟件GT-ITM生成模型，包含了5組平均出度為7的500節(jié)點網絡模型。指定的必經節(jié)點數(shù)量定為2個4個或6個，完全隨機分配。在每個網絡中對于每一組必經點點集Vs，隨機生成100對點集，產生20組樣例，并以95%的置信區(qū)間為誤差線標注在之后的圖表上。實驗結果的衡量是根據(jù)解決問題數(shù)量的占比百分數(shù)來決定并標注的，以CPLEX求解器計算出的結果予以比照，來評價本文中啟發(fā)式算法的效率。五、結論在某網絡中從某一源點經過

14、指定的必經點點集到達目的節(jié)點的途徑的計算需求隨著網絡管理約束的豐富而日益增多。整數(shù)線性規(guī)劃ILP8適用于解決此類問題并且滿足限制子途徑之間互相節(jié)點不相交，但時間本錢過高。根據(jù)本文的實驗結果不難看出，基于啟發(fā)式算法的主動途徑選擇和備用途徑優(yōu)先選擇算法可以廣泛應用于各種復雜的網絡環(huán)境中，并且在可承受的誤差范圍內計算出可行解。相比于整數(shù)線性規(guī)劃算法ILP，該算法在CPU時間開銷方面具有明顯的優(yōu)勢，可以在網絡拓撲環(huán)境日益復雜的今天被廣泛應用。參考文獻1J.P.Sterbenz，D.Hutchison，E.K.C？etinkaya，A.Jabbar，J.P.Rohrer， M.Scholler，and P.Smith，“Resilience and survivability in muni- cation networks：Strategies，principles，and survey of disciplines，p