最短路徑算法分類與應(yīng)用研究(編輯修改稿)
2024-07-23 06:04 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 成樹(shù)；（2）無(wú)向圖(有向圖的是最小樹(shù)形圖)；（3）多用于稠密圖。算法描述：設(shè)圖G =（V，E），其生成樹(shù)的頂點(diǎn)集合為U。（1）把v0放入U(xiǎn)；（2）在所有u∈U，v∈VU的邊(u，v)∈E中找一條最小權(quán)值的邊，加入生成樹(shù)；（3）把（2）找到的邊的v加入U(xiǎn)集合。如果U集合已有n個(gè)元素，則結(jié)束，否則繼續(xù)執(zhí)行（2）。算法實(shí)現(xiàn)：（1）集合：設(shè)置一個(gè)數(shù)組set(i=0,1,..,n1)，初始值為0，代表對(duì)應(yīng)頂點(diǎn)不在集合中（注意：頂點(diǎn)號(hào)與下標(biāo)號(hào)差1)；（2）圖用鄰接陣表示，路徑不通用無(wú)窮大表示，在計(jì)算機(jī)中可用一個(gè)大整數(shù)代替；（3）具體程序見(jiàn)參考文獻(xiàn)[12]。八、Kruskal算法適用范圍：（1）MST(MinimumSpanningTree,最小生成樹(shù))；（2）無(wú)向圖(有向圖的是最小樹(shù)形圖)；（3）多用于稀疏圖；（4）邊已經(jīng)按權(quán)值排好序給出。算法描述：（1）將邊按非降序排列；（2）While合并次數(shù)少于|V|1①取一條邊(u,v)(因?yàn)橐呀?jīng)排序，所以必為最小)②Ifu,v不屬于同一連通分量then,v所在的連通分量(u,v)；tot=tot+W(u,v)（3）算法結(jié)束：tot為MST的總權(quán)值。算法實(shí)現(xiàn)：見(jiàn)參考文獻(xiàn)[13]。九、Johnson算法適用范圍：Johnson算法適用于求All Pairs Shortest Path。算法實(shí)現(xiàn)：Johnson算法應(yīng)用了重標(biāo)號(hào)技術(shù)（1）先進(jìn)行一次BellmanFord算法；（2）然后對(duì)原圖進(jìn)行重標(biāo)號(hào)，w39。(i,j)=h[i]h[j]+w(i,j)；（3）然后對(duì)每個(gè)點(diǎn)進(jìn)行一次Dijkstra。第三章 最短路徑算法應(yīng)用一、TSP問(wèn)題的介紹TSP問(wèn)題，即旅行商問(wèn)題，是一種典型的組合最優(yōu)化問(wèn)題，可描述為某旅行商欲往n個(gè)城市推銷貨物，從某個(gè)城市出發(fā)，沿途經(jīng)過(guò)各個(gè)城市一次后返回出發(fā)城市，要確定一條行走的路線，計(jì)算途徑n個(gè)城市的最短距離，即給定ｎ個(gè)城市和兩兩城市之間的距離，確定一條經(jīng)過(guò)每個(gè)城市并且僅經(jīng)過(guò)一次的路線，要求總路徑最短。TSP分為2類，即對(duì)稱TSP和不對(duì)稱TSP。對(duì)于城市數(shù)目為n的地圖, 共有n種不同的路徑。城市越多,可能的路徑也越多。而且路徑的增加速度非?？烨沂欠蔷€形的。當(dāng)n很大時(shí)，去嘗試每一種可能的路徑是不可能的，所以需要設(shè)計(jì)一個(gè)有效的算法去尋找最短的路徑。二、TSP問(wèn)題算法的介紹貪心算法貪心算法的主要思想是永遠(yuǎn)選擇當(dāng)前最短的路徑。這是解決TSP問(wèn)題的最簡(jiǎn)便的算法。貪心算法容易實(shí)現(xiàn)但是效率不好。如下圖所示:有4個(gè)城市:A，B，C和D。距離從A到B是5公里，A到C是6公里，A到D是9公里，B到C是3公里, B到D是7公里，C到D是8公里。假設(shè)我們一開(kāi)始在A，比較A到其他點(diǎn)的路徑長(zhǎng)度，找出A到B是最短的路徑(5公里)。我們從A到B，然后設(shè)定A和B之間的距離無(wú)限大。在B我們找出B到C(3公里)是最短的路徑。如此然后去C，再到D。所以，此算法則總是選擇最短的路徑。模擬退火算法模擬退火算法是一種求解大規(guī)模組合優(yōu)化問(wèn)題的方法，對(duì)于NP完全組合優(yōu)化問(wèn)題尤其有效。模擬退火算法來(lái)源于固體退火原理，將固體加溫至充分高，再讓其緩慢降溫(即退火)，使之達(dá)到能量最低點(diǎn)。反之，如果急速降溫(即淬火)則不能達(dá)到最低點(diǎn)。加溫時(shí), 固體內(nèi)部粒子隨溫升變?yōu)闊o(wú)序狀，內(nèi)能增大，而緩慢降溫時(shí)粒子漸趨有序，在每個(gè)溫度上都達(dá)到平衡態(tài)，最后在常溫時(shí)達(dá)到基態(tài)，內(nèi)能減為最小。根據(jù)Metropolis準(zhǔn)則，粒子在溫度T時(shí)趨于平衡的概率為exp( E/(kT)), 其中E為溫度T時(shí)的內(nèi)能，E為其改變量，k為Boltzman常數(shù)。用固體退火模擬組合優(yōu)化問(wèn)題，將內(nèi)能E模擬為目標(biāo)函數(shù)值f，溫度T演化成控制參數(shù)t，即得到解組合優(yōu)化問(wèn)題的模擬退火算法: 由初始解i和控制參數(shù)初值t開(kāi)始，對(duì)當(dāng)前解重復(fù)產(chǎn)生“新解→計(jì)算目標(biāo)函數(shù)差→接受或舍棄”的迭代，并逐步衰減t值, 算法終止時(shí)的當(dāng)前解即為所得近似最優(yōu)解。所以我們可以通過(guò)上面的思想寫(xiě)出解決TSP問(wèn)題的模擬退火算法。步驟如下:（1）初始化: 初始溫度T(充分大), 初始解狀態(tài)s(隨機(jī)選取一條TSP路線, 算出走完此路線的長(zhǎng)度Cost(s)作為評(píng)價(jià)函數(shù), 這是算法迭代的起點(diǎn)), 每個(gè)T值的迭代次數(shù)L；（2）對(duì)k=1至k=L做第(3)至第(6)步；（3）產(chǎn)生新解 ( 一般利用2opt算法來(lái)產(chǎn)生新的路徑)；（4）計(jì)算增量Cost=Cost() Cost(s)，其中Cost(s)為評(píng)價(jià)函數(shù)；（5）若則接受作為新的當(dāng)前解, 否則以概率exp(/T)接受作為新當(dāng)前解；（6）如果滿足終止條件則輸出當(dāng)前解作為最優(yōu)解, 結(jié)束程序。終止條件通常取為連續(xù)若干個(gè)新解都沒(méi)有被接受時(shí)終止算法；（7）T逐漸減少，且T趨于0，然后轉(zhuǎn)第2步運(yùn)算。遺傳序列算法遺傳算法簡(jiǎn)稱GA(Genetic Algorithm), 在本質(zhì)上是一種不依賴具體問(wèn)題的直接搜索方法。遺傳算法GA把問(wèn)題的解表示成“染色體”，在算法中也即是以二進(jìn)制編碼的串。并且，在執(zhí)行遺傳算法之前，給出一群“ 染色體”， 也即是假設(shè)解。然后, 把這些假設(shè)解置于問(wèn)題的“ 環(huán)境”中, 并按適者生存的原則，從中選擇出較適應(yīng)環(huán)境的“ 染色體”進(jìn)行復(fù)制，再通過(guò)交叉，變異過(guò)程產(chǎn)生更適應(yīng)環(huán)境的新一代“ 染色體”群。這樣，一代一代地進(jìn)化，最后就會(huì)收斂到最適應(yīng)環(huán)境的一個(gè)“ 染色體”上，它就是問(wèn)題的最優(yōu)解。步驟如下:（1) 產(chǎn)生一群染色體(不同的游歷路徑) 然后計(jì)算評(píng)估每個(gè)染色體的健壯度(總路徑長(zhǎng)度)。（2) 選留健壯度較好的染色體(總路徑較短的路徑)，剩下的作為父染色體；（3) 父染色體交換, 倒轉(zhuǎn)或移位產(chǎn)生下一代染色體(其中有5%的染色體變異的概率)；（4) 在下一代染色體的基礎(chǔ)上回到第（1）步驟；（5) 循環(huán)整個(gè)程序多次，記錄下每代的最好的染色體；（6) 選擇其中最優(yōu)秀的染色體作為最優(yōu)解。
語(yǔ)文相關(guān)推薦
鄂ICP備17016276號(hào)-1