最短路徑算法分類(lèi)與應(yīng)用研究-wenkub.com
2025-06-23 06:04 本頁(yè)面
【正文】 在此，謹(jǐn)向老師們致以衷心的感謝和崇高的敬意！ 最后，我要向百忙之中抽時(shí)間對(duì)本文進(jìn)行審閱、評(píng)議的各位老師表示感謝。最后應(yīng)用蟻群算法來(lái)解決浙江旅行商問(wèn)題，由結(jié)果可以看出，蟻群算法運(yùn)用于浙江旅行商問(wèn)題，在結(jié)果上表現(xiàn)出令人滿意的效果。hold onplot([C(R(1),1),C(R(N),1)],[C(R(1),2),C(R(N),2)])hold onfor ii=2:Nplot([C(R(ii1),1),C(R(ii),1)],[C(R(ii1),2),C(R(ii),2)])hold onend蟻群算法解決浙江旅行商問(wèn)題浙江旅行商問(wèn)題初始參數(shù)設(shè)置如下： 蟻群中螞蟻數(shù)量m=200；信息素重要程度的參數(shù)Alpha=1；啟發(fā)式因子重要程度的參數(shù)Beta=5；信息素蒸發(fā)系數(shù)Rho=；最大迭代次數(shù)NC_max=200；信息素增加強(qiáng)度系數(shù)Q=100。Tabu=zeros(m,n)。NC=NC+1第五步 更新信息素Delta_Tau=zeros(n,n)。endL_best(NC)=min(L)。End第四步 記錄本次迭代最佳路線L=zeros(m,1)。Select=find(Pcum=rand)。Jc=Jc+1。 J=zeros(1,(nj+1))。 while NC=NC_max 第二步 將m只螞蟻放到n個(gè)城市上Randpos=[]。 NC=1。endD(j,i)=D(i,j)。蟻群算法的MATLAB程序描述 蟻群算法解決TSP的主要符號(hào)說(shuō)明：n 為城市個(gè)數(shù)；C 為n個(gè)城市的坐標(biāo)，n2的矩陣；m 為蟻群中螞蟻數(shù)量；NC_max 最大迭代次數(shù)；Alpha 表征信息素重要程度的參數(shù)；Beta 表征啟發(fā)式因子重要程度的參數(shù)；Rho 信息素蒸發(fā)系數(shù)；Q 信息素增加強(qiáng)度系數(shù)；R_best 各代最佳路線；L_best 各代最佳路線的長(zhǎng)度； MATLAB程序描述：第一步 變量初始化n=size(C,1)。判斷信息素是否超出，如果超出，則限制大小。三、算法應(yīng)用解決浙江旅行商問(wèn)題時(shí)算法描述 第一步：初始化，將所有城市坐標(biāo)列出，并計(jì)算出兩兩城市之間的距離。在ｔ時(shí)刻， （1）式中：表示螞蟻ｋ下一步允許選擇的城市；α和β為2個(gè)參數(shù)，分別反映螞蟻在運(yùn)動(dòng)過(guò)程中所積累的信息和啟發(fā)信息在螞蟻選擇路徑中的相對(duì)重要性。步驟如下:（1) 產(chǎn)生一群染色體(不同的游歷路徑) 然后計(jì)算評(píng)估每個(gè)染色體的健壯度(總路徑長(zhǎng)度)。遺傳算法GA把問(wèn)題的解表示成“染色體”，在算法中也即是以二進(jìn)制編碼的串。所以我們可以通過(guò)上面的思想寫(xiě)出解決TSP問(wèn)題的模擬退火算法。反之，如果急速降溫(即淬火)則不能達(dá)到最低點(diǎn)。如此然后去C，再到D。距離從A到B是5公里，A到C是6公里，A到D是9公里，B到C是3公里, B到D是7公里，C到D是8公里。二、TSP問(wèn)題算法的介紹貪心算法貪心算法的主要思想是永遠(yuǎn)選擇當(dāng)前最短的路徑。對(duì)于城市數(shù)目為n的地圖, 共有n種不同的路徑。算法實(shí)現(xiàn)：Johnson算法應(yīng)用了重標(biāo)號(hào)技術(shù)（1）先進(jìn)行一次BellmanFord算法；（2）然后對(duì)原圖進(jìn)行重標(biāo)號(hào)，w39。算法描述：（1）將邊按非降序排列；（2）While合并次數(shù)少于|V|1①取一條邊(u,v)(因?yàn)橐呀?jīng)排序，所以必為最小)②If算法實(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]。七、Prim算法適用范圍：（1）用于求無(wú)向圖的最小生成樹(shù)；（2）無(wú)向圖(有向圖的是最小樹(shù)形圖)；（3）多用于稠密圖。ThenDis[i,j]=dis[i,k]+dis[k,j]。j=1nFor算法描述：（1）初始化：dis[u,v]=w[u,v]。 （1）APSP(AlldoRelax(u,v,w)；（4）算法結(jié)束后：如有環(huán)則輸出錯(cuò)誤信息；否則dis[i]為s到i的最短距離，pre[i]為前驅(qū)頂點(diǎn)。a算法描述：（1）Toposort；（2）IfOnIf(計(jì)數(shù)器)；（5）While棧非空(top0)算法描述：（1）每次挑選入度為0的頂點(diǎn)輸出(不計(jì)次序)；（2）如果最后發(fā)現(xiàn)輸出的頂點(diǎn)數(shù)小于|V|，則表明有回路存在。Sort(拓?fù)渑判?算法適用條件和范圍：（1）AOV網(wǎng)(Activity For每條邊(u,v)∈E do If dis[u]+wdis[v] Then Exit(False)?。?）C/C++語(yǔ)言 void bellman_ford(int v) { for 1 to n initialize dist[v]。 CLOSED=[O2, H3, C4, B4, A5]（7）估算P3，已得到解。 CLOSED=[A5]（3）估算B4，取得搜有子節(jié)點(diǎn)，并放入OPEN表中；OPEN=[C4, E5, F5, D6]。這樣循環(huán)中的每一步只考慮OPEN表中狀態(tài)最好的節(jié)點(diǎn)。確定估價(jià)函數(shù)方法通常是：搜索到該結(jié)點(diǎn)的深度+ 距離目標(biāo)最近的程度。程序見(jiàn)參考文獻(xiàn)[8]。n①取VS中的一頂點(diǎn)u使得dis[u]=min{dis[v]|v∈VS}②S=S+{u}③For算法實(shí)現(xiàn)：（1）初始化：dis[v]=maxint ；dis[s]=0；pre[s]=s。其中最常用的路徑算法有：Dijkstra算法、
語(yǔ)文相關(guān)推薦
鄂ICP備17016276號(hào)-1