關(guān)于過必經(jīng)點(diǎn)的最短無環(huán)路徑算法

《關(guān)于過必經(jīng)點(diǎn)的最短無環(huán)路徑算法》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫(kù)。

1、關(guān)于過必經(jīng)點(diǎn)的最短無環(huán)路徑算法導(dǎo)讀：現(xiàn)在請(qǐng)大家鑒賞的文章是路徑和算法方面的畢業(yè)論文題目。本篇文章有利于同專業(yè)方向的大學(xué)碩士研究生和本科生在寫作畢業(yè)論文范文前寫作和查找資料有清晰思路。（遼金融職業(yè)學(xué)院，遼沈陽(yáng)110122）【摘要】通過啟發(fā)式算法解決帶權(quán)有向圖中從某一源點(diǎn)經(jīng)過指定的必經(jīng)點(diǎn)集到達(dá)目標(biāo)終點(diǎn)且節(jié)點(diǎn)不重復(fù)的最短無環(huán)路徑問題.隨著復(fù)雜X絡(luò)優(yōu)化問題的不斷凸顯，對(duì)X絡(luò)分析算法的性能要求也日漸升高.經(jīng)過必經(jīng)點(diǎn)的最短無環(huán)路徑問題的復(fù)雜度不亞于旅行商問題（TSP），但沒有獲得廣泛的關(guān)注.近些年來出現(xiàn)了一種高效的整數(shù)線性規(guī)劃公式（ILP）來解決此類問題

2、，這種ILP算法適用于有節(jié)點(diǎn)不相交約束的最短路徑問題，但是實(shí)驗(yàn)表明大型復(fù)雜X絡(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)作為社會(huì)關(guān)鍵基礎(chǔ)設(shè)施，通信X絡(luò)的伸縮性和生命力是十分重要的.參見通信X絡(luò)中的彈性和生命力結(jié)構(gòu)性框架.根據(jù)路由路徑約束的等級(jí)，其通過約束路徑來尋找節(jié)點(diǎn)（或邊）不重復(fù)的路由，某些情況下尋求的路徑必須

3、滿足經(jīng)過指定的必經(jīng)點(diǎn)點(diǎn)集的約束，這些必經(jīng)點(diǎn)能是基于某種特性（比高靠性）被選出的，也能是根據(jù)基于運(yùn)營(yíng)商間協(xié)議產(chǎn)生的參數(shù)來決定的，或者是由于其他X絡(luò)管理的約束條件制定的.針對(duì)諸此類從某一源點(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），這里k2代表

4、必經(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算法的修正版算法.第三部分描述了針對(duì)此類最短路徑問題的三種變體型啟發(fā)式算法.第四部分為實(shí)驗(yàn)數(shù)據(jù)結(jié)果.第五部分為總結(jié).一、數(shù)學(xué)模型對(duì)該問題的數(shù)學(xué)建模旨尋找經(jīng)過給定必經(jīng)點(diǎn)點(diǎn)集的無環(huán)最短路徑，且滿足要求路徑上沒有交點(diǎn).一條無環(huán)路徑上每個(gè)節(jié)點(diǎn)只

5、能經(jīng)過一次，此有的路徑都必須是不存環(huán)路的.(一)數(shù)學(xué)符號(hào)二、過指定必經(jīng)點(diǎn)的最短路徑最初的SK66算法，雖然不能保證計(jì)算出最優(yōu)路徑，但是其時(shí)間復(fù)雜度與必經(jīng)點(diǎn)點(diǎn)集（

6、Vs

7、）的規(guī)模成正比初始化階段首先計(jì)算(

8、Vs

9、+2)

10、Vs

11、個(gè)最短路徑后的每一步需要

12、Vs

13、2次計(jì)算，該步驟中大部分的時(shí)間開銷花費(fèi)節(jié)點(diǎn)計(jì)算過程中，其最差時(shí)間復(fù)雜度為

14、V

15、log2

16、V

17、;此，SK66算法的最差時(shí)間復(fù)雜度為O(

18、Vs+2

19、2

20、A

21、log2

22、V

23、+

24、Vs

25、2

26、V

27、log2

28、V

29、)，其中假設(shè)最短子路徑計(jì)算是基于二叉堆的Dijkstra算法.(一)Saksena和Kumar

30、提出的算法（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)集

31、Vs

32、中任意兩點(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).于是該算法以迭代地表示為：其中η=1，2，…，

33、本篇關(guān)于過必經(jīng)點(diǎn)的最短無環(huán)路徑算法論

34、文范文綜合參考評(píng)定下度:優(yōu)質(zhì)題目Vs

35、1，每一次迭代經(jīng)尋得的路徑上新加入指定點(diǎn)集中距離當(dāng)前vi路徑最近的一點(diǎn)，且算法中每一次從點(diǎn)vi經(jīng)過新的一點(diǎn)vl到終點(diǎn)t的路徑（能包含環(huán)路）的尋找過程中必須保證剩余必經(jīng)點(diǎn)點(diǎn)集中不包含經(jīng)經(jīng)過的節(jié)點(diǎn)vi.(二)SK66算法改進(jìn)版此部分算法為SK66算法的改進(jìn)版本，以保證獲得的路徑是不含環(huán)路的，且提高了原始算法的性能.此改進(jìn)版本的算法犧牲了一定空間來時(shí)存儲(chǔ)更多的中間子路徑，來?yè)Q取時(shí)間上的充裕，這種算法暫命名為SK.為了保證獲得的路徑是無環(huán)的，每一次迭代（12）和（11）進(jìn)行時(shí)必須嚴(yán)格保證迭代獲得的子路徑不含環(huán)路.

36、根據(jù)上述公式，SK66算法的每一次迭代中，對(duì)于每一個(gè)必經(jīng)點(diǎn)集Vs中的點(diǎn)vi都要選出一個(gè)新的中間點(diǎn)vl（vl∈Vs）放到路徑中.SK66的這個(gè)步驟尋找局部最優(yōu)路徑時(shí)也