版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、基于MATLAB求解最短路問(wèn)題1.引言 MATLAB和Mathematica、Maple并稱(chēng)為三大數(shù)學(xué)軟件。它在數(shù)學(xué)類(lèi)科技應(yīng)用軟件中在數(shù)值計(jì)算方面首屈一指。通過(guò)本學(xué)期的學(xué)習(xí)了解和上機(jī)實(shí)踐,已經(jīng)初步掌握使用MATLAB工具解決實(shí)際問(wèn)題的能力。結(jié)合運(yùn)籌學(xué)課程的學(xué)習(xí),我考慮使用MATLAB求解最短路問(wèn)題,而在所有求解最短路的方法中,Dijkstra算法是最為經(jīng)典的一種,因此本文主要解決在MATLAB環(huán)境下使用Dijkstra算法求解最短路。1.1 提出問(wèn)題設(shè)6個(gè)城市v1,v2,.,v6之間的一個(gè)公路網(wǎng)(圖1)每條公路為圖中的邊,邊上的權(quán)數(shù)表示該段公路的長(zhǎng)度(單位:百公里),設(shè)你處在城市v1,那么從v
2、1到v6應(yīng)選擇哪一路徑使你的費(fèi)用最省。 1.2 分析問(wèn)題 這屬于一個(gè)典型的求解最短路的問(wèn)題,圖中頂點(diǎn)代表六個(gè)城市,邊上的權(quán)數(shù)表示該段公路的長(zhǎng)度,題目所求為從v1到v6、的一條費(fèi)用最省的路徑,我們假設(shè)所需費(fèi)用僅與路徑長(zhǎng)短有關(guān),因此求費(fèi)用最省的路徑即求權(quán)值最小的路徑。網(wǎng)絡(luò)圖中各權(quán)值均為正,可以使用Dijkstra算法。 1.3 數(shù)據(jù)整理 將網(wǎng)絡(luò)圖中各邊的權(quán)作如下整理以方便程序運(yùn)行 W(1,2)=5; W(2,1)=5; W(1,3)=2; W(3,1)=2; W(2,3)=1; W(3,2)=1; W(2,4)=5; W(4,2)=5; W(2,5)=5; W(5,2)=5; W(3,4)=8;
3、W(4,3)=8; W(3,5)=10; W(5,3)=10; W(4,5)=2; W(5,4)=2; W(4,6)=5; W(6,4)=5; W(5,6)=2; W(6,5)=2;2.數(shù)學(xué)原理 2.1 Dijkstra算法介紹Dijkstra 算法思想為:設(shè)G=(V,E)是一個(gè)帶權(quán)有向圖(也可以是無(wú)向圖,無(wú)向圖是有向圖的特例), 把圖中頂點(diǎn)集合V分成兩組:第一組為已求出最短路徑的頂點(diǎn)集合(用S 表示,初始時(shí)S 中只有一個(gè)源點(diǎn),以后每求得一條最短路徑,就將其加入到集合S 中,直到全部頂點(diǎn)都加入到S 中,算法就結(jié)束了);第二組為其余未確定最短路徑的頂點(diǎn)集合( 用U 表示), 按最短路徑長(zhǎng)度的遞增
4、次序依次把第二組的頂點(diǎn)加入S 中。在加入的過(guò)程中,總保持從源點(diǎn)v 到S 中各頂點(diǎn)的最短路徑長(zhǎng)度不大于從源點(diǎn)v 到U 中任何頂點(diǎn)的最短路徑長(zhǎng)度。此外,每個(gè)頂點(diǎn)對(duì)應(yīng)一個(gè)距離,S 中的頂點(diǎn)的距離就是從v 到此頂點(diǎn)的最短路徑長(zhǎng)度,U中的頂點(diǎn)的距離,是從v 到此頂點(diǎn)只包括S 中的頂點(diǎn)為中間頂點(diǎn)的當(dāng)前最短路徑長(zhǎng)度。其步驟主要有:第一,初始時(shí),S 只包含源點(diǎn),即S頂點(diǎn),v 的距離為0。U 包含除v 外的其他頂點(diǎn),U 中頂點(diǎn)u 距離為邊上的權(quán)(若v 與u 有邊)或(若u 不是v 的出邊鄰接點(diǎn))。第二,從U 中選取一個(gè)距離v 最小的頂點(diǎn)k,把k 加入S 中(該選定的距離就是v 到k 的最短路徑長(zhǎng)度)。第三,以k
5、 為新考慮的中間點(diǎn),修改U 中各頂點(diǎn)的距離; 若從源點(diǎn)v 到頂點(diǎn)u的距離(經(jīng)過(guò)頂點(diǎn)k)比原來(lái)距離(不經(jīng)過(guò)頂點(diǎn)k)短,則修改頂點(diǎn)u 的距離值,修改后的距離值的頂點(diǎn)k 的距離加上邊上的權(quán)。第四,重復(fù)步驟第二步和第三步直到所有頂點(diǎn)都包含在S 中。3. 程序設(shè)計(jì)function c0,c,path0,path=dijkstra(s,t,C,flag)s=floor(s);t=floor(t);n=size(C,1);label=ones(1,n)*inf;label(s)=0;S=s;Sbar=1:s-1,s+1:n;c0=0;path=zeros(n,n);path(:,1)=s;c=ones(1,
6、n)*inf;parent=zeros(1,n);i=1; % number of points in point set S.while i<n % for each point in Sbar, replace label(Sbar(j) by % min(label(Sbar(j),label(S(k)+C(S(k),Sbar(j) for j=1:n-i for k=1:i if label(Sbar(j) > label(S(k)+C(S(k),Sbar(j) label(Sbar(j)=label(S(k)+C(S(k),Sbar(j); parent(Sbar(j)=
7、S(k); end end end % Find the minmal label(j), j in Sbar. temp=label(Sbar(1); son=1; for j=2:n-i if label(Sbar(j)< temp temp=label(Sbar(j); son=j; end end % update the point set S and Sbar S=S,Sbar(son); Sbar=Sbar(1:son-1),Sbar(son+1:n-i); i=i+1; % if flag=1, just output the shortest path between
8、s and t. if flag=1 && S(i)=t son=t; temp_path=son; if son=s while parent(son)=s son=parent(son); temp_path=temp_path,son; end temp_path=temp_path,s; end temp_path=fliplr(temp_path); m=size(temp_path,2); path0(1:m)=temp_path; c_temp=0; for j=1:m-1 c_temp=c_temp+C(temp_path(j),temp_path(j+1);
9、end c0=c_temp; path(t,1:m)=path0; c(t)=c0; return endend% Form the output resultsfor i=1:n son=i; temp_path=son; if son=s while parent(son)=s son=parent(son); temp_path=temp_path,son; end temp_path=temp_path,s; end temp_path=fliplr(temp_path); m=size(temp_path,2); path(i,1:m)=temp_path; c_temp=0; fo
10、r j=1:m-1 c_temp=c_temp+C(temp_path(j),temp_path(j+1); end c(i)=c_temp; c0=c(t); path0=path(t,:);endreturn4. 結(jié)果分析 4.1 運(yùn)行程序clcs=1;t=6;flag=1;W=ones(9,9)*inf; % for i=1:9 W(i,i)=0;endW(1,2)=5; W(2,1)=5;W(1,3)=2; W(3,1)=2;W(2,3)=1; W(3,2)=1;W(2,4)=5; W(4,2)=5;W(2,5)=5; W(5,2)=5;W(3,4)=8; W(4,3)=8;W(3,5
11、)=10; W(5,3)=10;W(4,5)=2; W(5,4)=2;W(4,6)=5; W(6,4)=5;W(5,6)=2; W(6,5)=2;c0,c,path0,path=dijkstra(s,t,W,flag);c0path0 4.2 運(yùn)行結(jié)果 4.3 結(jié)果分析由運(yùn)行結(jié)果可知,從V1到V6的最短路徑長(zhǎng)度為10,路徑為:V1->V3->V2->V5->V6,結(jié)合網(wǎng)絡(luò)圖進(jìn)行驗(yàn)證,所求即為最短路。并且利用上述程序還可求得網(wǎng)絡(luò)中任意兩點(diǎn)之間的最短路徑。5. 學(xué)習(xí)體會(huì) MATLAB是美國(guó)MathWorks公司出品的商業(yè)數(shù)學(xué)軟件,用于算法開(kāi)發(fā)、數(shù)據(jù)可視化、數(shù)據(jù)分析以及數(shù)值計(jì)
12、算的高級(jí)技術(shù)計(jì)算語(yǔ)言和交互式環(huán)境,主要包括MATLAB和Simulink兩大部分。MATLAB是matrix&laboratory兩個(gè)詞的組合,意為矩陣工廠(矩陣實(shí)驗(yàn)室)。是由美國(guó)mathworks公司發(fā)布的主要面對(duì)科學(xué)計(jì)算、可視化以及交互式程序設(shè)計(jì)的高科技計(jì)算環(huán)境。它將數(shù)值分析、矩陣計(jì)算、科學(xué)數(shù)據(jù)可視化以及非線性動(dòng)態(tài)系統(tǒng)的建模和仿真等諸多強(qiáng)大功能集成在一個(gè)易于使用的視窗環(huán)境中,為科學(xué)研究、工程設(shè)計(jì)以及必須進(jìn)行有效數(shù)值計(jì)算的眾多科學(xué)領(lǐng)域提供了一種全面的解決方案,并在很大程度上擺脫了傳統(tǒng)非交互式程序設(shè)計(jì)語(yǔ)言(如C、Fortran)的編輯模式,代表了當(dāng)今國(guó)際科學(xué)計(jì)算軟件的先進(jìn)水平。Matl
13、ab的學(xué)習(xí)是在運(yùn)籌學(xué)之后開(kāi)始的,雖然是作為選修課,也只安排了短短的10次課,但從一開(kāi)始學(xué)習(xí),我就抱著要掌握好這個(gè)工具的態(tài)度上課,因?yàn)椴还苁菙?shù)學(xué)建模還是運(yùn)籌學(xué)中,都可以用到它解決很多實(shí)際問(wèn)題。課堂上教員給我們講解了軟件的基本操作并介紹了大量常用的命令,通過(guò)理論學(xué)習(xí)和上機(jī)實(shí)踐操作,慢慢的從開(kāi)始的完全不懂漸漸能夠編寫(xiě)一些簡(jiǎn)單的M文件解決一些應(yīng)用題,其中的成就感是相當(dāng)令人欣慰的。雖然在此之前我們還學(xué)過(guò)C語(yǔ)言、C+和數(shù)據(jù)庫(kù),也可以用它們來(lái)編程解題,但相比之下,使用MATLAB要簡(jiǎn)單得多,同樣的一個(gè)問(wèn)題,用編程的方法可能需要編寫(xiě)很多條代碼,在這個(gè)軟件中卻可以輕松實(shí)現(xiàn)?!皫煾殿I(lǐng)進(jìn)門(mén),修行靠個(gè)人”,受限于開(kāi)課
14、課時(shí),教員不可能給我們做太過(guò)深入的教學(xué),因此要想學(xué)好這個(gè)軟件,最重要的還是靠自己課下的探索,任何工具性的東西都是這樣,只有練熟才了生巧。 對(duì)提高matlab編程能力的方法,我想主要有以下三個(gè): 1、查help 在第一節(jié)課教員就向我們介紹了help命令,在學(xué)習(xí)過(guò)程中,時(shí)常遇到一些不知道的關(guān)鍵字,這時(shí)候只要通過(guò)help命令就可以找到該關(guān)鍵字的介紹,并且還有部分舉例,非常有助于理解程序。 2、多上論壇,搜索帖子、發(fā)帖詢問(wèn) 網(wǎng)上有很多關(guān)于MATLAB的貼吧和論壇,許多學(xué)習(xí)這個(gè)程序的人都在這里交流,有初學(xué)者也有高手,上論壇的一個(gè)好處就是可以知道別人在學(xué)習(xí)過(guò)程中都遇到了一些什么問(wèn)題,他們是怎么解決的,有什么好的學(xué)習(xí)經(jīng)驗(yàn)和方法可以供自己借鑒,甚至也可以自己發(fā)帖和別人交流,請(qǐng)教高手解答自己的困惑等等。 3、閱讀別人、特別是牛人的程序 多閱讀程序永遠(yuǎn)是編程類(lèi)軟件學(xué)
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025年度醫(yī)療設(shè)施場(chǎng)地租賃合同范本6篇
- 2025年度常年法律顧問(wèn)服務(wù)合同企業(yè)勞動(dòng)爭(zhēng)議解決報(bào)價(jià)4篇
- 2024經(jīng)濟(jì)中介服務(wù)合同格式
- 2025年度環(huán)保設(shè)備銷(xiāo)售與環(huán)保技術(shù)服務(wù)合同4篇
- 2025年度養(yǎng)老地產(chǎn)項(xiàng)目場(chǎng)地規(guī)則與條款詳細(xì)約定合同4篇
- 2025年度智能廠房電氣安裝及維護(hù)一體化服務(wù)合同范本4篇
- 2025年度航空航天器材供應(yīng)與研發(fā)合作合同4篇
- 2024年04月廣東廣州銀行春季校園招考筆試歷年參考題庫(kù)附帶答案詳解
- 2025年度礦產(chǎn)資源測(cè)繪技術(shù)服務(wù)合同模板4篇
- 2024年03月遼寧2024年興業(yè)銀行沈陽(yáng)分行春季校園招考筆試歷年參考題庫(kù)附帶答案詳解
- 增強(qiáng)現(xiàn)實(shí)技術(shù)在藝術(shù)教育中的應(yīng)用
- TD/T 1060-2021 自然資源分等定級(jí)通則(正式版)
- 《創(chuàng)傷失血性休克中國(guó)急診專(zhuān)家共識(shí)(2023)》解讀
- 倉(cāng)庫(kù)智能化建設(shè)方案
- 海外市場(chǎng)開(kāi)拓計(jì)劃
- 2024年度國(guó)家社會(huì)科學(xué)基金項(xiàng)目課題指南
- 供應(yīng)鏈組織架構(gòu)與職能設(shè)置
- 幼兒數(shù)學(xué)益智圖形連線題100題(含完整答案)
- 七上-動(dòng)點(diǎn)、動(dòng)角問(wèn)題12道好題-解析
- 2024年九省聯(lián)考新高考 數(shù)學(xué)試卷(含答案解析)
- 紅色歷史研學(xué)旅行課程設(shè)計(jì)
評(píng)論
0/150
提交評(píng)論