數(shù)學(xué)建模模最短路

1、.基于最短路問題的研究及應(yīng)用：Fanmeng學(xué) 號(hào) ：指導(dǎo)老師：.摘要最短路問題是圖論中的一大問題， 對(duì)最短路的研究在數(shù)學(xué)建模和實(shí)際生活中具有很重要的實(shí)際 意義，介紹 最短路 問題的定 義及這類問 題的解 決辦法 Dijkstra 算法，并且能夠在水渠修建實(shí)例運(yùn)用到此數(shù)學(xué)建模的方法，為我們解決這類圖論問題提供了基本思路與方法。關(guān)鍵字?jǐn)?shù)學(xué)建模最短路問題Dijkstra算法水渠修建。.目錄第一章研究背景 . .1第二章理論基礎(chǔ) . .22.1定義 .22.2單源最短路問題Dijkstra 求解 :. .22.2.1局限性 . .22.2.2 Dijkstra算法求解步驟 .22.2.3時(shí)間復(fù)雜度

2、. .22.3簡(jiǎn)單樣例 . .3第三章應(yīng)用實(shí)例 . .43.1題目描述 . .43.2問題分析 . .43.3符號(hào)說明 .53.4模型假設(shè) . .53.5模型建立與求解 .53.5.1模型選用 .53.5.2模型應(yīng)用及求解 .53.6模型評(píng)價(jià) .5第四章 .參考文獻(xiàn) . .6第五章附錄 .7.第一章研究背景在現(xiàn)實(shí)生活中中， 我們經(jīng)常會(huì)遇到圖類問題， 圖是一種有頂點(diǎn)和邊組成， 頂點(diǎn)代表對(duì)象，在示意圖中我們經(jīng)常使用點(diǎn)或者原來表示， 邊表示的是兩個(gè)對(duì)象之間的連接關(guān)系， 在示意圖中， 我們使用連接兩點(diǎn) G點(diǎn)直接按的下端來表示。 頂點(diǎn)的集合是 V，邊的集合是 E 的圖記為 GV,E , 連接兩點(diǎn) u 和

3、 v 的邊用 e(u,v) 表示 1 。最短問題是圖論中的基礎(chǔ)問題，也是解決圖類問題的有效辦法之一，在數(shù)學(xué)建模中會(huì)經(jīng)常遇到， 通常會(huì)把一個(gè)實(shí)際問題抽象成一個(gè)圖， 然后來進(jìn)行求的接任意兩點(diǎn)之間的最短距離。因此掌握最短路問題具有很重要的意義。.第二章理論基礎(chǔ)2.1定義最短路問題（ short-path problem ）：若網(wǎng)絡(luò)中的每條邊都有一個(gè)數(shù)值（長(zhǎng)度、成本、時(shí)間等），則找出兩節(jié)點(diǎn)，（通常是源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)）之間總權(quán)和最小的路徑就是最短路問題。 最短路問題是網(wǎng)絡(luò)理論解決的典型問題之一， 可用來解決管道鋪設(shè)，線路安裝，廠區(qū)布局和設(shè)備更新等實(shí)際問題 2 。2.2單源最短路問題Dijkstra求解

4、:局限性Dijkstra 算法不能夠處理帶有負(fù)邊的圖，即圖中任意兩點(diǎn)之間的權(quán)值必須非負(fù)。算法求解步驟(1).先給圖中的點(diǎn)進(jìn)行編號(hào)，確定起點(diǎn)的編號(hào)。(2).得到圖的構(gòu)成，寫出寫出圖的矩陣(u0 , u0 )(u0 , un )G(un , u0 )(un , un )(3).根據(jù)要求求出發(fā)點(diǎn) S 到終點(diǎn) E 的最短距離，那么需要從當(dāng)前沒被訪問過的結(jié)點(diǎn)集合 unvist=u | u 1,2,3. n 中找到一個(gè)距離已經(jīng)標(biāo)記的點(diǎn)的集合中 vist=u | u 1,2,3. n 的最短距離，得到這個(gè)頂點(diǎn)；(4).利用這個(gè)頂點(diǎn)來松弛其它和它相連的頂點(diǎn)距離S 的值(5). 重復(fù)步驟 (2) 和 (3) ，

5、直到再也沒有點(diǎn)可以用來松弛其它點(diǎn)，這樣我們就得到了由起點(diǎn) S 到其它任意點(diǎn)的最短距離。時(shí)間復(fù)雜度時(shí)間復(fù)雜度達(dá)到 O(N 2).2.3簡(jiǎn)單樣例給出對(duì)應(yīng)的結(jié)點(diǎn)之間的關(guān)系表 1 為對(duì)應(yīng)的結(jié)點(diǎn)之間的關(guān)系長(zhǎng)度ABCDEA02151010B201115C15111207D10102003E105730注釋：其中（ A,B） = 2表示結(jié)點(diǎn) A 到 B 的長(zhǎng)度為 2第一步：進(jìn)行編號(hào)，假定A 點(diǎn)即為起點(diǎn)。第二步：得到圖02151010201115G 151102071012003105730第三步：首先從起點(diǎn) A 開始找到距離 A 最近的點(diǎn)，那就是 A 點(diǎn)了；第四步：把A 點(diǎn)標(biāo)記到已經(jīng)用過的的集合vist A

6、 用 A 來更新其它點(diǎn)unvist B, C , D , E 到起點(diǎn)的距離得到的集合dist =ABCDE02151010表示起點(diǎn)到 B,C,D,E 的距離分別為 2,15,10,10第五步：重復(fù)上述步驟：得到vistA,B,unvistC,D,E,ABCDEdist =213370繼續(xù)重復(fù)上述步驟，最后的到vist A, B,C , D , E , unvist, 得到的ABCDEdist =021336，即最短路求解完畢。.第三章應(yīng)用實(shí)例3.1題目描述農(nóng)村的孩子應(yīng)該都會(huì)聽到大人們經(jīng)常談?wù)撨@樣的問題-修建水渠。在我們北方采用深井灌溉，所以說修建水渠更加普遍，因?yàn)橐话愣际撬苯右鞯教锏嘏赃?/p>

7、。經(jīng)常一些土地需要開發(fā)，在這個(gè)過程中，我們需要能夠?qū)⒃谀骋粋€(gè)地點(diǎn)的水源引流到新建的田地里面，這個(gè)過程很麻煩，有時(shí)候大家很激動(dòng)的去引流，結(jié)果最后修建的水渠并不能滿足要求，往往浪費(fèi)了大量的物力人力和財(cái)力， 所以現(xiàn)在我們要設(shè)計(jì)一定的數(shù)學(xué)模型來幫助農(nóng)民來規(guī)劃一下，如何修建的水渠最優(yōu)，并且給出修建的路徑。通常是通過步長(zhǎng)來估計(jì)兩個(gè)點(diǎn)之間的長(zhǎng)度，我們通常可以這樣理解，每?jī)刹娇梢哉J(rèn)為是1 米。給出的點(diǎn)之間的關(guān)系描述關(guān)系為（其他因素先可以不用考慮）：表 2、描述進(jìn)水口之間的關(guān)系步數(shù)ABCDEFGHIA0111200300400500600B102342573C12010611121314/p>

8、4E20046100010203040F3002111100506060G4005122205002334H5007133306023012I6003144406034120注： A 表示的是總的進(jìn)水口，其余字母表示的是每塊田地的進(jìn)水口的位置,這只是部分?jǐn)?shù)據(jù)。3.2問題分析問題是讓我們來規(guī)劃一下水渠該如何來修建的問題，并且已經(jīng)知道了出水口所在的位置，并且簡(jiǎn)單的知道了一些點(diǎn)之間的距離，讓我們幫農(nóng)民找到一條最優(yōu)的水渠來完成引流工作。既然給出的是關(guān)于長(zhǎng)度的問題，那么長(zhǎng)度一定是很重要的標(biāo)記量了，那么我們只需要找到一條從總出水到某一塊地的修建的距離最短即可。.3.3 符號(hào)說明G由長(zhǎng)度構(gòu)成的矩陣（L X,

9、Y ）表示從 X 到 Y 的最短距離S總出水口E田地進(jìn)水口3.4模型假設(shè)假設(shè)其余條件不會(huì)影響水渠修建，比如土壤硬度假設(shè)水渠寬度不會(huì)對(duì)水流量造成影響即水渠的流量會(huì)滿足要求3.5 模型建立與求解模型選用最短路模型最短路模型解決的就是圖論中任意兩點(diǎn)之間的最短路問題。模型應(yīng)用及求解我們的指標(biāo)是（L X,Y） = min(x,y) | x A, B., y A, B,.首先對(duì)數(shù)據(jù)進(jìn)行抽取， 得到我們所需要的數(shù)值， 并把它存儲(chǔ)到矩陣 G這應(yīng)該是一個(gè) 9*9 的矩陣，其次我們可以按照最短路的模型使用Dijkstra算法來進(jìn)行求解，得到的值便是 S 到任一點(diǎn)的最短距離值，最后按照路徑還原的思想還原修建的路徑即

10、可。3.6 模型評(píng)價(jià)最短路模型的是行能夠較好的解決單源最短路徑問題， 可以較好的模擬出路徑修建，得到的一定是最短的路徑，能夠達(dá)到預(yù)期要求的效果，得到的最終結(jié)果如附錄里“ 3. 應(yīng)用實(shí)例結(jié)果輸出”所示.第四章 .參考文獻(xiàn)1. 中庚著，數(shù)學(xué)建模方法與應(yīng)用，高等教育2. baike.baidu./view/838916.htm3. 美 Frank R.Giordano 著數(shù)學(xué)建模（原書第五版）4. 曉妍著基于最短路的設(shè)備更新問題的數(shù)學(xué)建模 教育學(xué)院學(xué)報(bào) ( 自然科學(xué)版) 第22卷第四期 2013 年 12月5. 啟帆、邊馥萍著，數(shù)學(xué)模型，大學(xué).第五章附錄1. 應(yīng)用實(shí)例矩陣01112003004005

11、0060010234257312010611121314131001001234G2004610001020304030021111005060604005122205002334500713330602301260031444060341202. 應(yīng)用實(shí)例 C+程序#include <iostream>#include <cstring>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath&g

12、t;#include <vector>usingnamespacestd ;constdouble INF= 0xFFFFFFF;const int MAX_N = 10005 ; / 表示最大有頂點(diǎn) 10005 個(gè)； int n , m; / 表示有 n 個(gè)結(jié)點(diǎn)；給出了 m條邊 double G MAX_N MAX_;N / 用鄰接矩陣來從這個(gè)圖 double dist MAX_;N / 表示起點(diǎn)到當(dāng)前點(diǎn)的最短距離bool vist MAX_;Nintprev MAX_;Nvector< int>getpath (intt ) /路徑還原可變長(zhǎng)數(shù)組類型vector&l

13、t;int>path ;for(;t!=- 1; t= prev t )path. push_back( t );reverse( path . begin (), path . end();returnpath ;void Dijkstra(ints ) / 求得最短路徑dist s= 0 ;.while(true)intv= - 1;double mx = INF ;for(inti= 1 ; i<= n ; i +) / 挑選出未被標(biāo)記集合最短的點(diǎn)if(!vist i && mx > dist i )mx= dist i ;v= i ;if(v = -

14、1) break;vist v= true;for(inti= 1 ; i<= n ; i +) /用當(dāng)前的到的值來松弛其他不在標(biāo)記的集合中的值if(!vist i &&dist i > dist v+ G v i )dist i = dist v+ G v i ;prev i = v ;void init() /初始化值for(inti= 1 ; i<= n ; i +) for(intj= 1 ; j<= n ; j +) G i j = INF ;G i i = 0 ;dist i = INF ;vist i = false;prev i = -

15、1;intmain ()freopen ( "data.in", "r" , stdin ); /默認(rèn)數(shù)據(jù)讀入用data.infreopen( "data.out", "w" , stdout ); /輸出默認(rèn)到 data.outcin>> n ;init();for(inti= 1 ; i<= n ; i +) for(intj= 1 ; j<= n ; j +) cin>> G i j ;.Dijkstra( 1);for(inti= 1 ; i<= n ; i +)p

16、rintf( " 出 水 口 到 目 標(biāo) 點(diǎn)%d 的 最 短 距 離= %.0fn", i , dist i );vector<int>q = getpath ( i );printf( " 目標(biāo)點(diǎn) %d 的路徑為 n" , i );printf( "%d", q 0);for(inti= 1 ; i< (int)q. size ();i +) printf( "-> %d " , q i );printf( "n" );return0 ;3. 應(yīng)用實(shí)例結(jié)果輸出出水口到目標(biāo)點(diǎn) 1 的最短距離 = 0 目標(biāo)點(diǎn) 1 的路徑為1出水口到目標(biāo)點(diǎn)2的最短距離 = 1目標(biāo)點(diǎn) 2的路徑為1-> 2出水口到目標(biāo)點(diǎn)3