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

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

2、題目描述43.2 問題分析43.3符號說明53.4 模型假設(shè)53.5模型建立與求解53.5.1模型選用53.5.2模型應(yīng)用及求解53.6模型評價5第四章. 參考文獻6第五章附錄7第一章研究背景 在現(xiàn)實生活中中，我們經(jīng)常會遇到圖類問題，圖是一種有頂點和邊組成，頂點代表對象，在示意圖中我們經(jīng)常使用點或者原來表示，邊表示的是兩個對象之間的連接關(guān)系，在示意圖中，我們使用連接兩點G點直接按的下端來表示。頂點的集合是V，邊的集合是E的圖記為GV,E ,連接兩點u和v的邊用e(u,v)表示1。最短問題是圖論中的基礎(chǔ)問題，也是解決圖類問題的有效辦法之一，在數(shù)學(xué)建模中會經(jīng)常遇到，通常會把一個實際問題抽象成一個圖

3、，然后來進行求的接任意兩點之間的最短距離。因此掌握最短路問題具有很重要的意義。第二章理論基礎(chǔ)2.1 定義最短路問題（short-path problem）：若網(wǎng)絡(luò)中的每條邊都有一個數(shù)值（長度、成本、時間等），則找出兩節(jié)點，（通常是源節(jié)點和目標(biāo)節(jié)點）之間總權(quán)和最小的路徑就是最短路問題。最短路問題是網(wǎng)絡(luò)理論解決的典型問題之一，可用來解決管道鋪設(shè)，線路安裝，廠區(qū)布局和設(shè)備更新等實際問題2。2.2 單源最短路問題Dijkstra求解:2.2.1 局限性Dijkstra算法不能夠處理帶有負邊的圖，即圖中任意兩點之間的權(quán)值必須非負。2.2.2 Dijkstra算法求解步驟(1). 先給圖中的點進行編號，確

4、定起點的編號。(2). 得到圖的構(gòu)成，寫出寫出圖的矩陣(3). 根據(jù)要求求出發(fā)點S到終點E的最短距離，那么需要從當(dāng)前沒被訪問過的結(jié)點集合中找到一個距離已經(jīng)標(biāo)記的點的集合中的最短距離，得到這個頂點；(4). 利用這個頂點來松弛其它和它相連的頂點距離S的值(5). 重復(fù)步驟(2)和(3)，直到再也沒有點可以用來松弛其它點，這樣我們就得到了由起點S到其它任意點的最短距離。2.2.3 時間復(fù)雜度時間復(fù)雜度達到2.3 簡單樣例給出對應(yīng)的結(jié)點之間的關(guān)系表1為對應(yīng)的結(jié)點之間的關(guān)系長度ABCDEA02151010B201115C15111207D10102003E105730注釋：其中（A,B）= 2 表示結(jié)

5、點A到B 的長度為2第一步：進行編號，假定A點即為起點。第二步：得到圖 第三步：首先從起點A開始找到距離A最近的點，那就是A點了；第四步：把A點標(biāo)記到已經(jīng)用過的的集合用A來更新其它點到起點的距離得到的集合表示起點到B,C,D,E的距離分別為2,15,10,10第五步：重復(fù)上述步驟：得到,繼續(xù)重復(fù)上述步驟，最后的到,得到的 ，即最短路求解完畢。第三章應(yīng)用實例3.1 題目描述農(nóng)村的孩子應(yīng)該都會聽到大人們經(jīng)常談?wù)撨@樣的問題-修建水渠。在我們北方采用深井灌溉，所以說修建水渠更加普遍，因為一般都是水渠直接引流到田地旁邊。經(jīng)常一些土地需要開發(fā)，在這個過程中，我們需要能夠?qū)⒃谀骋粋€地點的水源引流到新建的田地

6、里面，這個過程很麻煩，有時候大家很激動的去引流，結(jié)果最后修建的水渠并不能滿足要求，往往浪費了大量的物力人力和財力，所以現(xiàn)在我們要設(shè)計一定的數(shù)學(xué)模型來幫助農(nóng)民來規(guī)劃一下，如何修建的水渠最優(yōu)，并且給出修建的路徑。通常是通過步長來估計兩個點之間的長度，我們通常可以這樣理解，每兩步可以認為是1米。給出的點之間的關(guān)系描述關(guān)系為（其他因素先可以不用考慮）： 表2、描述進水口之間的關(guān)系步數(shù)ABCDEFGHIA0111200300400500600B102342573C12010611121314D131001001234E20046100010203040F3002111100506060G40051222

7、05002334H5007133306023012I6003144406034120注：A表示的是總的進水口，其余字母表示的是每塊田地的進水口的位置,這只是部分數(shù)據(jù)。3.2 問題分析問題是讓我們來規(guī)劃一下水渠該如何來修建的問題，并且已經(jīng)知道了出水口所在的位置，并且簡單的知道了一些點之間的距離，讓我們幫農(nóng)民找到一條最優(yōu)的水渠來完成引流工作。既然給出的是關(guān)于長度的問題，那么長度一定是很重要的標(biāo)記量了，那么我們只需要找到一條從總出水到某一塊地的修建的距離最短即可。3.3符號說明由長度構(gòu)成的矩陣表示從X到 Y的最短距離S總出水口E田地進水口3.4 模型假設(shè)假設(shè)其余條件不會影響水渠修建，比如土壤硬度假設(shè)

8、水渠寬度不會對水流量造成影響即水渠內(nèi)的流量會滿足要求3.5模型建立與求解3.5.1模型選用最短路模型 最短路模型解決的就是圖論中任意兩點之間的最短路問題。3.5.2模型應(yīng)用及求解我們的指標(biāo)是 首先對數(shù)據(jù)進行抽取，得到我們所需要的數(shù)值，并把它存儲到矩陣 這應(yīng)該是一個9*9的矩陣，其次我們可以按照最短路的模型使用Dijkstra算法來進行求解，得到的值便是S到任一點的最短距離值，最后按照路徑還原的思想還原修建的路徑即可。3.6模型評價最短路模型的是行能夠較好的解決單源最短路徑問題，可以較好的模擬出路徑修建，得到的一定是最短的路徑，能夠達到預(yù)期要求的效果，得到的最終結(jié)果如附錄里“3. 應(yīng)用實例結(jié)果輸

9、出”所示第四章. 參考文獻1. 韓中庚著，數(shù)學(xué)建模方法與應(yīng)用，高等教育出版社2. 3. 美 Frank R.Giordano著數(shù)學(xué)建模（原書第五版）4.劉曉妍著基于最短路的設(shè)備更新問題的數(shù)學(xué)建模 河南教育學(xué)院學(xué)報(自然科學(xué)版) 第22卷 第四期 2013年12月5. 楊啟帆、邊馥萍著，數(shù)學(xué)模型，浙江大學(xué)出版社第五章附錄1. 應(yīng)用實例矩陣2. 應(yīng)用實例C+程序#include <iostream>#include <cstring>#include <cstdio>#include <cstdlib>#include <algorithm&g

10、t;#include <cstring>#include <cmath>#include <vector>using namespace std;const double INF = 0xFFFFFFF;const int MAX_N = 10005;/ 表示最大有頂點10005個；int n,m;/ 表示有n個結(jié)點；給出了m條邊double GMAX_NMAX_N;/ 用鄰接矩陣來從這個圖double distMAX_N;/ 表示起點到當(dāng)前點的最短距離bool vistMAX_N;int prevMAX_N;vector < int> getp

11、ath(int t) / 路徑還原可變長數(shù)組類型 vector<int> path; for(; t != -1; t = prevt) path.push_back(t); reverse(path.begin(),path.end(); return path;void Dijkstra(int s) /求得最短路徑 dists = 0; while(true) int v = -1; double mx = INF; for(int i = 1; i <= n; i+) /挑選出未被標(biāo)記集合最短的點 if(!visti && mx > disti)

12、 mx = disti; v = i; if(v = -1) break; vistv = true; for(int i = 1; i <= n; i+) /用當(dāng)前的到的值來松弛其他不在標(biāo)記的集合中的值 if(!visti && disti > distv+Gvi) disti = distv+Gvi; previ = v; void init() /初始化值 for(int i = 1; i <= n; i+) for(int j = 1; j <= n; j+) Gij = INF; Gii = 0; disti = INF; visti = fa

13、lse; previ = -1; int main() freopen("data.in","r",stdin);/ 默認數(shù)據(jù)讀入用data.in freopen("data.out","w",stdout);/ 輸出默認到data.out cin >> n; init(); for(int i = 1; i <= n; i+) for(int j = 1; j <= n; j+) cin >> Gij; Dijkstra(1); for(int i = 1; i <= n

14、; i+) printf("出水口到目標(biāo)點 %d 的最短距離 = %.0fn",i,disti); vector<int> q = getpath(i); printf("目標(biāo)點 %d 的路徑為n",i); printf("%d",q0); for(int i = 1; i < (int)q.size(); i+) printf("-> %d ",qi); printf("n"); return 0;3. 應(yīng)用實例結(jié)果輸出出水口到目標(biāo)點 1 的最短距離 = 0目標(biāo)點 1 的路徑為1出水口到目標(biāo)點 2 的最短距離 = 1目標(biāo)點 2 的路徑為1-> 2 出水口到目標(biāo)點 3 的最短距離 = 1目標(biāo)點 3 的路徑為1-> 3 出水口到目標(biāo)點 4 的最短距離 = 1目標(biāo)點 4 的路徑為1-> 4 出水口