版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
1、1用matlab尋找賦權(quán)圖中的最短路中的應(yīng)用尋找賦權(quán)圖中的最短路中的應(yīng)用1引言引言圖論是應(yīng)用數(shù)學(xué)的一個(gè)分支,它的概念和結(jié)果來源都非常廣泛,最早起源于一些數(shù)學(xué)游戲的難題研究,如歐拉所解決的格尼斯堡七橋問題,以及在民間廣泛流傳的一些游戲的難題,如迷宮問題,博弈問題等。這些古老的難題,吸引了很多學(xué)者的注意。1847年,圖論應(yīng)用于分析電路網(wǎng)絡(luò),這是它最早應(yīng)用于工程科學(xué),以后隨著科學(xué)的發(fā)展,圖論在解決運(yùn)籌學(xué),網(wǎng)絡(luò)理論,信息論,控制論,博弈論以及計(jì)
2、算機(jī)科學(xué)等各個(gè)領(lǐng)域的問題時(shí),發(fā)揮出很大的作用。在實(shí)踐中,圖論已成為解決自然科學(xué),工程技術(shù),社會(huì)科學(xué),軍事等領(lǐng)域中許多問題的有力工具之一。最短路問題是圖論理論中的經(jīng)典問題,尋找最短路徑就是在指定網(wǎng)絡(luò)中兩節(jié)點(diǎn)間找一條距離最小的路。2最短路最短路2.12.1最短路的定義(shtpathproblem)對最短路問題的研究早在上個(gè)世紀(jì)60年代以前就卓有成效了,其中對賦權(quán)圖的有效算法是由荷蘭著名計(jì)算機(jī)專家E.W.Dijkstra在1959年首次提出
3、的該算法能??0ijw?夠解決兩指定點(diǎn)間的最短路也可以求解圖G中一特定點(diǎn)到其它各頂點(diǎn)的最短路。后來海斯在Dijkstra算法的基礎(chǔ)之上提出了海斯算法。但這兩種算法都不能解決含有負(fù)權(quán)的圖的最短路問題。因此由Fd提出了Fd算法它能有效地解決含有負(fù)權(quán)的最短路問題。但在現(xiàn)實(shí)生活中我們所遇到的問題大都不含負(fù)權(quán)所以我們在的情況下選擇Dijkstra算法。??0ijw?若網(wǎng)絡(luò)中的每條邊都有一個(gè)數(shù)值(長度、成本、時(shí)間等),則找出兩節(jié)點(diǎn)(通常是源節(jié)點(diǎn)和阱
4、節(jié)點(diǎn))之間總權(quán)和最小的路徑就是最短路問題。最短路問題是網(wǎng)絡(luò)理論解決的典型問題之一,它不僅可以直接應(yīng)用于解決生產(chǎn)實(shí)際的許多問題,如管路鋪設(shè)、線路安裝、廠區(qū)布局和設(shè)備更新等,而且經(jīng)常被作為一個(gè)基本的工具,用于解決其他的做優(yōu)化問題。3f(i=1:n)f(j=1:n)R(ij)=jendend%賦路徑初值f(k=1:n)f(i=1:n)f(j=1:n)if(D(ik)D(kj)D(ij))D(ij)=D(ik)D(kj)%更新dijR(ij)=
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫僅提供信息存儲(chǔ)空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 最短路徑問題―――螞蟻爬行的最短路徑
- 最短路徑畢業(yè)論文--交通咨詢系統(tǒng)的最短路徑算法與實(shí)現(xiàn)
- 利用matlab編程計(jì)算最短路徑及中位點(diǎn)選址
- 最短路算法[1]
- 最短路問題的靈敏度分析與最短路調(diào)整.pdf
- 最短路徑學(xué)年論文
- 最短路徑問題(經(jīng)典)
- 最短路徑規(guī)劃研究
- 最短路徑優(yōu)化算法的研究與實(shí)現(xiàn).pdf
- 最短路f_d
- 最短路徑問題(經(jīng)典)
- 海上航線最短路徑算法研究與實(shí)現(xiàn).pdf
- 最短路徑優(yōu)化算法的研究與實(shí)現(xiàn)(1)
- 交通分配之隨機(jī)配流算法matlab源碼(含最短路徑算法)
- 軸對稱——最短路徑問題
- 最短路徑問題--教學(xué)設(shè)計(jì)
- 最短路徑畢業(yè)論文
- 13.4最短路徑問題教案
- 單元點(diǎn)最短路徑算法的實(shí)現(xiàn)課程設(shè)計(jì)
評(píng)論
0/150
提交評(píng)論