創(chuàng)業(yè)收益的規(guī)劃模型

基于Dijkstra算法的環(huán)游世界最佳路徑選擇數(shù)學(xué)建模協(xié)會(huì)編號(hào)：69姓名1：李明宇姓名2：楊軍姓名3：艾建行指導(dǎo)教師：李學(xué)文評閱編號(hào)：評閱專家1評閱專家2評閱專家3評閱專家4評閱專家5摘要本文根據(jù)題中所給數(shù)據(jù)，通過建立基于Dijkstra算法的最短路徑模型，為著名的《80天環(huán)游世界》中福格的壯舉選取最優(yōu)路徑，從而判斷出基于當(dāng)時(shí)的交通環(huán)境不能實(shí)現(xiàn)該想法，同時(shí)解決了當(dāng)起點(diǎn)發(fā)生改變時(shí)能否通過尋找最佳路徑，達(dá)到在一定時(shí)間內(nèi)完成環(huán)游世界的目的。在具體求解過程中，我們將從倫敦環(huán)游世界的不同路線的交通網(wǎng)絡(luò)圖劃分成五個(gè)小區(qū)域，然后利用Dijkstra算法求取出各個(gè)區(qū)域的不同起點(diǎn)到各個(gè)終點(diǎn)的最短路徑，然后將五個(gè)區(qū)域組合，得到簡化后的環(huán)游世界的交通網(wǎng)絡(luò)圖，最后用同一算法得到從倫敦出發(fā)，環(huán)游世界的最短天數(shù)為81天，最佳路徑為：1倫敦6Pairs7Barcelona12Budapest17Athens22Cairo23Aden28Bombay31Calcutta33Singapore35HongKong37Shanghai39Yokohama41SanFrancisco47Denver50Chicago53NewYork1倫敦，從而得出他不能贏得賭注的結(jié)論，同時(shí)，80天與81天相差不多，且注意到題中31-32﹑15-19之間所需天數(shù)未給出，若已知該時(shí)間且不長，則很有可能所需天數(shù)少于80天。運(yùn)用類似方法計(jì)算出當(dāng)環(huán)游世界的起點(diǎn)變?yōu)樯虾r(shí)，依據(jù)同一交通路線圖并且在交通環(huán)境沒有變化的前提下，得到環(huán)游世界的最短天數(shù)為77天，最短路徑為：37Shanghai39Yokohama41SanFrancisco47Denver50Chicago53NewYork2Lisbon4Madrid7Barcelona12Budapest17Athens22Cairo23Aden28Bombay31Calcutta33Singapore35HongKong37Shanghai，從而得到此時(shí)他可以贏得賭注的結(jié)論。最后，我們對Diskstra算法進(jìn)行了優(yōu)化，從而提高了求最短路徑時(shí)的運(yùn)行速度，增加了算法的執(zhí)行效率。關(guān)鍵字：Dijkstra算法最優(yōu)路徑分區(qū)簡化標(biāo)號(hào)法一問題重述在儒勒·凡爾納的著名小說《環(huán)游世界80天》中，英國紳士福格在倫敦與人打賭能夠在80天內(nèi)環(huán)游世界，這在當(dāng)時(shí)的1872年是一個(gè)了不起的壯舉。當(dāng)時(shí)最快的旅行方式是火車和輪船，然而世界上大部分地區(qū)還是靠馬車、大象、驢子或者步行來旅行。下面是一個(gè)從倫敦環(huán)游世界不同路線的交通網(wǎng)絡(luò)圖，福格選擇的是往東走，每段路線所需要的天數(shù)顯示在圖上，旅行的時(shí)間基于1872年能采用的旅行方式以及距離。請?jiān)O(shè)計(jì)一個(gè)算法為福格選擇一條最佳路徑，即環(huán)游世界天數(shù)最短，你選擇的路徑能讓他贏得賭注嗎？如果他在別的地方與人打賭，比如紐約或者上海，結(jié)果會(huì)怎樣？交通網(wǎng)絡(luò)圖如下：二問題分析1.對問題一的分析：問題一要求通過設(shè)計(jì)一個(gè)算法選擇最佳路徑，并判斷福格是否能在八十天內(nèi)環(huán)游世界。我們可以通過將題中所給的交通網(wǎng)絡(luò)路線圖分區(qū)域?qū)ふ易罴崖窂剑_(dá)到簡化的效果，最后得到合并后的簡化的交通路線圖，從而得到最短路徑以及此時(shí)所需的時(shí)間。2.對問題二的分析：問題二將環(huán)游世界的起點(diǎn)改變?yōu)樯虾；蚣~約，在此我隊(duì)對從上海出發(fā)繼續(xù)向東旅行的情況利用相似的方法進(jìn)行求解，從而判斷出此時(shí)的最短路徑及所需最少的時(shí)間。三模型假設(shè)與符號(hào)說明(一)模型假設(shè)題中所給的交通網(wǎng)絡(luò)路線圖所提供的時(shí)間準(zhǔn)確。福格在旅行中沒有發(fā)生意外情況導(dǎo)致旅行路線發(fā)生改變。起點(diǎn)改變時(shí)其他條件均不變。除出發(fā)點(diǎn)外，每個(gè)地點(diǎn)只到達(dá)一次。(二)符號(hào)說明由頂點(diǎn)V,弧A,和權(quán)值W組成的有向網(wǎng)絡(luò)PD中從到的一條路P中所有弧的權(quán)之和到自身的長度四模型建立與求解1問題一的分析與求解（1）模型的引入：取最短路徑問題給定有向網(wǎng)絡(luò)，任意弧，有權(quán)，給定D中的兩個(gè)頂點(diǎn)，。設(shè)P是D中從到的一條路，定義路P的權(quán)（長度）是P中所有弧的權(quán)之和，記為。最短路問題就是要在所有從到的路中，求一條路P0，使稱是從到的最短路。路P0的權(quán)稱為從到的路長,記為。Dijkstra算法思想：將中到所有其它頂點(diǎn)的最短路按其路長從小到大排列為：表示到自身的長度，相應(yīng)最短路記為：一定只有一條弧，記取最小值的點(diǎn)為，。假定的值已求出，對應(yīng)的最短路分別為：記則使上式達(dá)到最小值的點(diǎn)可取為。計(jì)算過程中可采用標(biāo)號(hào)方法：中的點(diǎn)，值是到的最短路長度，相應(yīng)的點(diǎn)記“永久”標(biāo)號(hào)；中的點(diǎn)，值是到的最短路長度的上界，相應(yīng)的點(diǎn)記“臨時(shí)”標(biāo)號(hào)，供進(jìn)一步計(jì)算使用。前點(diǎn)標(biāo)號(hào):表示點(diǎn)到的最短路上的前一點(diǎn)。如，表示vs到的最短路上前一點(diǎn)是。Dijkstra算法步驟：第1步：令,則令，,,，第2步：(選永久標(biāo)號(hào))在中選一點(diǎn)，滿足如果，停止，從到中各點(diǎn)沒有路；否則，轉(zhuǎn)第3步。第3步：（給點(diǎn)永久性標(biāo)號(hào)）令如果，結(jié)束，到所有的點(diǎn)的最短路已經(jīng)求得；否則，轉(zhuǎn)第4步。第4步：(修改臨時(shí)標(biāo)號(hào))對所有，如果，令否則,不變,把k換成k+1，返回第2步。（2）模型的求解：交通網(wǎng)絡(luò)圖如下：在這張地圖上所涉及的共有54個(gè)點(diǎn)，若再加上周期延拓，該數(shù)字將達(dá)到60，將這60個(gè)點(diǎn)之間的關(guān)系表現(xiàn)在矩陣中，不僅會(huì)造成輸入繁瑣﹑出錯(cuò)可能性大、移植性差等問題，還由于矩陣所占空間與點(diǎn)的個(gè)數(shù)成二次曲線，點(diǎn)過多將大幅度提升計(jì)算機(jī)的負(fù)擔(dān)，延長運(yùn)算時(shí)間，降低模型的效果。因此我們將這個(gè)地圖分為5個(gè)模塊，每個(gè)模塊中含有921個(gè)點(diǎn)不等，有效提高了建模的效率。這5個(gè)模塊分別如下所示：模塊1簡化后結(jié)果：上圖中，以倫敦為出發(fā)點(diǎn)，分別以18（St.Peterburg）、19（Moscow）、20（Kiev）、21（Istanbul）、17（Athens）為終點(diǎn)，得出了由起點(diǎn)到各終點(diǎn)的最短時(shí)間分別為9﹑13﹑13﹑10﹑11天。模塊2簡化后結(jié)果：模塊2以模塊1的終點(diǎn)：18（St.Peterburg）、19（Moscow）、20（Kiev）、21（Istanbul）、17（Athens）為起點(diǎn)，以27（Novosibirsk）、24（Tehran）、23（Aden）為終點(diǎn)，得出了各起點(diǎn)至終點(diǎn)的最短天數(shù)。圖中數(shù)字含義同模塊1.模塊3簡化后結(jié)果：模塊3以模塊2的終點(diǎn)：27（Novosibirsk）、24（Tehran）、23（Aden）為起點(diǎn)，以34（Beijing）、37（Shanghai）、35（HongKong）、33（Singapore）為終點(diǎn)，得出由各起點(diǎn)至終點(diǎn)的最短天數(shù)。模塊4簡化后結(jié)果：該模塊原理同前模塊，以34（Beijing）、37（Shanghai）、35（HongKong）、33（Singapore）為起點(diǎn)，以42（Seattle）、41（SanFrancisco）、43（LosAngeles）45（Panama）為終點(diǎn)。模塊5簡化后結(jié)果：以上為模塊5，以42（Seattle）、41（SanFrancisco）、43（LosAngeles）45（Panama）為起點(diǎn)，1（倫敦）、2（Lisbon）、3（Casablanca）為終點(diǎn)，本模塊中本不需要2（Lisbon）3（Casablanca），只需要終點(diǎn)倫敦即可，但考慮到模塊的完整性和后面模型的需要將其加入。經(jīng)過以上模塊的分解，我們將一個(gè)很大的地圖化解為5個(gè)較小的圖，這5個(gè)模塊的起點(diǎn)與終點(diǎn)之間的所有點(diǎn)就可以忽略不計(jì)，只考慮起點(diǎn)與終點(diǎn)之間的天數(shù)即可，將一個(gè)54點(diǎn)的圖化為了1+5+3+4+4=17點(diǎn)的圖，再將這個(gè)17點(diǎn)圖帶入Dijkstra算法中求解即可得出最短天數(shù)的路徑為：1倫敦6Pairs7Barcelona12Budapest17Athens22Cairo23Aden28Bombay31Calcutta33Singapore35HongKong37Shanghai39Yokohama41SanFrancisco47Senver50Chicago53NewYork1倫敦所需最短天數(shù)為：81天。80天與81天相差不多，且注意到題中31-32﹑15-19之間所需天數(shù)未給出，若已知該時(shí)間且不長，則很有可能所需天數(shù)少于80天。2模型二的求解：從上海繞行與從倫敦繞行思路相同，只是模塊稍有不同：模塊1：本模型中上海作為起點(diǎn)34（Beijing）35（HongKong）33（Singapore）本不需要，但考慮到模塊的完整性這里將其加入，圖中數(shù)字與前相同。模塊2：模塊3：模塊4：模塊5：利用Dijkstra算法中求解即可得出最短天數(shù)的路徑為：37Shanghai39Yokohma41SanFrancisco47Senver50Chicago53NewYork2Lisbon4Madrid7Barcelona12Budapest17Athens22Cario23Aden28Bombay31Calutta33Singapore35HongKong37Shanghai最短天數(shù)為77天，得出他如果在上海出發(fā)，則可以贏得賭注。五模型優(yōu)化由于經(jīng)典Dijkstra算法在節(jié)點(diǎn)個(gè)數(shù)較多時(shí)會(huì)出現(xiàn)運(yùn)行效率低，內(nèi)存占用大，出錯(cuò)率高，靈活性差等缺點(diǎn)，于是我們對經(jīng)典Dijkstra算法進(jìn)行了優(yōu)化，對搜索網(wǎng)絡(luò)進(jìn)行了分區(qū)域處理得到“優(yōu)化Dijkstra算法”從模型的求解過程可以看出，若將該地圖分為幾個(gè)模塊，即使要換一個(gè)地點(diǎn)來計(jì)算最短時(shí)間也可以很快解決，直接套用原模塊即可，但是若將整個(gè)地圖全部輸入矩陣中，一旦更換地點(diǎn)，將不得不重新輸入圖矩陣，圖的規(guī)模越大，這樣所浪費(fèi)的時(shí)間越多，出錯(cuò)率越高，分塊的優(yōu)點(diǎn)就充分體現(xiàn)了出來。優(yōu)化Dijkstra算法與原始Dijkstra算法的搜索范圍比較示意圖如圖2．2所示。由圖2．2可見，原始Dijkstra算法的搜索過程(見圖2．2a)，是以源點(diǎn)為圓心的一系列同心圓，搜索過程沒有考慮終點(diǎn)所在的方向或位置，在從源點(diǎn)出發(fā)的搜索過程中，其他結(jié)點(diǎn)與終點(diǎn)被搜索到的概率是相同的。“優(yōu)化Dijkstra算法”的搜索過程(見圖2．2b)是以源點(diǎn)和終點(diǎn)為焦點(diǎn)的一系列“同心橢圓”，永久標(biāo)記點(diǎn)的選取原則為：當(dāng)前結(jié)點(diǎn)距源點(diǎn)的最短距離與此結(jié)點(diǎn)到終點(diǎn)的直線距離之和最小者被選取為永久標(biāo)記點(diǎn)。所以搜索過程趨向于終點(diǎn)，搜索過程到達(dá)終點(diǎn)的速度明顯快于原始Di]kstm算法，搜索到的結(jié)點(diǎn)也少于原始Dijkstra算法。六參考文獻(xiàn)[1]費(fèi)培之圖和網(wǎng)絡(luò)及其應(yīng)用四川大學(xué)出版社1996.8[2]李雷基于地圖分區(qū)算法求解動(dòng)態(tài)最佳路徑的研究與實(shí)現(xiàn)江蘇大學(xué)碩士學(xué)位論文2004.6[3]楊長保，王開義，馬生密一種晟短路徑分析優(yōu)化算法的實(shí)現(xiàn)吉林大學(xué)學(xué)報(bào)(信息科學(xué)版)．第20卷，第2期，2002年6月[4]柬濤，范東明OlS分析中最短路徑問題的圈論解決方法四川測繪，2002年04期七附錄function[S,D]=minRoute(i,m,W)%圖與網(wǎng)絡(luò)論中求最短路徑的Dijkstra算法M-函數(shù)%i為最短路徑的起始點(diǎn),m為圖頂點(diǎn)數(shù),W為圖的帶權(quán)鄰接矩陣，%不構(gòu)成邊的兩頂點(diǎn)之間的權(quán)用inf表示。顯示結(jié)果為：S的每%一列從上到下記錄了從始點(diǎn)到終點(diǎn)的最短路徑所經(jīng)頂點(diǎn)的序號(hào)；%D是一行向量，記錄了S中所示路徑的大小;dd=[];tt=[];ss=[];ss(1,1)=i;V=1:m;V(i)=[];dd=[0;i];%dd的第二行是每次求出的最短路徑的終點(diǎn)，第一行是最短路徑的值kk=2;[mdd,ndd]=size(dd);while~isempty(V)[tmpd,j]=min(W(i,V));tmpj=V(j);fork=2:ndd[tmp1,jj]=min(dd(1,k)+W(dd(2,k),V));tmp2=V(jj);tt(k-1,:)=[tmp1,tmp2,jj];endtmp=[tmpd,tmpj,j;tt];[tmp3,tmp4]=min(tmp(:,1));iftmp3==tmpd,ss(1:2,kk)=[i;tmp(tmp4,2)];else,tmp5=find(ss(:,tmp4)~=