數(shù)學(xué)建模比賽最短路徑問題

2015大學(xué)生數(shù)學(xué)建模競賽承諾書我們仔細(xì)閱讀了《全國大學(xué)生數(shù)學(xué)建模競賽章程》和《全國大學(xué)生數(shù)學(xué)建模競賽參賽規(guī)則》（以下簡稱為“競賽章程和參賽規(guī)則”，可從全國大學(xué)生數(shù)學(xué)建模競賽網(wǎng)站下載）。我們完全明白，在競賽開始后參賽隊員不能以任何方式（包括電話、電子郵件、網(wǎng)上咨詢等）與隊外的任何人（包括指導(dǎo)教師）研究、討論與賽題有關(guān)的問題。我們知道，抄襲別人的成果是違反競賽章程和參賽規(guī)則的，如果引用別人的成果或其他公開的資料（包括網(wǎng)上查到的資料），必須按照規(guī)定的參考文獻的表述方式在正文引用處和參考文獻中明確列出。我們鄭重承諾，嚴(yán)格遵守競賽章程和參賽規(guī)則，以保證競賽的公正、公平性。如有違反競賽章程和參賽規(guī)則的行為，我們將受到嚴(yán)肅處理。我們授權(quán)全國大學(xué)生數(shù)學(xué)建模競賽組委會，可將我們的論文以任何形式進行公開展示（包括進行網(wǎng)上公示，在書籍、期刊和其他媒體進行正式或非正式發(fā)表等）。我們參賽選擇的題號是（從A/B/C/D中選擇一項填寫）：B 我們的報名參賽隊號為（8位數(shù)字組成的編號）：所屬學(xué)校（請?zhí)顚懲暾娜喝輲煼秾W(xué)院參賽隊員(打印并簽名)：1.蔡惠芳1213010272.肖丁福1213010283.李雅萍121301020指導(dǎo)教師或指導(dǎo)教師組負(fù)責(zé)人(打印并簽名)：楊昔陽 （論文紙質(zhì)版與電子版中的以上信息必須一致，只是電子版中無需簽名。以上內(nèi)容請仔細(xì)核對，提交后將不再允許做任何修改。如填寫錯誤，論文可能被取消評獎資格。）日期：2015年5月17日賽區(qū)評閱編號（由賽區(qū)組委會評閱前進行編號）：目錄1.摘要…………………..32.問題的重述及分析…………………..43.符號說明……………..44.模型的分析，建立和求解…………..55.模型的評價和改進…………………..106.參考文獻……………..107.附錄…………………..11最短路徑問題摘要 由于保安資源有限，根據(jù)學(xué)校的實際情況與需求，泉州師院數(shù)學(xué)專業(yè)新引進了智能機器人---大白，目的是讓他自動在校園巡邏，以確保校園的安全。對于題中所給的三個問題，研究在不同現(xiàn)實背景下的最優(yōu)線路設(shè)計問題，即研究在約束條件下的最短路徑問題。針對本案例，我們采用了大量的科學(xué)分析方法，利用圖論中的各種知識，采用數(shù)據(jù)結(jié)構(gòu)里的最短路徑算法,也叫Dijkstra算法，對最優(yōu)線路的設(shè)計進行建模并使用MATLAB和lingo軟件進行編程求解。進行了一系列反復(fù)驗證，得出如下結(jié)果：問題一：根據(jù)所給問題與數(shù)據(jù)，先將題目中給出的地點，及其之間的線路看做是一個賦權(quán)連通簡單無向圖，使用幾何畫板優(yōu)化出地圖，利用圖論中最短路徑算法的知識建立起“遠(yuǎn)距離優(yōu)先模型”，求出最優(yōu)線路。在此基礎(chǔ)上，通過觀察分析計算對上述結(jié)果進行修正，然后，再采用窮舉法對問題結(jié)果進行驗證，結(jié)果與最終答案相吻合，最后確定了問題一的最優(yōu)路線為：問題一：根據(jù)所給問題與數(shù)據(jù)，先將題目中給出的地點，及其之間的線路看做是一個賦權(quán)連通簡單無向圖，使用幾何畫板優(yōu)化出地圖，利用圖論中最短路徑算法的知識建立起“遠(yuǎn)距離優(yōu)先模型”，求出最優(yōu)線路。在此基礎(chǔ)上，通過觀察分析計算對上述結(jié)果進行修正，然后，再采用窮舉法對問題結(jié)果進行驗證，結(jié)果與最終答案相吻合，最后確定了問題一的最優(yōu)路線為：問題二：根據(jù)所給問題，當(dāng)大白巡邏到6時，接到報警說1處有恐怖分子，需要盡快趕到現(xiàn)場，即求地點6到地點1之間的最短路徑。利用迪杰斯特拉算法（Dijkstra算法）建立起“兩點間最短距離模型”，再運用MATLAB進行編程并求解。最后得到了問題二的最優(yōu)路線為：68711121。問題三：我們給定大白一個具體任務(wù)：大白巡邏完圖中標(biāo)號的所有地點所用時間最短的線路。將圖中的線路看作直線，畫出優(yōu)化地圖，同第二問，也是求最短路徑問題，結(jié)合問題二的“兩點間最短距離模型”，建立“最近插入法模型”，用lingo編寫程序并求解，最后對問題結(jié)果進行驗證，確定了問題三的最優(yōu)線路為：A3A2A1A12A11A10A13A4A5A9A8A7A8A6。（關(guān)鍵詞：最短路徑、賦權(quán)連通簡單無向圖、迪杰斯特拉算法（Dijkstra算法）、最近插入法、圖論、窮舉法、幾何畫板、matlab）問題重述問題背景：由于保安資源有限，根據(jù)學(xué)校的實際情況，為了保證校園安全，也為了學(xué)生能更安全，放心的在校園里生活，泉州師院數(shù)學(xué)專業(yè)引進了智能機器人大白來巡邏校園。根據(jù)題目所給數(shù)據(jù)，運用數(shù)學(xué)建模方法，將實際復(fù)雜的問題理想模型簡化，設(shè)計出滿足題目要求的校園路徑，有很重要的顯示意義。試建立數(shù)學(xué)模型討論下列問題：1.請為大白規(guī)劃一條路徑，使得他可以用最少的時間走遍所有的路。當(dāng)然，有些路徑走多遍是允許的。所有路徑的距離詳見附錄。2.大白巡邏到6時，接到報警說1處有恐怖分子，他應(yīng)該怎么走才能最快到達1.3.請你為大白再布置一個實際的任務(wù)，并給出解答。我們給定的任務(wù)是：大白如何走可以用最少的時間走遍所有的地點。二、問題的分析對于問題一，要求在最短時間內(nèi)，大白在路徑可重復(fù)行走的情況下巡邏完所有的路，我們首先對該問題進行優(yōu)化，假定在外部條件（道路、人為等外部因素）的影響下，大白速度始終不變的情況下，把最短時間問題優(yōu)化成最短距離問題。利用圖論中最短路徑算法，我們建立起“遠(yuǎn)距離優(yōu)先模型”，使用該模型以及幾何畫板作圖求得最優(yōu)解。對于問題二，當(dāng)大白巡邏到6時，接到報警說1處有恐怖分子，即要在最短時間內(nèi)到達地點1處，同樣也為最短距離問題。相比于問題一，要求到達特定點1處的最短距離，路徑自然不能重復(fù)行走，即問題一所建立的模型將無法再繼續(xù)使用。因此，我們將這個問題再進一步優(yōu)化為：兩點間的最短距離問題。針對這一問題，我們想到使用迪杰斯特拉算法（Dijkstra算法）建立“兩點間最短距離模型”，用MATLAB編寫程序，利用這一程序來求解我們所需要的最短距離及其所走的路徑。對于問題三，要求大白用最短時間巡邏完圖中編號的所有地點的最短路線，同樣也是求最短距離問題。這個問題類似于“中國快遞員問題”，由此受到啟發(fā)并結(jié)合問題二的“兩點間最短距離模型”，建立“最近插入法模型”，用lingo編寫程序并求解出最優(yōu)線路。三、模型的假設(shè)與符號說明3.1模型的假設(shè)1.假設(shè)大白在校園內(nèi)單位時間內(nèi)行走的路程是不變的，即速度V保持不變。2.假設(shè)大白的狀態(tài)始終良好且行動能量始終充足，不會中途停下。3.1符號說明 V 表示大白的行走速度 表示數(shù)字i所標(biāo)示的地點 表示數(shù)字i所標(biāo)示的地點到數(shù)字j所標(biāo)示的地點之間的距離Inf表示無直達路徑V表示的集合（i=1,2,3…..,12,13）E表示路徑存在的集合G（V，E）表示帶權(quán)鄰接圖min表示行走路的過程中所經(jīng)過的距離path表示行走路線四、模型的建立及求解4.1.建模前準(zhǔn)備1.數(shù)據(jù)處理將題目所給圖形數(shù)據(jù)進行處理整合，優(yōu)化，使之便于思考。首先利用幾何畫板將題目所給的泉州師院的地圖優(yōu)化為如圖（1）所示；其次，將題目所給的各地點之間的距離進行數(shù)據(jù)處理，兩地點間的無直達路徑則用inf表示，整合到excel表格中，表（1）所示。圖(1)表（1）2.圖論中最短路徑的問題通常歸屬為三類：a.單源最短路徑問題：包括確定起點的最短路徑問題和確定終點的最短路徑問題。確定終點與確定起點的最短路徑問題相反。在無向圖中，確認(rèn)終點的問題與確認(rèn)起點的問題完全等同，在有向圖中確定了終點的問題等同于把所有路徑方向反轉(zhuǎn)為確定起點的問題。b.確定終點的最短路徑問題：即已知起點和終點，求兩結(jié)點之間的最短路徑。c.全局最短路徑問題：求局中所有的最短路徑。3.迪杰斯特拉算法（Dijkstra算法）迪杰斯特拉(Dijkstra)算法是典型的最短路徑路由算法，用于計算一個節(jié)點到其他所有節(jié)點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。Dijkstra算法能得出最短路徑的最優(yōu)解。其基本思想是，設(shè)置頂點集合S并不斷地作中心選擇來擴充這個集合。一個頂點屬于集合S當(dāng)且僅當(dāng)從源到該頂點的最短路徑長度已知。4.中國郵遞員問題著名圖論問題之一。郵遞員從郵局出發(fā)送信，要求對轄區(qū)內(nèi)每條街，都至少通過一次，再回郵局。在此條件下，怎樣選擇一條最短路線？此問題由中國數(shù)學(xué)家管梅谷于1960年首先研究并給出算法，故名。用圖論的語言描述就是指在一個邊賦權(quán)的圖中找一個閉道，使得這個閉道經(jīng)過每一條邊，并且閉道上所以邊的權(quán)和最小。如果圖本身就是一個歐拉圖，那么這個閉道就是歐拉閉道。如果圖不是歐拉圖，那么就有一些邊可能會經(jīng)過至少兩次。.4.2.1.“遠(yuǎn)距離優(yōu)先模型”的建立問題一在速度V保持不變的情況下，屬于圖論中最短路徑的問題分類中的第c類問題,全局最短路徑問題：求局中所有的最短路徑。在行走路徑是可以重復(fù)行走的條件下，要是全局路徑最短，則如果有重復(fù)行走到路徑，那么重復(fù)行走的路徑必須要盡可能的短，反過來說，路徑長的路就盡量只走一次?？紤]這樣的約束條件，在行走到每一地點遇岔路時，則優(yōu)先行走路徑長的岔路；若岔路的路徑等長，則優(yōu)先行走通往未走過路徑多的岔路。我們以這種行走規(guī)則為模型，并稱之為“遠(yuǎn)距離優(yōu)先模型”。4.2.2“遠(yuǎn)距離優(yōu)先模型”的求解1．將題中所給的地圖與數(shù)據(jù)優(yōu)化處理成加權(quán)無向圖如圖（1）所示?，F(xiàn)考慮大白要將所有的路都走遍，必然不可能所有的路都只走一遍，容易看出這一地點只有一條路可走。于是，為了避免重復(fù)走,考慮從出發(fā)，利用遠(yuǎn)距離優(yōu)先模型求解。讓大白優(yōu)先走遠(yuǎn)距離的路，重復(fù)走的路徑都是盡可能短，以達到走完全局路程最短，行走時間最少的目的。解得其一條路線為：路徑總長度為：2+5+1+1+5+2+6+2+2+3+6+2+2+5+1+1+5+1+1+1+2+2+1+1+1+1=622．利用窮舉法列舉多種路線驗證上訴路徑是否為所求的最優(yōu)解，例如一下三種路線:路線一：路徑總長度為：2+2+2+1+5+5+2+1+1+2+6+1+1+2+1+2+1+1+5+5+5+1+3+3+6=66路線二：路徑總長度:2+2+2+3+6+5+1+5+5+1+1+1+6+1+1+5+2+5+2+1+2+1+1+1+2=65路線三：路徑總長度為：5+2+2+2+1+1+2+2+1+1+1+1+2+5+1+6+5+5+5+1+2+2+2+3+3+6=693．路線一、二、三的路徑總長度分別為：66、65、69，均大于我們利用“遠(yuǎn)距離優(yōu)先模型”所求路徑的總長度62。即大白行走的最優(yōu)路線如圖二所示，其路線為：。路徑總長度為：62。圖（2）4.3.1“兩點間最短距離模型”的建立將途中校園地點看做節(jié)點（i=1,2，…13），可知該網(wǎng)絡(luò)是一個加權(quán)無向圖。巡邏員大白要在最短時間內(nèi)到達目的地。依據(jù)問題的要求及相關(guān)假設(shè)，建立相應(yīng)的模型并進行求解。我們先引入最小生成樹的簡單定義：給定一個無向連通帶權(quán)鄰接圖G（V，E）中的每一條邊權(quán)值為C。如果G的子圖G‘是一個包含G中所有定點的子圖，那么G’成為G的生成樹，如果G‘的邊的權(quán)值最小，那么G’成為G的最小生成樹。根據(jù)題目意思，定義：權(quán)為兩地點間的距離，如下表線路權(quán)線路權(quán)21112126151253522165定義V為，，，，，，，，，，，，的集合。定義E為,,,,,,,,,，,,,,,,,，,的集合G=（V，E）表示帶權(quán)鄰接圖，即表（1）匯總excel表格正是此帶權(quán)鄰接矩陣。根據(jù)迪杰斯特拉算法（Dijkstra算法）在全局選取一點作為中心，向外層層擴展，直到擴展到終點為止的思想建立模型求解第二問。在全局中選取一點X作為中心（即大白此時的位置），根據(jù)帶權(quán)鄰接矩陣表（1），所示向外層層擴展到終點Y（大白應(yīng)去的指定位置）為止，在這過程中用path記錄擴展的路線，用min記錄擴展過程中所經(jīng)過的距離。以此想法建立起模型，并稱之為“兩點間最短距離模型”。 4.3.2“兩點間最短距離模型”的求解針對問題二，要求兩個確定點間的最短路徑問題，采用數(shù)據(jù)結(jié)構(gòu)里的最短路徑算法,也叫Dijkstra算法,再運用MATLAB進行編程，MATLAB的編程程序見附錄2，最后求得最短距離min與最短距離的行走路path如下，即A6A8A7A11A12A1。線路圖如圖（3）所示：圖（3）4.4.1“最近插入法模型”的建立針對問題三，我們所提出的實際問題是：要使大白在最短的時間內(nèi)走完所有的地點，即相當(dāng)于求所有點都連接起來的最短距離。有些地點有好幾條不同的線路可以走，要使行走過所有點的距離最短，就要使有多條線路可走的地點走最短的線路。再結(jié)合“中國郵遞員問題”，從而建立了“最近插入法模型”。4.4.2“最近插入法模型”的求解針對問題三的求解，還是先考慮到了A3這個只有一條線路可走的地點。則由A3出發(fā)，大白在每一地點遇岔路時，則優(yōu)先行走路徑短的岔路；若岔路的路徑等長，則優(yōu)先行走通往未走過地點多的岔路。這樣就得到了一條路線，在此基礎(chǔ)上，通過觀察分析計算對上述結(jié)果進行修正，然后，再采用窮舉法對問題結(jié)果進行驗證，結(jié)果與最終答案相吻合，最后確定了問題一的最優(yōu)路線為：A3A2A1A12A11A10A13A4A5A9A8A7A8A6。如圖（4）所示：圖（4）五、模型的評價與改進方向5.1模型的優(yōu)點： 1.優(yōu)點在于利用matlab、lingo軟件程序大大節(jié)約了計算量。 2.模型配予圖片分析，形象化，直觀，形象，易理解。 3.語言、符號簡單.5.2模型的缺點： 模型相對理想化，忽略了道路、環(huán)境、機器等影響因素。5.3模型的改進方向：對于不可避免的誤差納入計算，使結(jié)果更加貼近生活、真實化。六、參考文獻[1].傅家良.運籌學(xué)方法與模型[M].上海,復(fù)旦大學(xué)出版社.2006年；[2].劉來福，曾文藝.數(shù)學(xué)模型與數(shù)學(xué)建模（第二版）.北京：北京師范大學(xué)出版社，2002；[3].蔡鎖章.數(shù)學(xué)建模原理與方法.北京：海洋出版社；七、附錄附錄1：學(xué)校地圖：附錄2：第二題matlab程序編程：function[min,path]=dijkstra(a,start,terminal)n=size(a,1);label(start)=0;f(start)=start;fori=1:nifi~=startlabel(i)=inf;end,ends(1)=start;u=start;whilelength(s)<nfori=1:nins=0;forj=1:length(s)ifi==s(j)ins=1;end,endifins==0v=i;iflabel(v)>(label(u)+a(u,v))label(v)=(label(u)+a(u,v));f(v)=u;end,end,endv1=0;k=inf;fori=1:nins=0;forj=1:length(s)ifi==s(j)ins=1;end,endifins==0v=i;ifk>label(v)k=label(v);v1=v;end,end,ends(length(s)+1)=v1;u=v1;endmin=label(terminal);path(1)=terminal;i=1;whilepath(i)~=start;path(i+1)=f(path(i));i=i+1;endpath(i)=start;L=length(path);path=path(L:-1:1);[min,path]=dijkstra(a,6,1)min=11path=68711121附錄:3：第三題lingo程序編程:model:sets:didian/1..13/:u;link(didian,didian)/1,21,121,132,32,42,134,54,135,65,96,76,87,87,118,99,1010,1110,1311,1212,13/:c,X;endsetsdata:c=02100000100000100000100000100000100000100000100000100000212025100000100000100000100000100000100000100000100000110000020100000100000100000100000100000100000100000100000100000100000100000510000001100000100000100000100000100000100000100000510000010000010000010610000010000031000001000001000001000001000001000001000001000006052100000100000100000100000100000100000100000100000100000