最短路徑算法分類與應(yīng)用研究-預(yù)覽頁
【正文】 現(xiàn) 4五、SSSP最短路徑問題是圖論研究中的一個經(jīng)典算法問題，旨在尋找圖（由結(jié)點(diǎn)和路徑組成的）中兩結(jié)點(diǎn)之間的最短路徑。同時，也為參加數(shù)學(xué)建模的同學(xué)提供一些解題的思路與方法，為比賽提供有利的資源。On算法描述：如果 v1→ v2→ v3→ v4 是 v1→ v4 的最短路徑，則 v1→ v2→ v3 一定是 v1→ v3 的最短路徑。i:=1do它擴(kuò)展結(jié)點(diǎn)的次序類似于廣度優(yōu)先搜索，但不同的是每生成一個子結(jié)點(diǎn)需要計(jì)算估價函數(shù)F，以估算起始結(jié)點(diǎn)到該結(jié)點(diǎn)的代價及它到達(dá)目標(biāo)結(jié)點(diǎn)的代價的和；每當(dāng)擴(kuò)展結(jié)點(diǎn)時，總是在所有待擴(kuò)展結(jié)點(diǎn)中選擇具有最小F值的結(jié)點(diǎn)作為擴(kuò)展對象，以便使搜索盡量沿最有希望的方向進(jìn)行。OPEN表保存了所有已生成而未考察的節(jié)點(diǎn)，CLOSED表中記錄已訪問過的節(jié)點(diǎn)。CLOSED=[]。CLOSED=[C4, B4, A5]（5）估算H3，取得搜有子節(jié)點(diǎn)，并放入OPEN表中；OPEN=[O2, P3, G4, E5, F5, D6]。算法描述：（1）對每條邊進(jìn)行|V|次Relax操作；（2）如果存在（u,v）∈E使得dis[u]+wdis[v]，則存在負(fù)權(quán)回路；否則dis[v]即為s到v的最短距離，pre[v]為前驅(qū)。amp。Vertex有4個域{u,v,w,next}；indgr[i]:頂點(diǎn)i的入度；stack[]:棧；（2）初始化:top=0doa.then頂點(diǎn)u入棧；（6）EXIT(I=|V|)。AcyclicThendoFor還有，此算法的步驟（3）可以在toposort中實(shí)現(xiàn)，這樣即減小了此算法復(fù)雜度的一個系數(shù)。Shortestk=1tonIf算法小結(jié)：此算法簡單有效，由于三重循環(huán)結(jié)構(gòu)緊湊，對于稠密圖，效率要高于執(zhí)行|V|次Dijkstra算法。（1）把v0放入U；（2）在所有u∈U，v∈VU的邊(u，v)∈E中找一條最小權(quán)值的邊，加入生成樹；（3）把（2）找到的邊的v加入U集合。Spanning算法實(shí)現(xiàn)：見參考文獻(xiàn)[13]。第三章 最短路徑算法應(yīng)用一、TSP問題的介紹TSP問題，即旅行商問題，是一種典型的組合最優(yōu)化問題，可描述為某旅行商欲往n個城市推銷貨物，從某個城市出發(fā)，沿途經(jīng)過各個城市一次后返回出發(fā)城市，要確定一條行走的路線，計(jì)算途徑n個城市的最短距離，即給定ｎ個城市和兩兩城市之間的距離，確定一條經(jīng)過每個城市并且僅經(jīng)過一次的路線，要求總路徑最短。而且路徑的增加速度非?？烨沂欠蔷€形的。貪心算法容易實(shí)現(xiàn)但是效率不好。我們從A到B，然后設(shè)定A和B之間的距離無限大。模擬退火算法模擬退火算法是一種求解大規(guī)模組合優(yōu)化問題的方法，對于NP完全組合優(yōu)化問題尤其有效。根據(jù)Metropolis準(zhǔn)則，粒子在溫度T時趨于平衡的概率為exp( E/(kT)), 其中E為溫度T時的內(nèi)能，E為其改變量，k為Boltzman常數(shù)。終止條件通常取為連續(xù)若干個新解都沒有被接受時終止算法；（7）T逐漸減少，且T趨于0，然后轉(zhuǎn)第2步運(yùn)算。然后, 把這些假設(shè)解置于問題的“ 環(huán)境”中, 并按適者生存的原則，從中選擇出較適應(yīng)環(huán)境的“ 染色體”進(jìn)行復(fù)制，再通過交叉，變異過程產(chǎn)生更適應(yīng)環(huán)境的新一代“ 染色體”群。蟻群算法首先引入TSP中常用符號：m為蟻群中螞蟻數(shù)量；為ｔ時刻位于城市ｉ的螞蟻個數(shù)，且；為城市i和j之間的距離；為邊（i,j）的能見度，反映由城市i轉(zhuǎn)移到城市j的啟發(fā)程度；為邊（i,j）上的信息素軌跡強(qiáng)度；為螞蟻ｋ在邊（i,j）上留下的單位長度軌跡信息素量；為螞蟻k的轉(zhuǎn)移概率；j是尚未訪問的城市。經(jīng)過 ｎ 個時刻，螞蟻完成一次循環(huán)，各路徑上信息素“蒸發(fā)”和增加的量根據(jù)下式調(diào)整： （2）式中：表示信息素蒸發(fā)后的剩余，則（1）為衰減系數(shù)，表示信息素的減少；表示信息素增加的量，在式（1）中 （3）表示第k只螞蟻在時刻留在路徑上的信息素量；，Q為常數(shù)，為第k個螞蟻爬過路徑的長度，等于的值。由得到信息素的初值，然后進(jìn)行信息素更新，判斷是否超出范圍，如果超出，則限制大小。每一次計(jì)算都得出新的最優(yōu)解，所以每一次計(jì)算中，和都會重新被更新，是一個動態(tài)變化范圍。 for i=1:nfor j=1:nif i~=jD(i,j)=((C(i,1)C(j,1))^2+(C(i,2)C(j,2))^2)^。 Tau=ones(n,n)。 L_best=inf.*ones(NC_max,1)。endTabu(:,1)=(Randpos(1,1:m))39。 Jc=1。endP=P/(sum(P))。Tabu(i,j)=to_visit。for j=1:(n1)L(i)=L(i)+D(R(j),R(j+1))。R_best(NC,:)=Tabu(pos(1),:)。endDelta_Tau(Tabu(i,n),Tabu(i,1))=Delta_Tau(Tabu(i,n),Tabu(i,1))+Q/L(i)。Shortest_Route=R_best(Pos(1),:)Shortest_Length=L_best(Pos(1))DrawRoute(C,Shortest_Route)function DrawRoute(C,R) N=length(R)。浙江旅行商最短路線圖如下圖：第四章 總結(jié)通過收集整理關(guān)于最短路徑的普遍算法，為研究最短路徑問題在一些出行問題、管理問題、工程問題及實(shí)際生活問題中的應(yīng)用，為企業(yè)和個人提供方便的選擇方法。致謝在本次論文設(shè)計(jì)過程中，指導(dǎo)老師對該論文從選題，構(gòu)思到最后定稿的各個環(huán)節(jié)給予細(xì)心指引與教導(dǎo),使我得以最終完成
語文相關(guān)推薦
鄂ICP備17016276號-1