最短路徑算法分類與應(yīng)用研究-全文預(yù)覽
【正文】 及比較》[J].《福建電腦》,2008,.[18] 鄒亮 徐建閩 朱玲湘.《A*算法改進(jìn)及其在動態(tài)最短路徑問題中的應(yīng)用》[J].《深圳大學(xué)學(xué)報理工版》,2007,.[19] 高為民.《基于螞蟻算法的公交網(wǎng)絡(luò)最短路徑問題研究》[J].《交通與計算機》,2007,.[20] 柴世紅 曹建文.《遺傳算法求解ＴＳＰ及其改進(jìn)》[J].《福建電腦》,2008,.[21] 王劍文 戴光明 謝柏橋 張全元.《求解TSP問題算法綜述》[J].《計算機工程與科學(xué)》,2008,.[22] 馬坤 于海平 彭啟山.《改進(jìn)的遺傳模擬退火算法在中的應(yīng)用》[J].《武漢科技大學(xué)學(xué)報（自然科學(xué)版）》,2006,.。在學(xué)習(xí)中,老師嚴(yán)謹(jǐn)?shù)闹螌W(xué)態(tài)度、豐富淵博的知識、敏銳的學(xué)術(shù)思維、精益求精的工作態(tài)度以及侮人不倦的師者風(fēng)范是我終生學(xué)習(xí)的楷模，導(dǎo)師們的高深精湛的造詣與嚴(yán)謹(jǐn)求實的治學(xué)精神，將永遠(yuǎn)激勵著我。同時，也為參加數(shù)學(xué)建模的同學(xué)提供一些解題的思路與方法，為比賽提供有利的資源。scatter(C(:,1),C(:,2))。endTau=(1Rho).*Tau+Delta_Tau。L_ave(NC)=mean(L)。endL(i)=L(i)+D(R(1),R(n))。endendif NC=2Tabu(1,:)=R_best(NC1,:)。Pcum=cumsum(P)。for k=1:nif length(find(visited==k))==0J(Jc)=k。第三步 m只螞蟻選擇下一座城市，完成各自的周游for j=2:nfor i=1:mvisited=Tabu(i,1:(j1))。 L_ave=zeros(NC_max,1)。 Tabu=zeros(m,n)。elseD(i,j)=eps。 第五步：輸出最后結(jié)果。第三步：繼續(xù)迭代，直到第三次，得到。至此，一個螞蟻的循環(huán)過程結(jié)束，由此反復(fù)迭代多次，最終得出優(yōu)化結(jié)果。在初始時刻，各條路徑上的信息素量相等，設(shè)，（為常數(shù)），螞蟻被隨機放到某個城市，然后根據(jù)各條路徑上的信息素量選擇下一個城市。這樣，一代一代地進(jìn)化，最后就會收斂到最適應(yīng)環(huán)境的一個“ 染色體”上，它就是問題的最優(yōu)解。遺傳序列算法遺傳算法簡稱GA(Genetic Algorithm), 在本質(zhì)上是一種不依賴具體問題的直接搜索方法。用固體退火模擬組合優(yōu)化問題，將內(nèi)能E模擬為目標(biāo)函數(shù)值f，溫度T演化成控制參數(shù)t，即得到解組合優(yōu)化問題的模擬退火算法: 由初始解i和控制參數(shù)初值t開始，對當(dāng)前解重復(fù)產(chǎn)生“新解→計算目標(biāo)函數(shù)差→接受或舍棄”的迭代，并逐步衰減t值, 算法終止時的當(dāng)前解即為所得近似最優(yōu)解。模擬退火算法來源于固體退火原理，將固體加溫至充分高，再讓其緩慢降溫(即退火)，使之達(dá)到能量最低點。在B我們找出B到C(3公里)是最短的路徑。如下圖所示:有4個城市:A，B，C和D。當(dāng)n很大時，去嘗試每一種可能的路徑是不可能的，所以需要設(shè)計一個有效的算法去尋找最短的路徑。TSP分為2類，即對稱TSP和不對稱TSP。九、Johnson算法適用范圍：Johnson算法適用于求All Pairs Shortest Path。Tree,最小生成樹)；（2）無向圖(有向圖的是最小樹形圖)；（3）多用于稀疏圖；（4）邊已經(jīng)按權(quán)值排好序給出。如果U集合已有n個元素，則結(jié)束，否則繼續(xù)執(zhí)行（2）。算法實現(xiàn)：見參考文獻(xiàn)[11]。dis[i,j]dis[i,k]+dis[k,j]nFortoPaths)；（2）稠密圖效果最佳；（3）邊權(quán)可正可負(fù)。六、Floyd算法適用范圍：u的每個鄰接點vHALT(NotGraph,有向無環(huán)圖)；（2）邊權(quán)可正可負(fù)。五、SSSPdec(indgr[u])；b.(棧頂指針)；（3）將初始狀態(tài)所有入度為0的頂點壓棧；（4）I=0Network)；（2）有向圖；（3）作為某些算法的預(yù)處理過程(如DP)。 dist[k] edge[k][j]+dist[j] 更新當(dāng)前值 }四、Topological算法實現(xiàn)：（1）PASCA語言 For i:=1 to |V|1 do For 每條邊(u,v)∈E do Relax(u,v,w)。 CLOSED=H3C4, B4, A5]（6）估算O2，取得搜有子節(jié)點，并放入OPEN表中；OPEN=[P3, G4, E5, F5, D6]。（2）估算A5，取得搜有子節(jié)點，并放入OPEN表中；OPEN=[B4, C4, D6]。算法中有一步是根據(jù)估價函數(shù)重排OPEN表。因此，A*算法只要求產(chǎn)生問題的全部狀態(tài)空間的部分結(jié)點，就可以求解問題了，搜索效率較高。Relax （3）算法結(jié)束：dis[i]為s到i的最短距離；pre[i]為i的前驅(qū)節(jié)點。to v2→ v3→ v4 一定是 v2→ v4 的最短路徑。DAG算法、Floyd算法 、Prim算法、Kruskal算法及Johnson算法。最后應(yīng)用蟻群算法來解決浙江旅行商問題。算法具體的形式包括：確定起點的最短路徑問題—即已知起始結(jié)點，求最短路徑的問題；確定終點的最短路徑問題—與確定起點的問題相反，該問題是已知終結(jié)結(jié)點，求最短路徑的問題；在無向圖中該問題與確定起點的問題完全等同，在有向圖中該問題等同于把所有路徑方向反轉(zhuǎn)的確定起點的問題；確定起點終點的最短路徑問題—即已知起點和終點，求兩結(jié)點之間的最短路徑；全局最短路徑問題—求圖中所有的最短路徑。On最后應(yīng)用蟻群算法來解決浙江旅行商問題。同時，也為參加數(shù)學(xué)建模的同學(xué)提供一些解題的思路與方法，為比賽提供有利的資源。Sort(拓?fù)渑判?算法 4適用條件和范圍 4算法描述 4算法實
語文相關(guān)推薦
鄂ICP備17016276號-1