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

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

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

3、意兩點(diǎn)之間的最短距離。因此掌握最短路問(wèn)題具有很重要的意義。第二章理論基礎(chǔ)2.1 定義最短路問(wèn)題（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èn)題。最短路問(wèn)題是網(wǎng)絡(luò)理論解決的典型問(wèn)題之一，可用來(lái)解決管道鋪設(shè)，線(xiàn)路安裝，廠(chǎng)區(qū)布局和設(shè)備更新等實(shí)際問(wèn)題2。2.2 單源最短路問(wèn)題Dijkstra求解: 局限性Dijkstra算法不能夠處理帶有負(fù)邊的圖，即圖中任意兩點(diǎn)之間的權(quán)值必須非負(fù)。 Dijkstra算法求解步驟(1). 先給圖中的點(diǎn)進(jìn)行編號(hào)，確定起點(diǎn)的編號(hào)。(2). 得到圖的構(gòu)成，寫(xiě)

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

5、起點(diǎn)。第二步：得到圖 第三步：首先從起點(diǎn)A開(kāi)始找到距離A最近的點(diǎn)，那就是A點(diǎn)了；第四步：把A點(diǎn)標(biāo)記到已經(jīng)用過(guò)的的集合用A來(lái)更新其它點(diǎn)到起點(diǎn)的距離得到的集合表示起點(diǎn)到B,C,D,E的距離分別為2,15,10,10第五步：重復(fù)上述步驟：得到,繼續(xù)重復(fù)上述步驟，最后的到,得到的 ，即最短路求解完畢。第三章應(yīng)用實(shí)例3.1 題目描述農(nóng)村的孩子應(yīng)該都會(huì)聽(tīng)到大人們經(jīng)常談?wù)撨@樣的問(wèn)題-修建水渠。在我們北方采用深井灌溉，所以說(shuō)修建水渠更加普遍，因?yàn)橐话愣际撬苯右鞯教锏嘏赃?。?jīng)常一些土地需要開(kāi)發(fā)，在這個(gè)過(guò)程中，我們需要能夠?qū)⒃谀骋粋€(gè)地點(diǎn)的水源引流到新建的田地里面，這個(gè)過(guò)程很麻煩，有時(shí)候大家很激動(dòng)的去引流，結(jié)

6、果最后修建的水渠并不能滿(mǎn)足要求，往往浪費(fèi)了大量的物力人力和財(cái)力，所以現(xiàn)在我們要設(shè)計(jì)一定的數(shù)學(xué)模型來(lái)幫助農(nóng)民來(lái)規(guī)劃一下，如何修建的水渠最優(yōu)，并且給出修建的路徑。通常是通過(guò)步長(zhǎng)來(lái)估計(jì)兩個(gè)點(diǎn)之間的長(zhǎng)度，我們通常可以這樣理解，每?jī)刹娇梢哉J(rèn)為是1米。給出的點(diǎn)之間的關(guān)系描述關(guān)系為（其他因素先可以不用考慮）： 表2、描述進(jìn)水口之間的關(guān)系步數(shù)ABCDEFGHIA0111200300400500600B102342573C12010611121314D131001001234E20046100010203040F3002111100506060G4005122205002334H5007133306023012

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

8、求3.5模型建立與求解模型選用最短路模型 最短路模型解決的就是圖論中任意兩點(diǎn)之間的最短路問(wèn)題。模型應(yīng)用及求解我們的指標(biāo)是 首先對(duì)數(shù)據(jù)進(jìn)行抽取，得到我們所需要的數(shù)值，并把它存儲(chǔ)到矩陣 這應(yīng)該是一個(gè)9*9的矩陣，其次我們可以按照最短路的模型使用Dijkstra算法來(lái)進(jìn)行求解，得到的值便是S到任一點(diǎn)的最短距離值，最后按照路徑還原的思想還原修建的路徑即可。3.6模型評(píng)價(jià)最短路模型的是行能夠較好的解決單源最短路徑問(wèn)題，可以較好的模擬出路徑修建，得到的一定是最短的路徑，能夠達(dá)到預(yù)期要求的效果，得到的最終結(jié)果如附錄里“3. 應(yīng)用實(shí)例結(jié)果輸出”所示第四章. 參考文獻(xiàn)1. 韓中庚著，數(shù)學(xué)建模方法與應(yīng)用，高等教育

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

10、<cmath>#include <vector>using namespace std;const double INF = 0xFFFFFFF;const int MAX_N = 10005;/ 表示最大有頂點(diǎn)10005個(gè)；int n,m;/ 表示有n個(gè)結(jié)點(diǎn)；給出了m條邊double GMAX_NMAX_N;/ 用鄰接矩陣來(lái)從這個(gè)圖double distMAX_N;/ 表示起點(diǎn)到當(dāng)前點(diǎn)的最短距離bool vistMAX_N;int prevMAX_N;vector < int> getpath(int t) / 路徑還原可變長(zhǎng)數(shù)組類(lèi)型 vector<

11、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)記集合最短的點(diǎn) if(!visti && mx > disti) mx = disti; v = i; if(v = -1) brea

12、k; vistv = true; for(int i = 1; i <= n; i+) /用當(dāng)前的到的值來(lái)松弛其他不在標(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 = false; previ = -1; int main() freopen

13、("data.in","r",stdin);/ 默認(rèn)數(shù)據(jù)讀入用data.in freopen("data.out","w",stdout);/ 輸出默認(rèn)到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; i+) printf("出水口到目標(biāo)點(diǎn) %d 的最短距離

14、 = %.0fn",i,disti); vector<int> q = getpath(i); printf("目標(biāo)點(diǎn) %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)用實(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 的最短距離 = 1目標(biāo)點(diǎn) 3 的路徑為1-> 3 出水口到目標(biāo)點(diǎn) 4 的最短距離 = 1目標(biāo)點(diǎn) 4 的路徑為1-> 4 出水口到