最短路徑算法分類與應(yīng)用研究-文庫(kù)吧資料
2025-07-02 06:04本頁(yè)面
【正文】 for i=1:(ceil(m/n))Randpos=[Randpos,randperm(n)]。 L_ave=zeros(NC_max,1)。 R_best=zeros(NC_max,n)。 Tabu=zeros(m,n)。endendEta=1./D。elseD(i,j)=eps。 D=zeros(n,n)。 第五步：輸出最后結(jié)果。第四步：往復(fù)迭代計(jì)算，直到達(dá)到最大迭代次數(shù)。第三步：繼續(xù)迭代，直到第三次，得到。 第二步：用蟻群算法迭代一次，得出一個(gè)最優(yōu)解，由此來(lái)計(jì)算出和的大小。至此，一個(gè)螞蟻的循環(huán)過(guò)程結(jié)束，由此反復(fù)迭代多次，最終得出優(yōu)化結(jié)果。為了阻止螞蟻重復(fù)訪問(wèn)，為每只螞蟻都設(shè)計(jì)一個(gè)被稱為禁忌表（tabu list）的數(shù)據(jù)結(jié)構(gòu)。在初始時(shí)刻，各條路徑上的信息素量相等，設(shè)，（為常數(shù)），螞蟻被隨機(jī)放到某個(gè)城市，然后根據(jù)各條路徑上的信息素量選擇下一個(gè)城市。（2) 選留健壯度較好的染色體(總路徑較短的路徑)，剩下的作為父染色體；（3) 父染色體交換, 倒轉(zhuǎn)或移位產(chǎn)生下一代染色體(其中有5%的染色體變異的概率)；（4) 在下一代染色體的基礎(chǔ)上回到第（1）步驟；（5) 循環(huán)整個(gè)程序多次，記錄下每代的最好的染色體；（6) 選擇其中最優(yōu)秀的染色體作為最優(yōu)解。這樣，一代一代地進(jìn)化，最后就會(huì)收斂到最適應(yīng)環(huán)境的一個(gè)“ 染色體”上，它就是問(wèn)題的最優(yōu)解。并且，在執(zhí)行遺傳算法之前，給出一群“ 染色體”， 也即是假設(shè)解。遺傳序列算法遺傳算法簡(jiǎn)稱GA(Genetic Algorithm), 在本質(zhì)上是一種不依賴具體問(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é)束程序。用固體退火模擬組合優(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)解。加溫時(shí), 固體內(nèi)部粒子隨溫升變?yōu)闊o(wú)序狀，內(nèi)能增大，而緩慢降溫時(shí)粒子漸趨有序，在每個(gè)溫度上都達(dá)到平衡態(tài)，最后在常溫時(shí)達(dá)到基態(tài)，內(nèi)能減為最小。模擬退火算法來(lái)源于固體退火原理，將固體加溫至充分高，再讓其緩慢降溫(即退火)，使之達(dá)到能量最低點(diǎn)。所以，此算法則總是選擇最短的路徑。在B我們找出B到C(3公里)是最短的路徑。假設(shè)我們一開(kāi)始在A，比較A到其他點(diǎn)的路徑長(zhǎng)度，找出A到B是最短的路徑(5公里)。如下圖所示:有4個(gè)城市:A，B，C和D。這是解決TSP問(wèn)題的最簡(jiǎn)便的算法。當(dāng)n很大時(shí)，去嘗試每一種可能的路徑是不可能的，所以需要設(shè)計(jì)一個(gè)有效的算法去尋找最短的路徑。城市越多,可能的路徑也越多。TSP分為2類，即對(duì)稱TSP和不對(duì)稱TSP。(i,j)=h[i]h[j]+w(i,j)；（3）然后對(duì)每個(gè)點(diǎn)進(jìn)行一次Dijkstra。九、Johnson算法適用范圍：Johnson算法適用于求All Pairs Shortest Path。u,v不屬于同一連通分量then,v所在的連通分量(u,v)；tot=tot+W(u,v)（3）算法結(jié)束：tot為MST的總權(quán)值。Tree,最小生成樹(shù))；（2）無(wú)向圖(有向圖的是最小樹(shù)形圖)；（3）多用于稀疏圖；（4）邊已經(jīng)按權(quán)值排好序給出。八、Kruskal算法適用范圍：（1）MST(Minimum如果U集合已有n個(gè)元素，則結(jié)束，否則繼續(xù)執(zhí)行（2）。算法描述：設(shè)圖G =（V，E），其生成樹(shù)的頂點(diǎn)集合為U。算法實(shí)現(xiàn)：見(jiàn)參考文獻(xiàn)[11]。（3）算法結(jié)束：dis即為所有點(diǎn)對(duì)的最短路徑矩陣。dis[i,j]dis[i,k]+dis[k,j]tonFori=1to（2）ForPaths)；（2）稠密圖效果最佳；（3）邊權(quán)可正可負(fù)。Pairs六、Floyd算法適用范圍：算法實(shí)現(xiàn)：此算法時(shí)間復(fù)雜度O(V+E)，時(shí)間和編程復(fù)雜度低，如遇到符合條件的題目(DAG)，推薦使用。u的每個(gè)鄰接點(diǎn)vDAG)；（3）For拓?fù)湫虻拿總€(gè)頂點(diǎn)uHALT(NotToposort=FalseGraph,有向無(wú)環(huán)圖)；（2）邊權(quán)可正可負(fù)。DAG算法適用條件和范圍：（1）DAG(Directed五、SSSPindgr[u]=0dec(indgr[u])；b.do①頂點(diǎn)v出棧；輸出v；計(jì)數(shù)器增1；②For與v鄰接的頂點(diǎn)u(棧頂指針)；（3）將初始狀態(tài)所有入度為0的頂點(diǎn)壓棧；（4）I=0算法實(shí)現(xiàn)：（1）數(shù)據(jù)結(jié)構(gòu)：adj:鄰接表。Network)；（2）有向圖；（3）作為某些算法的預(yù)處理過(guò)程(如DP)。On dist[k] edge[k][j]+dist[j] 更新當(dāng)前值 }四、Topological for 2 to n1 (i) for 1 to n (j) for 1 to n (k) if edge[k][j] 0 amp。算法實(shí)現(xiàn)：（1）PASCA語(yǔ)言 For i:=1 to |V|1 do
語(yǔ)文相關(guān)推薦
鄂ICP備17016276號(hào)-1