最短路徑算法分類與應(yīng)用研究(存儲(chǔ)版)
【正文】 》,2007,.[6] 國內(nèi)主要城市經(jīng)緯度表(參考表).[7] 李士勇.《蟻群算法及其應(yīng)用》[M].哈爾濱:.[8] Dijkstra算法.[9] 拓?fù)渌惴?[10] 高玉龍 張西紅 吳彩華.《廣域網(wǎng)中網(wǎng)絡(luò)拓?fù)渌惴ㄑ芯俊穂J].《科學(xué)技術(shù)與工程》,2005,－1972.[11] Floyd算法.[12] Prim算法.[13] kruskal算法.[14] 賴金富 李向新.《基于改進(jìn)蟻群算法在最短路徑搜索中的應(yīng)用》[J].《昆明冶金高等?？茖W(xué)校學(xué)報(bào)》,2008,.[15] 江重光 傅培玉 孫仲憲 汪 鐳 吳啟迪.《智能蟻群算法》[J].《前沿技術(shù)》,2005,.[16] 張勇德 黃莎白. 多目標(biāo)優(yōu)化問題的蟻群算法研究》[J].《控制與決策》,2005,.[17] 劉文海 徐榮聰.《幾種最短路徑的算法及比較》[J].《福建電腦》,2008,.[18] 鄒亮 徐建閩 朱玲湘.《A*算法改進(jìn)及其在動(dòng)態(tài)最短路徑問題中的應(yīng)用》[J].《深圳大學(xué)學(xué)報(bào)理工版》,2007,.[19] 高為民.《基于螞蟻算法的公交網(wǎng)絡(luò)最短路徑問題研究》[J].《交通與計(jì)算機(jī)》,2007,.[20] 柴世紅 曹建文.《遺傳算法求解ＴＳＰ及其改進(jìn)》[J].《福建電腦》,2008,.[21] 王劍文 戴光明 謝柏橋 張全元.《求解TSP問題算法綜述》[J].《計(jì)算機(jī)工程與科學(xué)》,2008,.[22] 馬坤 于海平 彭啟山.《改進(jìn)的遺傳模擬退火算法在中的應(yīng)用》[J].《武漢科技大學(xué)學(xué)報(bào)（自然科學(xué)版）》,2006,.。浙江省33個(gè)城市的坐標(biāo)C（以33城市的經(jīng)緯度作為城市的相對坐標(biāo)），如下表：標(biāo)號(hào)城市北緯東經(jīng)標(biāo)號(hào)城市北緯東經(jīng)標(biāo)號(hào)城市北緯東經(jīng)1杭州12蘭溪23桐鄉(xiāng)2慈溪13臨海24溫嶺3東陽14麗水25溫州4奉化15龍泉26蕭山5富陽16寧波27義烏6海寧17平湖28樂清7湖州18衢州29余杭8建德19瑞安30余姚9江山20上虞31永康10嘉興21紹興3032舟山11金華22臺(tái)州33諸暨運(yùn)行蟻群算法，所得到的最短路線結(jié)果為：32－16－4－13－22－24－28－25－19－14－15－9－18－8－12－11－27－3－33－31－5－7－29－1－26－21－20－6－23－10－17－2－30即，舟山－寧波－奉化－臨海－臺(tái)州－溫嶺－樂清－溫州－瑞安－麗水－龍泉－江山－衢州－建德－蘭溪－金華－義烏－東陽－諸暨－永康－富陽－湖州－余杭－杭州－蕭山－紹興－上虞－寧海－桐鄉(xiāng)－嘉興－平湖－慈溪－余姚由于采用的是相對坐標(biāo)，即城市的經(jīng)緯度，因此不能算出具體最短路徑是多長，如果采用實(shí)際地理坐標(biāo)，則在運(yùn)行后的MATLAB程序結(jié)果里可以看見所計(jì)算出的最短路徑長度。for i=1:mfor j=1:(n1)Delta_Tau(Tabu(i,j),Tabu(i,j+1))=Delta_Tau(Tabu(i,j),Tabu(i,j+1))+Q/L(i)。for i=1:mR=Tabu(i,:)。endendfor k=1:length(J)P(k)=(Tau(visited(end),J(k))^Alpha)*(Eta(visited(end),J(k))^Beta)。for i=1:(ceil(m/n))Randpos=[Randpos,randperm(n)]。endendEta=1./D。第四步：往復(fù)迭代計(jì)算，直到達(dá)到最大迭代次數(shù)。為了阻止螞蟻重復(fù)訪問，為每只螞蟻都設(shè)計(jì)一個(gè)被稱為禁忌表（tabu list）的數(shù)據(jù)結(jié)構(gòu)。并且，在執(zhí)行遺傳算法之前，給出一群“ 染色體”， 也即是假設(shè)解。加溫時(shí), 固體內(nèi)部粒子隨溫升變?yōu)闊o序狀，內(nèi)能增大，而緩慢降溫時(shí)粒子漸趨有序，在每個(gè)溫度上都達(dá)到平衡態(tài)，最后在常溫時(shí)達(dá)到基態(tài)，內(nèi)能減為最小。假設(shè)我們一開始在A，比較A到其他點(diǎn)的路徑長度，找出A到B是最短的路徑(5公里)。城市越多,可能的路徑也越多。u,v不屬于同一連通分量then,v所在的連通分量(u,v)；tot=tot+W(u,v)（3）算法結(jié)束：tot為MST的總權(quán)值。算法描述：設(shè)圖G =（V，E），其生成樹的頂點(diǎn)集合為U。to（2）For算法實(shí)現(xiàn)：此算法時(shí)間復(fù)雜度O(V+E)，時(shí)間和編程復(fù)雜度低，如遇到符合條件的題目(DAG)，推薦使用。Toposort=Falseindgr[u]=0算法實(shí)現(xiàn)：（1）數(shù)據(jù)結(jié)構(gòu)：adj:鄰接表。 for 2 to n1 (i) for 1 to n (j) for 1 to n (k) if edge[k][j] 0 amp。 CLOSED=[B4, A5]（4）估算C4；取得搜有子節(jié)點(diǎn)，并放入OPEN表中；OPEN=[H3, G4, E5, F5, D6]。算法原理：如圖有如下的狀態(tài)空間：（起始位置是A，目標(biāo)位置是P，字母后的數(shù)字表示節(jié)點(diǎn)的估價(jià)值）狀態(tài)空間圖搜索過程中設(shè)置兩個(gè)表：OPEN和CLOSED。VS中每個(gè)頂點(diǎn)v一、Di
語文相關(guān)推薦
鄂ICP備17016276號(hào)-1