最短路徑--導(dǎo)航

1、數(shù)學(xué)建模最短路問題模擬GPS衛(wèi)星導(dǎo)航系統(tǒng)計(jì)算北京市西四到天壇公園北門的最短路問題。周盛友2013/6/22項(xiàng)目名稱最短路徑問題人員情況周盛友人員分工情況論文：周盛友模型：周盛友假設(shè)討論：周盛友算法：周盛友摘要本文是一個(gè)與實(shí)際息息相關(guān)的最短路徑問題，通過以北京市西四城區(qū)到天壇公園北門為例子去論述這個(gè)原理及算法，模擬出GPS衛(wèi)星導(dǎo)航的基本原理。它是自動(dòng)定位車輛的當(dāng)前位置，并執(zhí)行接收用戶反饋的信息：起點(diǎn)，終點(diǎn)。在內(nèi)部進(jìn)行數(shù)據(jù)的處理，經(jīng)過最短路徑的幾種算法原理，找出最合適的一種反饋給用戶。經(jīng)過模型的設(shè)計(jì)后，得出的數(shù)據(jù)與網(wǎng)上查詢的最短路結(jié)果吻合。對(duì)于處理這個(gè)問題，如何做到擬合性較精確的的模擬，以下我提出

2、了一個(gè)數(shù)學(xué)模型：矩陣對(duì)角線區(qū)域模型。針對(duì)在實(shí)際的情況下兩點(diǎn)連線距離最小而延伸的矩陣區(qū)域范圍內(nèi)求對(duì)角兩點(diǎn)之間的最短距離。利用Matlab軟件編程，進(jìn)行模擬，反饋詳細(xì)的信息給用戶。并提出在多種相同的情況下根據(jù)實(shí)時(shí)路況，途徑紅路燈的多少，周邊風(fēng)景等多種客觀因素進(jìn)行綜合性的分析，反饋用戶最滿意的一條路線。改進(jìn)模型，對(duì)于同時(shí)擁有多條最短路徑，根據(jù)用戶的需求進(jìn)行客觀分析問題，導(dǎo)入權(quán)重，進(jìn)行篩選，得出唯一解。關(guān)鍵字： 最短路徑 矩陣 衛(wèi)星導(dǎo)航 篩選1、 問題重述最短路徑問題是圖論研究中的一個(gè)經(jīng)典算法問題，旨在尋找圖（由結(jié)點(diǎn)和路徑組成的）中兩結(jié)點(diǎn)之間的最短路徑。搜集資料，作一個(gè)最短路徑問題算法的專題報(bào)告，闡述

3、最短路徑的的幾種算法原理，并利用最短路徑算法，解決下面的問題：駕車旅行時(shí)，GPS汽車導(dǎo)航儀會(huì)自動(dòng)確定車輛的所在位置，并以此為坐標(biāo)，幫你選擇一條涵蓋起點(diǎn)和終點(diǎn)的最佳的道路網(wǎng)絡(luò)圖。假設(shè)你在北京駕車，試建立數(shù)學(xué)模型模擬汽車導(dǎo)航儀選擇一條從西四去往目的地天壇公園北門的最佳行車線路（地圖上黃色的路線是可行車道路，里程數(shù)據(jù)可通過百度地圖獲得）。2最短路徑的的幾種算法原理一、 迪杰斯特拉（dijkstra）算法原理首先，引進(jìn)一個(gè)輔助向量D，它的每個(gè)分量D表示當(dāng)前所找到的從始點(diǎn)v到每個(gè)終點(diǎn)vi的最短路徑的長度。如D3=2表示從始點(diǎn)v到終點(diǎn)3的路徑相對(duì)最小長度為2。這里強(qiáng)調(diào)相對(duì)就是說在算法過程中D的值是在不斷逼

4、近最終結(jié)果但在過程中不一定就等于最短路徑長度。它的初始狀態(tài)為：若從v到vi有弧，則D為弧上的權(quán)值；否則置D為。顯然，長度為 Dj=MinD | viV 的路徑就是從v出發(fā)的長度最短的一條最短路徑。此路徑為(v,vj)。 那么，下一條長度次短的最短路徑是哪一條呢？假設(shè)該次短路徑的終點(diǎn)是vk，則可想而知，這條路徑或者是(v,vk)，或者是(v,vj,vk)。它的長度或者是從v到vk的弧上的權(quán)值，或者是Dj和從vj到vk的弧上的權(quán)值之和。 一般情況下，假設(shè)S為已求得最短路徑的終點(diǎn)的集合，則可證明：下一條最短路徑（設(shè)其終點(diǎn)為X）或者是弧(v,x)，或者是中間只經(jīng)過S中的頂點(diǎn)而最后到達(dá)頂點(diǎn)X的路徑。因此

5、，下一條長度次短的最短路徑的長度必是Dj=MinD | viV-S 其中，D或者是弧(v,vi)上的權(quán)值，或者是Dk(vkS)和弧(vk,vi)上的權(quán)值之和。迪杰斯特拉算法描述如下： 1）arcs表示弧上的權(quán)值。若不存在，則置arcs為（在本程序中為MAXCOST）。S為已找到從v出發(fā)的最短路徑的終點(diǎn)的集合，初始狀態(tài)為空集。那么，從v出發(fā)到圖上其余各頂點(diǎn)vi可能達(dá)到的最短路徑長度的初值為D=arcsLocate Vex(G,v),i viV 2）選擇vj，使得Dj=MinD | viV-S 3）修改從v出發(fā)到集合V-S上任一頂點(diǎn)vk可達(dá)的最短路徑長度。二、蟻群算法的原理 自然界中的螞

6、蟻是沒有視覺的，既不知道向何處尋找食物，也不知道發(fā)現(xiàn)食物后如何返回自己的巢穴，它僅僅依賴于同類散發(fā)在周圍環(huán)境中的特殊物質(zhì)信息素的軌跡，來決定自己何去何從。但是盡管沒有任何先驗(yàn)的知識(shí)，但螞蟻們還是有能力找到從其巢穴到食物源的最佳路徑。所以大量研究發(fā)現(xiàn)，同一蟻群中的螞蟻能感知信息素及其強(qiáng)度，后來的螞蟻會(huì)傾向于朝信息素濃度高的方向移動(dòng)，而移動(dòng)留下的信息素又會(huì)對(duì)原有信息素進(jìn)行加強(qiáng)，后續(xù)的螞蟻而后續(xù)的螞蟻選擇該路徑的可能性也越大。由于在相同時(shí)間段 內(nèi)越短的路徑會(huì)被越多的螞蟻訪問,所以后續(xù)的螞蟻選擇較短路徑的可能性也越大,最后所有的螞蟻都走最短的那條路徑。三、動(dòng)態(tài)規(guī)劃原理概述動(dòng)態(tài)規(guī)劃最優(yōu)化原理，

7、可以這樣闡述：一個(gè)最優(yōu)化策略不倫過去狀態(tài)和決策如何，對(duì)前面的決策所形成的狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)策略，及其子決策總是最優(yōu)的，任何思想方法都有一定的局限性，動(dòng)態(tài)規(guī)劃也有其適用的條件，如果某階段的狀態(tài)給定后，則在這個(gè)階段以后的過程的發(fā)展不受這階段以前各段狀態(tài)的影響，這個(gè)性質(zhì)稱為無后效性，適用動(dòng)態(tài)規(guī)劃的問題必須滿足這個(gè)性質(zhì)；其次還需滿足上述最優(yōu)化原理，動(dòng)態(tài)規(guī)劃基本思想一是正確地寫出基本的遞推關(guān)系和恰當(dāng)?shù)倪吔鐥l件；二是在多階段決策過程中，動(dòng)態(tài)規(guī)劃方法是既把當(dāng)前一段和后來各段分開，又把當(dāng)?shù)男б婧臀磥硇б娼Y(jié)合起來考慮的一種多階段決策的最優(yōu)化的方法，每階段決策和選取是從全局來考慮的，與該段的最優(yōu)選

8、擇的答案一般是不同的；三是在求整個(gè)問題的最優(yōu)策略時(shí)，由于出事狀態(tài)是已知的，而每階段的決策又都是改階段狀態(tài)的函數(shù)，因而最優(yōu)策略所經(jīng)過的各階段狀態(tài)便可逐次變換得到，從而確定最優(yōu)路線，簡而言之動(dòng)態(tài)規(guī)劃的基本思想就是把全局的問題化為局部的問題，為了全局最優(yōu)必須局部最優(yōu)。四、弗洛伊德算法 原理（Floyd-Wrashall）Floyd-Warshall算法的原理是動(dòng)態(tài)規(guī)劃。設(shè)Di,j,k為從i到j(luò)的只以(1.k)集合中的節(jié)點(diǎn)為中間結(jié)點(diǎn)的最短路徑的長度。1. 若最短路徑經(jīng)過點(diǎn)k，則Di,j,k = Di,k,k  1 + Dk,j,k 

9、 1；2. 若最短路徑不經(jīng)過點(diǎn)k，則Di,j,k = Di,j,k  1。因此，Di,j,k = min(Di,k,k  1 + Dk,j,k  1,Di,j,k  1)。在實(shí)際算法中，為了節(jié)約空間，可以直接在原來空間上進(jìn)行迭代，這樣空間可降至二維。（見下面的算法描述）Floyd-Warshall算法的描述如下：for k  1 to n do for i  1 to n do

10、 for j  1 to n do if (Di,k + Dk,j < Di,j) then Di,j  Di,k + Dk,j;其中Di,j表示由點(diǎn)i到點(diǎn)j的代價(jià)，當(dāng)Di,j為 表示兩點(diǎn)之間沒有任何連接。3、最短路的背景介紹和發(fā)展一：背景介紹 設(shè)計(jì)模擬GPS衛(wèi)星導(dǎo)航求最短路徑問題。1） 求出北京市西四到天壇公園北門的最短路徑 2) 在社會(huì)生活中，最短距離的運(yùn)用相當(dāng)廣泛。

11、除了該課題外，還有于此相關(guān)的城市道路的設(shè)計(jì)，交通線路的設(shè)計(jì)，旅游景點(diǎn)的設(shè)計(jì)等等。除了路徑長度方面外，到兩地花費(fèi)的最少、時(shí)間的最短等等都是同樣的道理。二：發(fā)展以后，這不僅僅是作為數(shù)學(xué)或圖論中的一個(gè)經(jīng)典算法，它將逐步適應(yīng)社會(huì)的各行事業(yè)的發(fā)展需求而作為一門學(xué)科去被人研究，分析。4、最短路的問題分析和數(shù)學(xué)模型4-1：問題的假設(shè)假設(shè)：1、 起點(diǎn)與終點(diǎn)作矩陣的對(duì)角線，且矩陣區(qū)域內(nèi)有最短路徑（連通起點(diǎn)與終點(diǎn)）解。2、 衛(wèi)星監(jiān)控期間，忽略突發(fā)事件造成的路面大面積出現(xiàn)維修而導(dǎo)致汽車無法通過的情況。分析討論：1、 模擬雷達(dá)搜索目標(biāo)時(shí)的情景，再結(jié)合坐標(biāo)軸的位置，設(shè)起點(diǎn)為原點(diǎn)（0,0）；搜索終點(diǎn)的象限，進(jìn)而確定矩陣的

12、面積范圍。2、 在實(shí)際過程過，道路的覆蓋方式無法完全理想化恰恰好在選取的矩陣區(qū)域內(nèi)，因此在處理過程中允許存在誤差，但要適當(dāng)。3、 節(jié)點(diǎn)與節(jié)點(diǎn)之間的選取問題：當(dāng)結(jié)點(diǎn)連接到下一結(jié)點(diǎn)時(shí)，出現(xiàn)多個(gè)端點(diǎn)的情況，但我們只選取最靠近終點(diǎn)的兩個(gè)結(jié)點(diǎn)或一個(gè)結(jié)點(diǎn)，其他舍去。4、 在做無向圖的時(shí)候采取矩陣形狀去進(jìn)行繪點(diǎn)，左上角為起點(diǎn)V1，右下角為終點(diǎn)Vn，這樣的好處是能很好模擬衛(wèi)星的監(jiān)測方式和與地圖的對(duì)應(yīng)地理信息。5、 選取結(jié)點(diǎn)的標(biāo)準(zhǔn)：不以公交站或標(biāo)志性建筑物等為結(jié)點(diǎn)，這樣會(huì)搞成信息的混亂度大大增大；我經(jīng)模擬衛(wèi)星從鳥瞰式的選取結(jié)點(diǎn)方式，最終決定選取轉(zhuǎn)彎路段（轉(zhuǎn)彎前必須包含兩個(gè)方向以上的十字路口）作為結(jié)點(diǎn)的選取標(biāo)準(zhǔn)。

13、4-2：數(shù)學(xué)模型-矩陣對(duì)角線區(qū)域模型4-2-1：通過對(duì)該矩陣范圍內(nèi)的所有滿足分析結(jié)果的結(jié)點(diǎn)進(jìn)行篩選，并繪制北京市西四到天壇公園北門的無向圖，如下圖：注：各街道名稱省略，可查百度地圖資料駕車>西四>天壇公園北門->把地圖擴(kuò)大到能看見街道名稱的范圍即可。4-2-2：Dijkstra模型的選取因?yàn)樽疃搪窂絾栴}的算法的根本核心是：從每一個(gè)子決策的最優(yōu)解逐漸推出最終最優(yōu)解，即可用到貪心算法的基本原理去實(shí)驗(yàn)Dijkstra算法。Dijkstra算法是貪心算法的一個(gè)典型體現(xiàn)。但由于我們本文的解是關(guān)于最初位置到最末位置的最短路問題求解，恰好滿足Dijkstra的最初理念，因此可以直接借用Di

14、jfastra算法，然后輸入矩陣W，得出結(jié)果。結(jié)果包含：V1-V24的最短距離，而且還能輸出結(jié)點(diǎn)與結(jié)點(diǎn)之間的索引，追溯回到V1。這個(gè)過程正是衛(wèi)星定位的最重要部分。注：用弗洛伊德算法 （Floyd-Wrashall）也可以。5、最短路的算法實(shí)現(xiàn)和代碼5-1：偽代碼a=ones(n)+inf;for i=1:n a(i,i)=0;end輸入結(jié)點(diǎn)與結(jié)點(diǎn)之間的權(quán)重：a(1,2)=1.6;a(1,3)=1.9a(21,22)=0.9;a(22,23)=0.7;for i： 2 to nfor j： 1 to （i-1）a（i，j） = a（j，i）；endend尋找矩陣最大值M = max（m

15、ax（a）開一個(gè)一維數(shù)組記錄每個(gè)頂點(diǎn)的狀態(tài)pb開一個(gè)索引數(shù)組用來記錄頂點(diǎn)的索引index2初始化數(shù)據(jù)While sum（pb）<n尋找沒有完成最優(yōu)的頂點(diǎn)：tb=find（pb=0）更新l（v）記錄最小值的頂點(diǎn)find（d（tb）=min（d（tb）若返回多個(gè)解，則取第一個(gè)即可并記錄為已完成最優(yōu)解的狀態(tài)尋找索引值If 索引值返回多解取第一個(gè)即可End記錄索引值到index2End5-2： N-S框圖輸入該無向圖的鄰接矩陣a初始化數(shù)據(jù)：A=a；n=length（a）輸入每兩個(gè)頂點(diǎn)之間的街道名稱，存進(jìn)一個(gè)數(shù)組load完成鄰接矩陣的對(duì)稱賦值： i=2：n尋找數(shù)組的最大值：M=max（max（a）

16、開一個(gè)用來記錄狀態(tài)最優(yōu)解的數(shù)組：pb（1：length（a）=0開一個(gè)一維索引矩陣：index2=;開一個(gè)儲(chǔ)存起點(diǎn)到各頂點(diǎn)的最短距離一維數(shù)組：d(1:length(a)=M;d（1）=0；temp=1；sum(pb)<length(a)從尾追溯索引頂點(diǎn)： index2=index n對(duì) i=n-1:-1:1 循環(huán)索引數(shù)組逆序儲(chǔ)存：indexinfo = index2(end:-1:1);輸出起點(diǎn)到終點(diǎn)的最短路徑：d（end）輸出起點(diǎn)到終點(diǎn)途徑的第一個(gè)街道名稱：loadindexinfo(1),indexinfo(2)對(duì)i=2:length(indexinfo)-1 循環(huán)對(duì)j=1：（i-1

17、）循環(huán)a(i,j) = a(j,i);尋找還沒有處理的頂點(diǎn)：tb=find(pb=0); 更新l（v）：d(tb)=min(d(tb),d(temp)+a(temp,tb);記錄最小值得位置：tmpb = find(d(tb)=min(d(tb);最優(yōu)解的位置，取出第一個(gè)：temp=tb(tmpb(1); 用來記錄最優(yōu)解狀態(tài)：pb(temp)=1; Yd(i)+A(i,n)=d(n)Nindex2=index2 i; n=i;Yindex2(end)=1NBreak；輸出各街道的名稱：loadindexinfo(i),indexinfo(i+1)5-3完整的Matlab代碼：function

18、Dijkf_one(a)n=length(a);A=a;load=cell(17,18);load1,2='文津街'load1,3='西單北大街'load2,4='景山前街'load2,5='北長街-南長街'load3,5='西長安街'load3,6='宣武門內(nèi)大街'load4,7='北河沿大街'load5,7='東長安街'load6,8='宣武門東大街'load6,9='宣武門外大街'load7,10='正義路'loa

19、d8,10='門前西-東大街'load8,11='南新華街'load9,11='騾馬市大街'load9,12='宣武門外大街'load10,13='門前東大街'load11,14='珠市口西大街'load11,15='虎坊路'load12,15='南橫東街'load13,16='祈年大街'load14,16='珠市口東大街'load14,17='門前大街'load15,17='北緯路'load16,18=

20、'祈年大街'load17,18='天壇路'for i=2:n for j=1:(i-1) a(i,j) = a(j,i); endendM=max(max(a); pb(1:length(a)=0; pb(1)=1; index1=1; index2=ones(1,length(a); d(1:length(a)=M; d(1)=0;temp=1;while sum(pb)<length(a) tb=find(pb=0); d(tb)=min(d(tb),d(temp)+a(temp,tb); tmpb = find(d(tb)=min(d(tb); te

21、mp=tb(tmpb(1); pb(temp)=1; endindex2=;index2=index2 n;for i=n-1:-1:1 if d(i)+A(i,n)=d(n) index2=index2 i; n=i; end if index2(end)=1 break; endendindexinfo = index2(end:-1:1);fprintf('起點(diǎn)（西四）到終點(diǎn)（天壇公園北門）的最短距離為：%dn',d(end);fprintf('所途徑的路徑為：n');fprintf('%s',loadindexinfo(1),indexi

22、nfo(2);for i=2:length(indexinfo)-1 fprintf('-> %s',loadindexinfo(i),indexinfo(i+1);end6、最短路的主要結(jié)果及其分析討論6-1:從百度地圖搜到的信息與實(shí)驗(yàn)結(jié)果作比較實(shí)驗(yàn)結(jié)果（輸入數(shù)據(jù)）得：百度地圖搜索結(jié)果：可以看出：實(shí)驗(yàn)?zāi)M的結(jié)果也從百度地圖搜到的結(jié)果很吻合，其中的誤差是我在建立模型選取結(jié)點(diǎn)的原則（兩端結(jié)點(diǎn)取一個(gè)街道的名字）導(dǎo)致的，因?yàn)檫@樣就會(huì)出現(xiàn)重復(fù)的街道現(xiàn)象，例如：祈年大街1-祈年大街2.其實(shí)它們都是同一條街道！但總的來說通過網(wǎng)上的數(shù)據(jù)錄入，然后再通過自己稍微改進(jìn)一下Dijkstra算

23、法，這樣得出的結(jié)果還是比較精確的。6-2：結(jié)果分析1、 從6-1的結(jié)果可知。數(shù)據(jù)不會(huì)出現(xiàn)大幅度的偏差，正因?yàn)橛辛诉@個(gè)“矩陣對(duì)角線區(qū)域模型”的建立。其原則模擬雷達(dá)搜索過程：以起點(diǎn)作為雷達(dá)中心，以掃描式的方法去確定終點(diǎn)的位置。然后再結(jié)合平面直角坐標(biāo)系，確定終點(diǎn)象限。最后通過靠終點(diǎn)方向最近點(diǎn)優(yōu)先選取-最多選取兩個(gè)點(diǎn)即可。不斷迭代到終點(diǎn)。這樣就會(huì)很好避免了結(jié)點(diǎn)的選取問題，也就是作了一步優(yōu)化問題，這是整個(gè)模型的首要關(guān)鍵。2、 隨后就是選取或設(shè)計(jì)合適的算法的時(shí)候。很明顯，Dijkstra算法與Floyd算法同樣可以使用。在這里我選取的是Dijkstra算法，并加以自己的修改，來充當(dāng)這個(gè)模型的主要算法。通過

24、每一步的最優(yōu)迭代到最終解的最優(yōu)，這是這個(gè)算法的主要思想。最后，順理成章求出我們想要的答案了。比與實(shí)際結(jié)果作比較，擬合度比較好！7:、模型的改進(jìn)7-1：結(jié)點(diǎn)的選取問題模型在選取結(jié)點(diǎn)的時(shí)候忽略了一個(gè)特例：若起點(diǎn)與終點(diǎn)共線（東、南、西、北方向），那么按照這個(gè)模型的原則應(yīng)該提供特例解。如：在共線的情況下1、改進(jìn)取點(diǎn)：以兩點(diǎn)連線為中線，往線的兩邊（包括線上的點(diǎn)）擴(kuò)散分別尋找第一個(gè)點(diǎn)作為結(jié)點(diǎn)。2、改進(jìn)區(qū)域：以靠近起點(diǎn)的方向選取最近的一個(gè)或多個(gè)次終點(diǎn)（次終點(diǎn)：它的下一個(gè)結(jié)點(diǎn)則是終點(diǎn)），連接所有篩選出來的點(diǎn)構(gòu)成無向圖，則這個(gè)便是改進(jìn)之后的區(qū)域。7-2：總體結(jié)果的優(yōu)化問題7-2-1：條件不足現(xiàn)該模型只給出了輸入

25、起點(diǎn)與終點(diǎn)后求出最短路徑的問題。但沒能與實(shí)際接軌。例如百度地圖的“最少時(shí)間”，“不走高速”等功能選取。但由于沒有詳細(xì)的道路信息數(shù)據(jù)，例如：可以繞小巷更新大街道路信息、人為主觀因素選取路線等等實(shí)際問題。因此無法作進(jìn)一步的研究。:7-2-2：二次優(yōu)化模型在選取最短路過程中，若有多解，則系統(tǒng)可以給出一個(gè)按照用戶輸入的其它客觀因素信息（道路周邊風(fēng)景、盡量途徑較少紅綠燈、不喜歡多轉(zhuǎn)彎的道路等等）進(jìn)行篩選最優(yōu)的一條，當(dāng)然其中要涉及的知識(shí)就是要摻進(jìn)各客觀因素的權(quán)重通過層次分析發(fā)的綜合篩選，給出在多解的情況下，滿足用戶需求的唯一一條道路。8、對(duì)本學(xué)期課程的總結(jié)和建議總結(jié)：1、 本學(xué)期的數(shù)學(xué)課程主要是計(jì)算機(jī)數(shù)學(xué)上機(jī)實(shí)踐為主，與上學(xué)期的理論課有一定的差別。本人認(rèn)為這個(gè)