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