畢業(yè)設(shè)計(jì)——電子地圖與最短路徑算法的結(jié)合

1、<p>　　本科畢業(yè)設(shè)計(jì)（論文）</p><p>　　題　　目：電子地圖與最短路徑算法的結(jié)合</p><p>　　院　　系：　　　 數(shù)理學(xué)院　 　 　　</p><p>　　專業(yè)年級(jí)：　信息與計(jì)算科學(xué)專業(yè)2009級(jí) </p><p>　　學(xué)生姓名：　xx 學(xué)號(hào)：　 　</p><p>　　指導(dǎo)

2、教師：　　　　　xx　　　　 　</p><p>　　2013年 6月 3日</p><p><b>　　摘 要</b></p><p>　　最短路徑問題在圖論研究中是一個(gè)長(zhǎng)盛不衰的經(jīng)典問題，旨在尋找圖中指定兩結(jié)點(diǎn)間的最短路徑；而電子地圖如今蓬勃發(fā)展，依托計(jì)算機(jī)成象等技術(shù)，直觀的為人們服務(wù)。電子地圖需要借助最短路徑算法，得出指定起始點(diǎn)至目

3、的地，并且同時(shí)滿足需求的行進(jìn)路線。</p><p>　　二者的結(jié)合，在促進(jìn)彼此發(fā)展的同時(shí)，更為人們提供越發(fā)顯著的幫助。而探討二者結(jié)合，一方面要學(xué)習(xí)最短路徑問題，了解當(dāng)前已知的最短路徑算法，如適用于單源非負(fù)的算法，所有頂點(diǎn)之間的可負(fù)的算法等；另一方面要懂得電子地圖是如何將現(xiàn)實(shí)中的交通網(wǎng)絡(luò)數(shù)據(jù)化，抽象為一般有向圖。</p><p>　　電子地圖與最短路徑算法結(jié)合的前提是電子地圖的“繪制”：無論

4、是對(duì)哪種最短路徑算法，他們得以實(shí)施，實(shí)現(xiàn)的前提都是有向圖或無向圖的出現(xiàn)。而在“繪制”電子地圖時(shí)，最為關(guān)鍵的就是建立城市交通網(wǎng)絡(luò)數(shù)據(jù)模型。</p><p>　　電子地圖與最短路徑算法結(jié)合的核心是最短路徑算法的實(shí)現(xiàn)：如何在已知的交通有向圖或無向圖上，實(shí)現(xiàn)最短路徑算法，得到所求路徑，并保證準(zhǔn)確有效的到達(dá)，是電子地圖與最短路徑二者結(jié)合最突出，最核心的問題。</p><p>　　關(guān)鍵詞：電子地圖；最

5、短路徑算法；數(shù)據(jù)模型 </p><p>　　The Combination of Electronic Map and the Shortest Path Algorithm</p><p><b>　　Abstract</b></p><p>　　The shortest path problem in graph theory is an

6、enduring problem, aims to find diagrams specify the shortest path between two nodes. With the development of electronic maps which depends on computer imaging technology, it service intuitively for people. Electronic map

7、 need use a shortest path algorithm, and gets the road from the starting point to destination, and meets the demand of route at the same time. </p><p>　　The combination of both, in promoting the development

8、of each other at the same time, more people gain increasingly significant help. And explore this combination, on the one hand to study the shortest path problem, understand the currently known shortest path algorithm, su

9、ch as Dijkstra algorithm dispose for single-source non-negative, Floyd algorithm manage between all vertices of the algorithm can be negative, on the other hand to understand digital electronic map is how to real traffic

10、 netwo</p><p>　　Electronic map combined with the shortest path algorithm is the premise of electronic map in the "drawing": for all of shortest path algorithm, they can implement, implementation is

11、 the premise of directed graph or undirected graph. In the "drawing" electronic map, the key is to set up the urban traffic network data model. </p><p>　　Electronic map combined with the shortest p

12、ath algorithm is the core of the realization of the shortest path algorithm: how to achieve the shortest path algorithm in the known traffic directed graph or undirected graph, get demanding path, and ensure the accurate

13、 and effective reach, is the most prominent and the most core problem in the combination between electronic map and shortest path algorithm.</p><p>　　Key Words：Electronic Map；Shortest Path Algorithm；The Data

14、 Model</p><p><b>　　目 錄</b></p><p><b>　　摘 要I</b></p><p>　　AbstractII</p><p><b>　　引 言1</b></p><p><b>　　1

15、基本概念2</b></p><p>　　1.1 圖論基本概念2</p><p>　　1.1.1 圖的基本概念2</p><p>　　1.1.2 鄰接矩陣3</p><p>　　1.1.3 鄰接表3</p><p>　　1.2 最短路的基本概念4</p><p>　　1.2

16、.1 最短路問題4</p><p>　　1.2.2 單目標(biāo)最短路徑問題4</p><p>　　1.2.3 單對(duì)結(jié)點(diǎn)間的最短路徑問題4</p><p>　　1.3 電子地圖的基本概念5</p><p>　　1.3.1 電子地圖的基本性質(zhì)5</p><p>　　1.3.2 電子地圖的一般特點(diǎn)5</p>

17、;<p>　　1.3.3 地理信息系統(tǒng)GIS5</p><p>　　2 最短路問題的各種算法6</p><p>　　2.1 Dijkstra算法6</p><p>　　2.1.1 Dijkstra算法的原理6</p><p>　　2.1.2 Dijkstra算法實(shí)現(xiàn)7</p><p>　　2.2

18、 Bellman-Ford算法7</p><p>　　2.2.1 Bellman-Ford算法的原理8</p><p>　　2.2.2 Bellman-Ford算法實(shí)現(xiàn)8</p><p>　　2.3 SPFA算法9</p><p>　　2.3.1 SPFA算法的思想9</p><p>　　2.3.2 SPFA

19、算法的實(shí)現(xiàn)9</p><p>　　2.4 Floyd算法10</p><p>　　2.4.1 Floyd算法的思想10</p><p>　　2.4.2 Floyd算法的實(shí)現(xiàn)10</p><p>　　2.5 其他算法——A*(A-Star)算法11</p><p>　　3 城市交通網(wǎng)絡(luò)數(shù)據(jù)模型12</p

20、><p>　　3.1 電子地圖數(shù)據(jù)需滿足的技術(shù)要求12</p><p>　　3.2 電子地圖基礎(chǔ)數(shù)據(jù)的整理12</p><p>　　3.2.1 道路，建筑物的錄入12</p><p>　　3.2.2 坐標(biāo)系的轉(zhuǎn)換12</p><p>　　3.2.3 地形圖的分層、縮編13</p><p>

21、　　3.2.4 地形圖的接邊與圖幅分幅13</p><p>　　3.3 城市交通網(wǎng)絡(luò)數(shù)據(jù)模型的管理13</p><p>　　3.3.1 格網(wǎng)管理13</p><p>　　3.3.2 道路網(wǎng)絡(luò)數(shù)據(jù)區(qū)域管理13</p><p>　　3.3.3索引數(shù)據(jù)的管理14</p><p>　　4 電子地圖與最短路徑算法的結(jié)合

22、15</p><p>　　4.1 競(jìng)賽原題15</p><p>　　4.2 問題分析16</p><p>　　4.3建立道路的網(wǎng)絡(luò)數(shù)據(jù)模型17</p><p>　　4.4 管械范圍求解17</p><p>　　4.5 調(diào)度方案的求解19</p><p>　　4.6 平臺(tái)增加個(gè)數(shù)及位置

23、的求解20</p><p><b>　　結(jié) 論23</b></p><p><b>　　參考文獻(xiàn)24</b></p><p><b>　　附 錄25</b></p><p><b>　　致 謝28</b></p><

24、;p><b>　　引 言</b></p><p>　　科技讓世界更緊密，人們的腳步不斷在一個(gè)個(gè)陌生的城市留下足跡。在陌生的地方，如何到達(dá)目的地，如何正確到達(dá)目的地，如何快速正確到達(dá)目的地，是出行者不得不考慮的問題。隨著外出頻率和距離的增加，衛(wèi)星導(dǎo)航系統(tǒng)在我們生活中扮演的角色不斷提高。</p><p>　　獨(dú)立的衛(wèi)星導(dǎo)航系統(tǒng)，在軍事方面，可以擺脫外國(guó)的封鎖，建

25、立獨(dú)立自主的國(guó)防體系；在戰(zhàn)略方面，可以對(duì)他國(guó)形成一定威脅力，為信息化建設(shè)提供保障；在民用方面，更可以創(chuàng)新搭載平臺(tái)，促進(jìn)和推動(dòng)經(jīng)濟(jì)社會(huì)發(fā)展。而衛(wèi)星導(dǎo)航系統(tǒng)最日常，最普及，最為人所用，為人所知的用途，就是與我們生活息息相關(guān)，出門必備的電子地圖！</p><p>　　電子地圖，即數(shù)字地圖，是利用計(jì)算機(jī)技術(shù)，以數(shù)字方式存儲(chǔ)和查閱的地圖。電子地圖憑借可以進(jìn)行任意比例尺、任意范圍繪圖輸出，非常容易進(jìn)行修改，縮短成圖時(shí)間，與此

26、同時(shí)，更可以方便地與衛(wèi)星影像、航空照片等其他信息源結(jié)合，生成新的圖種，通過手機(jī)，電腦等信息渠道等優(yōu)勢(shì)而被人們接受。</p><p>　　在電子地圖的應(yīng)用方面，最主要的有兩個(gè)領(lǐng)域：其一是利用電子地圖的等高線和高程點(diǎn)可以生成數(shù)字高程模型，將地表起伏以數(shù)字模擬形式表現(xiàn)出來，直觀立體地表現(xiàn)地貌形態(tài)；其一是利用最短路徑算法，將兩地行進(jìn)路線完整，完美的表現(xiàn)出來。現(xiàn)實(shí)民用方面，無疑最短路領(lǐng)域更是電子地圖應(yīng)用的重中之重！<

27、/p><p>　　就目前而言，全球各大國(guó)對(duì)衛(wèi)星導(dǎo)航系統(tǒng)展開了激烈的競(jìng)爭(zhēng)，由于我國(guó)進(jìn)入該領(lǐng)域時(shí)間較晚，即便北斗的衛(wèi)星已經(jīng)成功發(fā)射了十六顆衛(wèi)星，但與美國(guó)全球定位系統(tǒng)，俄羅斯“格洛納斯”系統(tǒng)，歐洲“伽利略”系統(tǒng)在民用方面還有一定的不足，我們?nèi)粘Ｉ钪薪佑|到的電子地圖幾乎都是以為載體，我們自己的“電子地圖”迫切需要與最短路徑算法相結(jié)合。</p><p>　　電子地圖與最短路徑算法的結(jié)合已稱為必須，在生

28、活節(jié)奏快速的今天更是一種必然。這種結(jié)合的作用是顯然的，而這種結(jié)合的難度也是易見的，前期工作量極大。</p><p>　　電子地圖與最短路徑算法結(jié)合的前提是電子地圖的“繪制”：在研究最短路徑算法時(shí)，可以發(fā)現(xiàn)無論是對(duì)哪個(gè)算法，其得以實(shí)施，實(shí)現(xiàn)的前提都是圖。將現(xiàn)實(shí)的網(wǎng)絡(luò)抽象為一般有向圖或無向圖，然后根據(jù)點(diǎn)，邊等信息實(shí)現(xiàn)算法，而在“繪制”電子地圖時(shí)，最為關(guān)鍵的就是建立城市交通網(wǎng)絡(luò)數(shù)據(jù)模型。</p><

29、p>　　電子地圖與最短路徑算法結(jié)合的核心是最短路徑算法的實(shí)現(xiàn)：二者的結(jié)合，從某種角度上看，就是如何在電子地圖上實(shí)現(xiàn)最短路徑算法，如何在已知的抽象得出的有向圖或無向圖上，實(shí)現(xiàn)最短路徑算法，得到所求路徑，并保證準(zhǔn)確有效的到達(dá)，是電子地圖與最短路徑二者結(jié)合最突出，最核心的問題。</p><p><b>　　1 基本概念</b></p><p>　　1.1 圖論基本概念

30、</p><p>　　1.1.1 圖的基本概念</p><p>　　一集元素及其之間的某種關(guān)系稱之為圖。具體來說，圖通常就是一個(gè)二元組，其中集合為頂點(diǎn)集，集合是頂點(diǎn)集中元素組成的無序?qū)Φ募希Q為邊集。</p><p><b>　　例1 給定,其中</b></p><p>　　這便定義了一個(gè)無向圖,如下</p>

31、;<p><b>　　圖1.1 無向圖</b></p><p>　　無向圖：每條邊都是無向邊的圖。</p><p>　　有向圖：每條邊都是有向邊的圖。</p><p>　　混合圖：既有有向邊又有無向邊的圖。 </p><p>　　自回路：一條邊的兩端重合。</p><p>　　簡(jiǎn)單圖

32、：不含平行邊和自回路的圖。一條無向邊可以用一對(duì)方向相反的有向邊代替，因此一個(gè)無向圖可以用這種方法轉(zhuǎn)化為一個(gè)有向圖。</p><p>　　重?cái)?shù)：兩頂點(diǎn)間若有幾條邊，稱這些邊為平行邊，兩頂點(diǎn)間平行邊的條數(shù)成為的重?cái)?shù)。 </p><p>　　多重圖：含有平行邊的圖。</p><p>　　逆圖：把一個(gè)有向圖的每條邊都反向由此得到的圖稱為的逆圖。</p><

33、;p>　　賦權(quán)圖：每條邊都賦上了值。</p><p>　　出度：與頂點(diǎn)相連的邊數(shù)稱為該定點(diǎn)的度數(shù)，以該定點(diǎn)為始邊的邊數(shù)為出度。 入度：以該定點(diǎn)為終邊的邊數(shù)為入度。度數(shù)為零的定點(diǎn)稱為孤立點(diǎn)；度數(shù)為一的點(diǎn)為懸掛點(diǎn)。</p><p>　　無向完全圖：在階無向圖中如果任何兩點(diǎn)都有一條邊關(guān)連則稱此圖是無向完全圖。</p><p>　　完全有向圖：在階有向圖中如果任意兩點(diǎn)

34、都有方向相反的有向邊相連則稱此圖為完全有向圖。</p><p>　　競(jìng)賽圖：階圖中如果其底圖是無向完全圖，則稱此有向完全圖為競(jìng)賽圖。</p><p>　　圖1.2 賦權(quán)有向圖</p><p>　　1.1.2 鄰接矩陣</p><p>　　鄰接矩陣為儲(chǔ)存圖中“邊”信息的一種方法，為表示各個(gè)頂點(diǎn)之間關(guān)系的矩陣。設(shè)是一個(gè)具有個(gè)頂點(diǎn)的圖，則圖的鄰接矩

35、陣是一個(gè)的二維數(shù)組，用表示，定義為：</p><p>　　上述圖1.2中的鄰接矩陣為：</p><p><b>　　1.1.3 鄰接表</b></p><p>　　因?yàn)猷徑泳仃嚐o法存儲(chǔ)含有自身環(huán)或有重邊的圖，而且在圖的邊數(shù)較少時(shí)，使用鄰接矩陣會(huì)浪費(fèi)大量存儲(chǔ)空間，所以這時(shí)使用另一種存儲(chǔ)方式——鄰接表。</p><p>　　

36、鄰接表，就是把從同一個(gè)頂點(diǎn)出發(fā)的邊連接在同一個(gè)稱為邊鏈表的單鏈表中。邊鏈表的每一個(gè)結(jié)點(diǎn)代表著一條邊，稱為邊結(jié)點(diǎn)。對(duì)于有向圖，每個(gè)邊結(jié)點(diǎn)有三個(gè)域：該邊終點(diǎn)的序號(hào)，該邊的權(quán)值，以及指向下一個(gè)邊結(jié)點(diǎn)的指針。在鄰接表中，還有一個(gè)存儲(chǔ)頂點(diǎn)信息的頂點(diǎn)數(shù)組。</p><p><b>　　圖1.3 鄰接表</b></p><p>　　1.2 最短路的基本概念</p>&

37、lt;p>　　1.2.1 最短路問題</p><p>　　給出的是一有向加權(quán)圖，在其上定義的加權(quán)函數(shù)為從邊到實(shí)型權(quán)值的映射。路徑的權(quán)是指其組成邊的所有權(quán)值之和：</p><p>　　定義u到v間最短路徑的權(quán)為</p><p>　　從結(jié)點(diǎn)u到結(jié)點(diǎn)v的最短路徑定義為權(quán)的路徑。</p><p>　　1.2.2 單目標(biāo)最短路徑問題</p&

38、gt;<p>　　找出從每一結(jié)點(diǎn)v到某指定結(jié)點(diǎn)u的一條最短路徑。把圖中的每條邊反向，我們就可以把這一問題轉(zhuǎn)化為單源最短路徑問題。</p><p>　　1.2.3 單對(duì)結(jié)點(diǎn)間的最短路徑問題</p><p>　　對(duì)于某給定結(jié)點(diǎn)u和v，找出從u到v的一條最短路徑。如果我們解決了源結(jié)點(diǎn)為u的單源問題，則這一問題也就獲得了解決。對(duì)于該問題的最壞情況，從漸進(jìn)意義上看，目前還未發(fā)現(xiàn)比最好的

39、單源算法更快的方法。</p><p>　　1.3 電子地圖的基本概念</p><p>　　從狹義的角度，電子地圖是以數(shù)字地圖數(shù)據(jù)為數(shù)據(jù)基礎(chǔ)，以計(jì)算機(jī)系統(tǒng)為處理平臺(tái)，在屏幕上實(shí)時(shí)顯示的地圖；而廣義的來說，電子地圖是指屏幕地圖和支持其顯示的地圖軟件的總稱。</p><p>　　1.3.1 電子地圖的基本性質(zhì)</p><p>　　⑴電子地圖是一種模

40、擬地圖產(chǎn)品，仍具有地圖的三個(gè)基本特征：分色，比例尺，標(biāo)度；</p><p>　?、齐娮拥貓D中數(shù)據(jù)來源數(shù)字地圖；</p><p>　　⑶電子地圖采集及設(shè)計(jì)都是在計(jì)算機(jī)平臺(tái)環(huán)境下實(shí)現(xiàn)；</p><p>　?、入娮拥貓D表達(dá)載體為屏幕。</p><p>　　1.3.2 電子地圖的一般特點(diǎn)</p><p>　?、烹娮拥貓D數(shù)據(jù)的集

41、成性；</p><p>　　⑵使用電子地圖過程中的交互性：區(qū)別于紙質(zhì)地圖，可以讓用戶交互操作；</p><p>　　⑶信息表達(dá)的多樣性：地圖載負(fù)量極大擴(kuò)展；</p><p>　?、榷嗉?jí)縮放和多尺度數(shù)據(jù)：快速、高效的信息檢索與地圖分析；</p><p>　　⑸多維和動(dòng)態(tài)可視化：使地圖效果更加突出；</p><p>　?、?/p>

42、共享性及其低成本性：可存儲(chǔ)于地圖數(shù)據(jù)庫中，方便復(fù)制更新編輯，容易再版。</p><p>　　1.3.3 地理信息系統(tǒng)</p><p>　　地理信息系統(tǒng),又被稱作地學(xué)信息系統(tǒng)或資源與環(huán)境信息系統(tǒng)，是一種特定的空間信息系統(tǒng)。系統(tǒng)是在計(jì)算機(jī)硬、軟件系統(tǒng)支持下，對(duì)整體或局部地球表層空間——含蓋大氣層在內(nèi)——中相關(guān)地理分布數(shù)據(jù)進(jìn)行采集、儲(chǔ)存、管理、運(yùn)算、分析、顯示和描述的技術(shù)系統(tǒng)。</p>

43、;<p>　　在地理數(shù)據(jù)方面，中分為兩類：空間數(shù)據(jù)，與空間要素幾何特性有關(guān)；屬性數(shù)據(jù)，提供空間要素的信息。在應(yīng)用方面，技術(shù)能夠在科學(xué)調(diào)查、資源管理、財(cái)產(chǎn)管理、發(fā)展規(guī)劃、繪圖和路線規(guī)劃中發(fā)揮重要作用，如在自然災(zāi)害發(fā)生時(shí)計(jì)算出救援反應(yīng)時(shí)間，規(guī)律自然保護(hù)區(qū)等。 </p><p>　　2 最短路問題的各種算法</p><p>　　根據(jù)有向網(wǎng)或無向網(wǎng)中各邊權(quán)值情形及求解的需要，最短路徑

44、問題大致分為了以下四類，并分別用不同的算法求解：</p><p>　?、徘髥卧醋疃搪窂?，且邊的權(quán)值非負(fù)——算法。單源最短路徑指的是固定為一個(gè)頂點(diǎn)為源點(diǎn)，然后從源點(diǎn)出發(fā)到其他各個(gè)頂點(diǎn)的最短路徑；</p><p>　?、魄髥卧醋疃搪窂剑疫叺臋?quán)值可以為負(fù)，但不存在負(fù)權(quán)值的回路——算法；</p><p>　?、撬惴ǖ母倪M(jìn)——算法；</p><p>

45、　　⑷求所有頂點(diǎn)之間的最短路徑，且邊的權(quán)值可以為負(fù)，但不存在負(fù)權(quán)值回路——算法。</p><p><b>　　2.1 算法</b></p><p>　　該時(shí)效性較好，時(shí)間復(fù)雜度為,可以用優(yōu)先隊(duì)列進(jìn)行優(yōu)化，優(yōu)化后時(shí)間復(fù)雜度變?yōu)椤?lt;/p><p>　　2.1.1 算法的原理</p><p>　　從出發(fā)點(diǎn)出發(fā)，每次擴(kuò)展一個(gè)距離

46、最短的點(diǎn)，更新與其相鄰的點(diǎn)的距離。當(dāng)所有邊權(quán)都為正時(shí)，由于不會(huì)存在一個(gè)距離更短的沒擴(kuò)展過的點(diǎn)，所以這個(gè)點(diǎn)的距離永遠(yuǎn)不會(huì)再被改變，從而保證了算法的正確性。</p><p>　　圖2.1 算法的執(zhí)行流程</p><p>　　2.1.2 算法實(shí)現(xiàn)</p><p>　　該算法的實(shí)現(xiàn)中，需要設(shè)置三個(gè)數(shù)組，即距離數(shù)組，標(biāo)記數(shù)組，過渡數(shù)組，三個(gè)數(shù)組構(gòu)成了一個(gè)集合，對(duì)從源點(diǎn)到其他各

47、頂點(diǎn)（從）的最短路及其長(zhǎng)度而言渡數(shù)組中，表示從到的最短路徑上前一個(gè)頂點(diǎn)的序號(hào)，若，表示從到直達(dá)且該路徑最短；反之，采用“倒序追蹤”，得到從到最短路徑的行進(jìn)路線。初始時(shí)，若到之間有邊，則；若到之間無邊，則。</p><p>　　得到初始集合，算法實(shí)現(xiàn)的步驟為：</p><p>　?、旁谒鶎?duì)應(yīng)的中尋找最小值——及；</p><p>　　⑵將對(duì)應(yīng)的改為，表示從到已找到最短

48、路徑；</p><p>　　⑶在已經(jīng)找到最短路徑后，檢查所有標(biāo)記數(shù)組所對(duì)應(yīng)的頂點(diǎn)，若頂點(diǎn)與有直接相連的邊，且，說明從直接到的路徑，大于先從到，在從到的路徑，此時(shí)修改距離數(shù)組中，過渡數(shù)組中；反之則不需要改動(dòng)</p><p>　?、扔筛膭?dòng)的距離數(shù)組，標(biāo)記數(shù)組，過渡數(shù)組組成一個(gè)新的集合,重新進(jìn)行上述步驟，只要標(biāo)記數(shù)組中所有元素均為。</p><p><b>　　

49、2.2 算法</b></p><p>　　該算法適用于帶負(fù)權(quán)值的單源最短路徑問題，其限制條件為：圖中不能包含權(quán)值總和為負(fù)值的回路，即不存在負(fù)權(quán)值回路。</p><p>　　圖2.2 左負(fù)右正的回路全職總和</p><p>　　2.2.1 算法的原理</p><p>　　在個(gè)頂點(diǎn)且無負(fù)權(quán)值回路的有向圖中，如果從頂點(diǎn)到存在最短路徑，則

50、該路徑至多有條邊，即經(jīng)歷了所有個(gè)頂點(diǎn)。對(duì)計(jì)算從源點(diǎn)到其他頂點(diǎn)的最短路徑， 算法就是構(gòu)造出一個(gè)最短路徑長(zhǎng)度數(shù)組序列：，， 。</p><p>　　說明對(duì)計(jì)算從源點(diǎn)到頂點(diǎn)的最短路徑最多一共有條邊，其中取值范圍為到。算法最終就得到了，為到的最短路徑。</p><p><b>　　初始時(shí)：</b></p><p><b>　　遞推中：<

51、/b></p><p><b>　　其中：</b></p><p>　　2.2.2 算法實(shí)現(xiàn)</p><p>　　該算法的實(shí)現(xiàn)中，需要設(shè)置兩個(gè)數(shù)組，即距離數(shù)組，過渡數(shù)組，對(duì)從源點(diǎn)到其他各頂點(diǎn)（從）的最短路徑及其長(zhǎng)度而言：</p><p>　　距離數(shù)組用來儲(chǔ)存一系列的，其中；而過渡數(shù)組中，依然表示從到的最短路徑上前一

52、個(gè)頂點(diǎn)的序號(hào)。</p><p><b>　　算法實(shí)現(xiàn)的步驟為：</b></p><p>　　⑴初始時(shí)，，選擇一個(gè)計(jì)數(shù)變量，并令，而若到之間有邊，則；若到之間無邊，則；</p><p>　?、票容^大小，若小于，則。將改為兩者的最小值，且在原來值的基礎(chǔ)上加一，即；</p><p>　　⑶重復(fù)第二步，直到0000，此時(shí)代表著從

53、到（從）的最短路徑，根據(jù)值采用倒向追蹤得到各個(gè)最短路徑的行進(jìn)路線。</p><p>　　從算法實(shí)現(xiàn)的步驟可以看出，其時(shí)間復(fù)雜度為，而空間復(fù)雜度為。</p><p><b>　　2.3 算法</b></p><p>　　該算法是采用隊(duì)列方式算法進(jìn)行優(yōu)化，主要根據(jù)了“每個(gè)頂點(diǎn)的最短路徑不會(huì)更新次數(shù)太多”的特點(diǎn)。</p><p&g

54、t;　　算法時(shí)效性相對(duì)較好，采用一系列松弛操作以得到從某一個(gè)節(jié)點(diǎn)出發(fā)到達(dá)圖中其它所有節(jié)點(diǎn)的最短路徑。其可以在的時(shí)間復(fù)雜度內(nèi)求出源點(diǎn)到其他各個(gè)頂點(diǎn)的最短路徑，并且可以處理負(fù)權(quán)值邊。為每個(gè)頂點(diǎn)入隊(duì)列的平均次數(shù)，通常情況下。</p><p>　　2.3.1 算法的思想</p><p>　　若有向加權(quán)圖不存在負(fù)權(quán)回路，即最短路徑一定存在。用鄰接表來存儲(chǔ)圖。初始時(shí)將源點(diǎn)加入隊(duì)列，每次從隊(duì)列中取出一點(diǎn)

55、，并對(duì)所有與其相連的頂點(diǎn)進(jìn)行松弛操作（該算法實(shí)現(xiàn)步驟⑴）。若某個(gè)頂點(diǎn)松弛成功，則將該點(diǎn)入隊(duì)。重復(fù)這個(gè)過程，直到隊(duì)列為空。</p><p>　　即采取動(dòng)態(tài)逼近法：設(shè)立一個(gè)先進(jìn)先出隊(duì)列用來保存待優(yōu)化的結(jié)點(diǎn)，優(yōu)化時(shí)每次取出隊(duì)首結(jié)點(diǎn)，并且用點(diǎn)當(dāng)前的最短路徑估計(jì)值對(duì)離開點(diǎn)所指向的結(jié)點(diǎn)進(jìn)行松弛操作，如果點(diǎn)的最短路徑估計(jì)值有所調(diào)整，且點(diǎn)不在當(dāng)前的隊(duì)列中，就將點(diǎn)放入隊(duì)尾。以此方式，直至隊(duì)列空為止。</p><

56、p>　　2.3.2 算法的實(shí)現(xiàn) </p><p>　　與算法類似，該算法的實(shí)現(xiàn)中使用兩個(gè)數(shù)組，即距離數(shù)組，用來記錄源點(diǎn)到其他各頂點(diǎn)（從）最短路徑；過渡數(shù)組，對(duì)從源點(diǎn)到其他各頂點(diǎn)（從）最短路徑中前一個(gè)頂點(diǎn)的序號(hào)。</p><p>　　初始時(shí)，，其余元素均為；均為；并將源點(diǎn)放入隊(duì)列。算法實(shí)現(xiàn)的步驟為：</p><p>　?、湃〕鲫?duì)列的頭頂點(diǎn)，掃描從出發(fā)的每一條邊，

57、設(shè)邊的終點(diǎn)為，該邊的權(quán)值為。若，則修改為，同時(shí)修改為，此時(shí)若不在當(dāng)前隊(duì)列中，將放入隊(duì)列中；若，不變動(dòng)；</p><p>　?、浦貜?fù)執(zhí)行步驟⑴,直到隊(duì)列為空。</p><p><b>　　2.4 算法</b></p><p>　　該算法適用于求多源、無負(fù)權(quán)邊的最短路徑，其時(shí)間復(fù)雜度為，空間復(fù)雜度為。</p><p>　　2

58、.4.1 算法的思想</p><p>　　該算法的原理是動(dòng)態(tài)規(guī)劃：</p><p>　　設(shè)為從到中只以頂點(diǎn)集合中的某個(gè)頂點(diǎn)為中間節(jié)點(diǎn)的最短路徑的長(zhǎng)度。若最短路徑經(jīng)過點(diǎn)，則；若最短路徑不經(jīng)過點(diǎn)，則。</p><p><b>　　因此</b></p><p>　　由公式可知：在原有路徑的基礎(chǔ)上加入其它頂點(diǎn)為中間節(jié)點(diǎn)后，若距離

59、縮小，便以新路徑替代原有路徑。不斷更新后，即可得到最短路徑。在實(shí)際算法中，為節(jié)約空間，可以直接在原來空間上進(jìn)行迭代，從而空間可降至二維。</p><p>　　2.4.2 算法的實(shí)現(xiàn)</p><p>　　對(duì)擁有個(gè)頂點(diǎn)的有向圖而言，設(shè)置一個(gè)的方陣，其中除對(duì)角線的矩陣元素都等于外，其它元素表示從到的有向路徑長(zhǎng)度，表示中間節(jié)點(diǎn)范圍，取值范圍為：。</p><p>　　表示從

60、直接到的邊的長(zhǎng)度，即為鄰接矩陣；</p><p>　　表示從到，中間節(jié)點(diǎn)的序號(hào)不大于的最短路徑長(zhǎng)度；</p><p><b>　　其遞推公式為：</b></p><p><b>　　其中</b></p><p>　　在算法實(shí)現(xiàn)中，需要使用到兩個(gè)數(shù)組：距離數(shù)組,用來存放一系列的，其中，其規(guī)律為公式，算

61、法結(jié)束時(shí)，為從到的最短路徑；過渡數(shù)組，用來表示從到的最短路徑上前一個(gè)頂點(diǎn)的序號(hào)。</p><p><b>　　算法實(shí)現(xiàn)的步驟為：</b></p><p>　?、疟容^與的大小。若，則修改為，同時(shí)修改為；否則，則不變換；</p><p>　　⑵，重復(fù)步驟⑴，直到時(shí)，結(jié)束算法，此時(shí)為從到的最短路徑。</p><p>　　2.5

62、 其他算法——算法</p><p>　　該算法是一種靜態(tài)路網(wǎng)中求解最短路最有效的方法。</p><p><b>　　公式表示為：</b></p><p>　　公式中：是第節(jié)點(diǎn)從初始點(diǎn)到目標(biāo)點(diǎn)的估價(jià)函數(shù)，是在狀態(tài)空間中從初始節(jié)點(diǎn)到第節(jié)點(diǎn)的實(shí)際代價(jià)，是從第節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)最佳路徑的估計(jì)代價(jià)。</p><p>　　保證找到最短路

63、徑條件，關(guān)鍵在于估價(jià)函數(shù)的選?。?lt;/p><p>　　若估價(jià)值到目標(biāo)節(jié)點(diǎn)的距離實(shí)際值，搜索的點(diǎn)數(shù)多，搜索范圍大，效率低，但能保證得到最優(yōu)解。若估價(jià)值到目標(biāo)節(jié)點(diǎn)的距離實(shí)際值,搜索的點(diǎn)數(shù)少，搜索范圍小，效率高，但不能保證得到最優(yōu)解。估價(jià)值與實(shí)際值越接近，估價(jià)函數(shù)取得就越好。 </p><p>　　圖2.3 算法的靜態(tài)路網(wǎng)</p><p>　　3 城市交通網(wǎng)絡(luò)數(shù)據(jù)模型&

64、lt;/p><p>　　將最短路徑算法應(yīng)用于電子地圖之前，需要完成地圖的數(shù)據(jù)化，將現(xiàn)實(shí)中的交通網(wǎng)絡(luò)抽象轉(zhuǎn)化為有向圖。</p><p>　　首先, 基于制定一個(gè)面向城市交通需求預(yù)測(cè)的交通網(wǎng)絡(luò)數(shù)據(jù)模型框架；其次，在此框架內(nèi)對(duì)模型的具體內(nèi)容包括網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)、數(shù)據(jù)庫表的結(jié)構(gòu)的表示方法等作進(jìn)一步的探討，并給出一個(gè)模型實(shí)例；再次，針對(duì)交通規(guī)劃中路網(wǎng)方案動(dòng)態(tài)調(diào)整的具體特點(diǎn)，對(duì)該模型實(shí)例進(jìn)行拓展；最后，得到適

65、合動(dòng)態(tài)路網(wǎng)的數(shù)據(jù)模型。</p><p>　　數(shù)據(jù)是描述事物的符號(hào)記錄，模型是現(xiàn)實(shí)世界的抽象，而數(shù)據(jù)模型代表著一種實(shí)體和實(shí)體之間的關(guān)系，這些實(shí)體和關(guān)系被用于創(chuàng)建真實(shí)事物或現(xiàn)象的表示形式。網(wǎng)絡(luò)數(shù)據(jù)模型是現(xiàn)實(shí)世界中的網(wǎng)絡(luò)系統(tǒng)——排水系統(tǒng)，交通系統(tǒng)等——的抽象表示.構(gòu)成網(wǎng)絡(luò)系統(tǒng)的最基本元素是各個(gè)實(shí)體以及這些實(shí)體之間連接交匯點(diǎn)，前者通常被稱為網(wǎng)線或路段，后者一般稱為節(jié)點(diǎn)。在該網(wǎng)絡(luò)模型中主要實(shí)體包括：形狀點(diǎn)、線段、弧段、節(jié)點(diǎn)

66、、弧段序列、道路名稱、通行條件、交通指示牌等。</p><p>　　3.1 電子地圖數(shù)據(jù)需滿足的技術(shù)要求 </p><p>　?、烹娮拥貓D必須具有較高精確性，包括地理位置數(shù)據(jù)的精確性和實(shí)際地物信息的準(zhǔn)確性；</p><p>　　⑵電子地圖必須提供完備的地物屬性信息：一方面是電子地圖進(jìn)行查詢檢索的需要，另一方面也是進(jìn)行實(shí)際智能交通分析及相關(guān)導(dǎo)航應(yīng)用的客觀需要；<

67、/p><p>　　⑶電子地圖對(duì)硬件設(shè)備有一定要求：電子地圖，如車載系統(tǒng)、手持式設(shè)備等環(huán)境下，硬件條件相對(duì)特殊，對(duì)導(dǎo)航電子地圖的要求也相應(yīng)地更加苛刻；</p><p>　?、入娮拥貓D數(shù)據(jù)必須滿足全網(wǎng)道路數(shù)據(jù)的連通性。</p><p>　　3.2 電子地圖基礎(chǔ)數(shù)據(jù)的整理</p><p>　　3.2.1 道路，建筑物的錄入</p><

68、;p>　　在電子地圖中，最基礎(chǔ)的是交通道路的位置、走向，長(zhǎng)度，以及建筑物的所在區(qū)域，要把這些信息已電子地圖形式展現(xiàn)，首先需將其錄入進(jìn)系統(tǒng)，構(gòu)成地形圖；</p><p>　　3.2.2 坐標(biāo)系的轉(zhuǎn)換</p><p>　　因?yàn)樵谑占?、錄入的時(shí)候，工程量較大，故人員較多，而可能采用的不同的坐標(biāo)模式，這樣的話可能會(huì)在同一副地圖中出現(xiàn)兩種坐標(biāo)系的情況，這樣就好導(dǎo)致很大的誤差，故需要轉(zhuǎn)化為同一的

69、坐標(biāo)系標(biāo)準(zhǔn)，將采集，收集到的地形圖以指定的單位劃入指定的區(qū)域；</p><p>　　3.2.3 地形圖的分層、縮編</p><p>　　將已經(jīng)得到的圖形按照分層標(biāo)準(zhǔn)對(duì)其進(jìn)行分層，選定標(biāo)準(zhǔn)的比例尺，如，因不同團(tuán)隊(duì)，不同地形的收集到的信息量差異，反應(yīng)在地圖上的信息狀況也大不相同，可能局部詳細(xì)，局部粗糙，而經(jīng)過處理后，圖形中字體大小和線形比例以及塊符號(hào)的縮放比例可以完成統(tǒng)一修改，但是塊符號(hào)的密度

70、，經(jīng)過處理，可能會(huì)使一些信息量會(huì)產(chǎn)生疊加的情況，此時(shí)只能通過人工判斷來對(duì)圖面進(jìn)行整飾修改，補(bǔ)刪一定信息量；</p><p>　　3.2.4 地形圖的接邊與圖幅分幅</p><p>　　地形圖在做分層縮編時(shí)是以塊為單位進(jìn)行分層整理的，整理過的圖要進(jìn)行接邊處理?？紤]到實(shí)際情況，交接處會(huì)產(chǎn)生地物不一制，或者是接邊不到位和圖形重疊的情況，故在接邊過程中陣對(duì)圖面做整飾處理，不對(duì)圖形和屬性進(jìn)行一致性接

71、邊，盡量保持塊區(qū)域信息量的完整。</p><p>　　3.3 城市交通網(wǎng)絡(luò)數(shù)據(jù)模型的管理</p><p>　　3.3.1 格網(wǎng)管理</p><p>　　電子地圖的使用過程中，使用一定區(qū)域范圍的道路數(shù)據(jù)和背景數(shù)據(jù)的情況非常普遍，因此對(duì)城市交通網(wǎng)絡(luò)數(shù)據(jù)模型（下簡(jiǎn)稱數(shù)據(jù)模型）的管理，可以把整個(gè)地圖區(qū)域以格網(wǎng)為單位進(jìn)行分區(qū)管理。</p><p>　　

72、格網(wǎng)管理方式為采用層-塊-格網(wǎng)的三級(jí)線性樹狀邏輯結(jié)構(gòu)。這種樹結(jié)構(gòu)的線性分層分區(qū)管理方式，能夠大大加快數(shù)據(jù)信息的檢索速度。</p><p>　　格網(wǎng)的劃分一般有兩種情況：一種以一定角度的經(jīng)度線和緯度線作為邊界；另一種以基準(zhǔn)點(diǎn)的東西軸和南北軸的平行線為邊界線。后者適合于格網(wǎng)為區(qū)域較小的數(shù)據(jù)管理，前者適合于區(qū)域較大的數(shù)據(jù)管理。</p><p>　　3.3.2 道路網(wǎng)絡(luò)數(shù)據(jù)區(qū)域管理</p&g

73、t;<p>　　為了加快路徑規(guī)劃速度，數(shù)據(jù)模型管理，可以采用創(chuàng)建道路網(wǎng)絡(luò)數(shù)據(jù)的管理方式。道路網(wǎng)絡(luò)數(shù)據(jù)是在路徑規(guī)劃的過程中為了使用盡可能大范圍的數(shù)據(jù)，以由任意的多邊形定義的區(qū)域?yàn)閱挝粊泶娣?，存在區(qū)域根據(jù)其外接長(zhǎng)方形進(jìn)行管理。</p><p>　　這部分?jǐn)?shù)據(jù)為了處理大范圍的概略網(wǎng)絡(luò)數(shù)據(jù)而進(jìn)行了分層管理。在同一數(shù)據(jù)層上，區(qū)域之間不允許有重疊，并且上層數(shù)據(jù)區(qū)域必須與下層數(shù)據(jù)區(qū)域相同或者由其合并而成。道路網(wǎng)絡(luò)

74、數(shù)據(jù)采用這種線性樹狀結(jié)構(gòu)，可以提高路徑規(guī)劃時(shí)數(shù)據(jù)訪問的效率，加快路徑規(guī)劃的速度。</p><p>　　3.3.3索引數(shù)據(jù)的管理</p><p>　　數(shù)據(jù)模型中基礎(chǔ)數(shù)據(jù)的地點(diǎn)數(shù)據(jù)的檢索，可以通過多種多樣的操作順序來實(shí)現(xiàn)。這些操作順序的檢索，如電話號(hào)碼檢索、郵政編碼檢索、設(shè)施檢索等，雖然這些檢索方式之間存在差異，但對(duì)數(shù)據(jù)模型中地點(diǎn)數(shù)據(jù)都能實(shí)現(xiàn)共用。</p><p>　　

75、作為檢索結(jié)果所需要的地點(diǎn)信息，根據(jù)用途或?qū)傩缘牟煌赡苄枰鞣N不同數(shù)據(jù)信息。這些信息如果用一個(gè)地點(diǎn)信息來表示則會(huì)顯得冗長(zhǎng)，所以有必要準(zhǔn)備由多個(gè)適當(dāng)?shù)臄?shù)據(jù)信息構(gòu)成一個(gè)地點(diǎn)信息來共用。在數(shù)據(jù)模型的管理中，可由實(shí)現(xiàn)特定檢索方式的檢索關(guān)鍵字?jǐn)?shù)據(jù)，作為檢索結(jié)果的共有的基礎(chǔ)索引數(shù)據(jù)，并將其組合為目錄的形式劃分區(qū)域進(jìn)行管理。</p><p>　　4 電子地圖與最短路徑算法的結(jié)合</p><p>　　在把

76、交通網(wǎng)絡(luò)抽象為有向圖后，以此為基礎(chǔ)對(duì)交通分配進(jìn)行建模并求解，但是，交通網(wǎng)絡(luò)的有向圖只是對(duì)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的描述。這僅僅是網(wǎng)絡(luò)數(shù)據(jù)模型中的一部分，即便如此，由于交通網(wǎng)絡(luò)是帶轉(zhuǎn)向的網(wǎng)絡(luò)，普通的有向圖也無法對(duì)其進(jìn)行完全的描述，尚有待補(bǔ)充研究；而實(shí)際的交通網(wǎng)絡(luò)還包含大量的空間數(shù)據(jù)和屬性數(shù)據(jù)，這些數(shù)據(jù)如何組織、存儲(chǔ)，如何與網(wǎng)絡(luò)拓?fù)溆袡C(jī)的聯(lián)系起來，更值得考慮。</p><p>　　假設(shè)有一張地圖，其中邊上的權(quán)值表示兩點(diǎn)之間的距離

77、。那么該如何找到起始地點(diǎn)到其他各個(gè)地點(diǎn)的最短路徑？這些都需要借助最短路徑算法！在已經(jīng)得到的道路數(shù)據(jù)模型的基礎(chǔ)上，按照各種最短路徑算法的要求，從相連的地點(diǎn)出發(fā)，找到滿足要求的路線，即最短路徑！</p><p>　　圖4.1 上海電力學(xué)院兩個(gè)校區(qū)之間的電子地圖</p><p>　　近年來，電子地圖與最短路徑算法結(jié)合的問題得到了人們的廣泛關(guān)注，這在歷屆數(shù)學(xué)建模比賽中得到了很好表示，下文以“201

78、1高教社杯全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽題目”中題——交巡警服務(wù)平臺(tái)的設(shè)置與調(diào)度——的第一小問為例，探討電子地圖與最短路徑算法的結(jié)合。</p><p><b>　　4.1 競(jìng)賽原題 </b></p><p>　　“有困難找警察”，是家喻戶曉的一句流行語。警察肩負(fù)著刑事執(zhí)法、治安管理、交通管理、服務(wù)群眾四大職能。為了更有效地貫徹實(shí)施這些職能，需要在市區(qū)的一些交通要道和重要部位設(shè)

79、置交巡警服務(wù)平臺(tái)。每個(gè)交巡警服務(wù)平臺(tái)的職能和警力配備基本相同。由于警務(wù)資源是有限的，如何根據(jù)城市的實(shí)際情況與需求合理地設(shè)置交巡警服務(wù)平臺(tái)、分配各平臺(tái)的管轄范圍、調(diào)度警務(wù)資源是警務(wù)部門面臨的一個(gè)實(shí)際課題。</p><p>　　試就某市設(shè)置交巡警服務(wù)平臺(tái)的相關(guān)情況，建立數(shù)學(xué)模型分析研究下面的問題：</p><p>　　（1）附件1（A區(qū)和全市六區(qū)交通網(wǎng)絡(luò)與平臺(tái)設(shè)置的示意圖）給出了該市中心城區(qū)A

80、的交通網(wǎng)絡(luò)和現(xiàn)有的20個(gè)交巡警服務(wù)平臺(tái)的設(shè)置情況示意圖，相關(guān)的數(shù)據(jù)信息見附件2（全市六區(qū)交通網(wǎng)絡(luò)與平臺(tái)設(shè)置的相關(guān)數(shù)據(jù)表）。請(qǐng)為各交巡警服務(wù)平臺(tái)分配管轄范圍，使其在所管轄的范圍內(nèi)出現(xiàn)突發(fā)事件時(shí)，盡量能在3分鐘內(nèi)有交巡警（警車的時(shí)速為）到達(dá)事發(fā)地。</p><p>　　對(duì)于重大突發(fā)事件，需要調(diào)度全區(qū)20個(gè)交巡警服務(wù)平臺(tái)的警力資源，對(duì)進(jìn)出該區(qū)的13條交通要道實(shí)現(xiàn)快速全封鎖。實(shí)際中一個(gè)平臺(tái)的警力最多封鎖一個(gè)路口，請(qǐng)給出該

81、區(qū)交巡警服務(wù)平臺(tái)警力合理的調(diào)度方案。</p><p>　　根據(jù)現(xiàn)有交巡警服務(wù)平臺(tái)的工作量不均衡和有些地方出警時(shí)間過長(zhǎng)的實(shí)際情況，擬在該區(qū)內(nèi)再增加2至5個(gè)平臺(tái)，請(qǐng)確定需要增加平臺(tái)的具體個(gè)數(shù)和位置。</p><p><b>　　4.2 問題分析 </b></p><p>　　本文以實(shí)現(xiàn)警察的刑事執(zhí)法、治安管理、交通管理、服務(wù)群眾四大職能為宗旨，利用

82、有限的警務(wù)資源，根據(jù)城市的實(shí)際情況與需求合理地設(shè)置了交巡警服務(wù)平臺(tái)、分配各平臺(tái)的管轄范圍及調(diào)度警務(wù)資源。</p><p>　?、鸥鶕?jù)題目所給數(shù)據(jù)，確定各節(jié)點(diǎn)之間的相鄰關(guān)系和距離，利用算法及編程求出兩點(diǎn)之間的最短距離，使其盡量滿足能在3分鐘內(nèi)有交巡警平臺(tái)警力到達(dá)案發(fā)結(jié)點(diǎn)的原則，節(jié)點(diǎn)去選擇平臺(tái)，把節(jié)點(diǎn)分配給離節(jié)點(diǎn)距離最近的平臺(tái)管轄，據(jù)此，我們得到了平臺(tái)的管轄區(qū)域劃分。</p><p>　?、莆?/p>

83、們對(duì)進(jìn)出該區(qū)的13條交通要道實(shí)現(xiàn)快速全封鎖的問題，我們認(rèn)定在所有調(diào)度方案中，某種方案中耗時(shí)最長(zhǎng)的的圍堵時(shí)間最短即最佳方案，利用0-1變量確定平臺(tái)的去向，并利用線性規(guī)劃知識(shí)來求解指派問題，求得了最優(yōu)的調(diào)度方案。</p><p>　?、窃诖_定增添平臺(tái)的個(gè)數(shù)和具體位置的問題中，我們將盡量保證每個(gè)節(jié)點(diǎn)都有一個(gè)平臺(tái)可以在三分鐘內(nèi)到達(dá)作為主要原則來求解。我們先找出到達(dá)每個(gè)平臺(tái)的時(shí)間都超過三分鐘的節(jié)點(diǎn)，并嘗試在這些節(jié)點(diǎn)中選取若

84、干個(gè)作為新的平臺(tái)，求出合理的添加方案。</p><p>　　4.3建立道路的網(wǎng)絡(luò)數(shù)據(jù)模型</p><p>　　圖4.2 A區(qū)交通圖 其程序?yàn)椋?lt;/p><p>　　圖4.3 全市交通圖 其程序?yàn)椋?lt;/p><p>　　4.4 管械范圍求解</p><p>　　此問要求我們利用數(shù)據(jù)及附圖，將各路口節(jié)點(diǎn)劃分給最適合的服務(wù)

85、平臺(tái)，并要求各服務(wù)臺(tái)管轄的范圍內(nèi)有突發(fā)事件發(fā)生時(shí)，盡量能在3分鐘內(nèi)有交巡警到達(dá)事發(fā)地（此時(shí)交巡警的行駛距離為3km），換算到比例圖上，也就是30mm。本題，不考慮其他因素，只注重唯一因素——距離。所以，我們第一步用算法求出各個(gè)節(jié)點(diǎn)之間的最短距離。</p><p>　?、鸥鶕?jù)題中所給的各個(gè)節(jié)點(diǎn)的坐標(biāo)，用計(jì)算出任意兩點(diǎn)之間的距離，得到的鄰接距離矩陣：</p><p>　　其中分兩種情況：當(dāng)?shù)趥€(gè)

86、節(jié)點(diǎn)與第個(gè)節(jié)點(diǎn)相鄰時(shí)，為兩個(gè)節(jié)點(diǎn)的相鄰距離。不相鄰時(shí)，為一個(gè)充分大的數(shù)。</p><p>　?、七\(yùn)用算法，求出任意92個(gè)節(jié)點(diǎn)到任意92個(gè)節(jié)點(diǎn)的最短距離，得到最短距離矩陣，根據(jù)問題需要，我們截取所得矩陣前20行，即任意20個(gè)服務(wù)平臺(tái)間到任意72個(gè)節(jié)點(diǎn)（沒有建立平臺(tái)的節(jié)點(diǎn)）的最短距離矩陣：</p><p>　　因?yàn)榉?wù)平臺(tái)的編號(hào)為1到20，所以取的前二十行，后七十二列為觀察對(duì)象。在觀察對(duì)象中，

87、取出每列的最小值，計(jì)入到原本為設(shè)為全0的的矩陣A的相應(yīng)的位置。</p><p>　　對(duì)于每一列而言，每列的最小值是最有可能小于3分鐘的，如果最小值都不滿足這個(gè)條件，那么對(duì)于這列對(duì)應(yīng)的節(jié)點(diǎn)而言，就不存在三分鐘可以到達(dá)的平臺(tái),所用程序?yàn)椋?</p><p>　　⑶由此，最后每個(gè)節(jié)點(diǎn)都會(huì)歸屬于某個(gè)服務(wù)平臺(tái)，用編程得出結(jié)果并繪制了管轄區(qū)域圖如表4.1.</p><p>　　

88、表4.1 服務(wù)平臺(tái)管轄范圍</p><p>　　4.5 調(diào)度方案的求解 </p><p>　　本題可以使用運(yùn)籌學(xué)中的指派方法來解決：如果發(fā)生重大突發(fā)事件，需要調(diào)度全區(qū)20個(gè)交巡警服務(wù)平臺(tái)的警力資源，對(duì)進(jìn)出該區(qū)的13條交通要道實(shí)現(xiàn)快速全面封鎖。在全面封鎖時(shí)，既需要使用最短的時(shí)間，還必須保證一個(gè)平臺(tái)的警力只能封鎖一個(gè)路口，這樣就必然會(huì)多出7個(gè)平臺(tái)。</p><p>　　

89、先根據(jù)給出的數(shù)據(jù)，設(shè)立出指派問題的條件矩陣。為，其中前十三列是A區(qū)13個(gè)出口到二十個(gè)平臺(tái)的最短路距離，剩余的七列用零補(bǔ)齊。得到之后，使用算法，就得到我們需要的調(diào)度方案，其程序?yàn)椋骸?lt;/p><p>　　根據(jù)前一問的解答我們可以得出任意服務(wù)平臺(tái)到任意出口的最短距離，引入變量：</p><p>　　據(jù)此我們建立關(guān)于服務(wù)平臺(tái)調(diào)度的目標(biāo)函數(shù)Z：</p><p><b&

90、gt;　　約束條件：</b></p><p>　　第一個(gè)約束表示要求每個(gè)服務(wù)臺(tái)只能去1個(gè)或0個(gè)出口。</p><p>　　第二個(gè)約束表示每個(gè)出入路口有且僅有一個(gè)服務(wù)平臺(tái)的警力支持。</p><p>　　綜上，我們利用編程得出了最優(yōu)調(diào)度方案，結(jié)果見表4.2：</p><p>　　表4.2 出口平臺(tái)調(diào)度方案</p>&l

91、t;p>　　通過分析這些線路，我們知道線路最長(zhǎng)的組合為8號(hào)平臺(tái)到達(dá)29號(hào)節(jié)點(diǎn)，它所花的時(shí)間即為封鎖路口的最終時(shí)間，且這個(gè)時(shí)間約為10分鐘。</p><p>　　4.6 平臺(tái)增加個(gè)數(shù)及位置的求解 </p><p>　　本問要求在第1小問的前提下，根據(jù)服務(wù)平臺(tái)的工作量不均衡及出警時(shí)間的不合理來增加服務(wù)平臺(tái)的具體個(gè)數(shù)及位置，使整個(gè)交巡警服務(wù)平臺(tái)系統(tǒng)趨于合理化。</p><

92、;p>　　在第一小問中，我們選擇每一列的最小值，把該節(jié)點(diǎn)劃分給離他最近的平臺(tái)管轄。但這樣的話，一方面會(huì)導(dǎo)致一部分的平臺(tái)管轄的節(jié)點(diǎn)過多，其轄區(qū)內(nèi)部的總案發(fā)率過高，而現(xiàn)實(shí)中，各平臺(tái)轄區(qū)案發(fā)率應(yīng)該相差不大。另一方面，少量節(jié)點(diǎn)到每個(gè)平臺(tái)的最短距離都大于，即到任何平臺(tái)的時(shí)間都超過，所以，我們就需要增設(shè)一些平臺(tái)。對(duì)于平臺(tái)添加的原則是添加平臺(tái)后使得所有節(jié)點(diǎn)都有平臺(tái)可以在三分鐘內(nèi)到達(dá)。</p><p>　　首先，我們以距離

93、出發(fā)，選擇前二十行中，其最小值大于30的列，把這些節(jié)點(diǎn)之間的距離從中提取出去，組成一個(gè)方陣。在這個(gè)方陣中，選擇兩節(jié)點(diǎn)之間距離小于，小于30說明此兩點(diǎn)可以在內(nèi)到達(dá)彼此。故可以任意刪去一列，刪去先出現(xiàn)的列。</p><p>　　現(xiàn)在得到需要添加的最多平臺(tái)數(shù)就是上面剩下的那些列對(duì)應(yīng)的節(jié)點(diǎn)。提取這些節(jié)點(diǎn)D中所在行，加上之前的20行，組成一個(gè)新的最短距離矩陣。其中,均為的矩陣，是全0陣，是中的一部分，進(jìn)行五次迭代，出現(xiàn)我們

94、需要的平臺(tái)及對(duì)應(yīng)的轄區(qū)。</p><p><b>　　迭代的規(guī)則是：</b></p><p>　?、旁谥羞x取每列的最小值，賦給中相應(yīng)的行列位置。</p><p>　　⑵找到中不為0的位置對(duì)應(yīng)的案發(fā)率，把每個(gè)位置的距離數(shù)字乘以各自的案發(fā)率，并除去速度10，平臺(tái)自身案發(fā)率乘以0.5加上。所得數(shù)字為每一個(gè)平臺(tái)的判斷數(shù)。</p><

95、p>　　⑶逐行判斷，如果某行的判斷上數(shù)大于所有節(jié)點(diǎn)案發(fā)率平均數(shù)乘以2的話，就把該行中的最大數(shù)字在中置為0。</p><p>　?、戎貜?fù)上述三步，五次。</p><p>　　圖4.4 迭代前綜合指標(biāo)曲線分布與直方圖</p><p>　　表4.3 調(diào)整后服務(wù)平臺(tái)管轄范圍</p><p><b>　　結(jié) 論</b>

96、</p><p>　　進(jìn)入二十一世紀(jì)后，信息化，數(shù)字化，虛擬化逐漸成為科技的主流方向，傳統(tǒng)意義上的地圖已經(jīng)不能滿足人們?nèi)缃竦男枨?，也不能適應(yīng)當(dāng)今的快節(jié)奏。電子地圖以其不斷升級(jí)中的功能越來越受到人們的重視，關(guān)注以及應(yīng)用。</p><p>　　而電子地圖中最重要的功能——根據(jù)客戶需求，制訂最佳路線——的實(shí)現(xiàn)，依賴于道路的數(shù)字模擬和最短路徑算法。在現(xiàn)今的導(dǎo)航領(lǐng)域和電子地圖市場(chǎng)里，我國(guó)有著很大的發(fā)

97、展空間，北斗導(dǎo)航系統(tǒng)的運(yùn)行，更為這些搭建了良好平臺(tái)，提供了競(jìng)爭(zhēng)的可能，我國(guó)擁有足夠的基礎(chǔ)，能力以及需求去發(fā)展電子地圖交通網(wǎng)絡(luò)，而這也是本文的研究背景。</p><p>　　在本文中，首先介紹了最短路徑算法和電子地圖的基本信息，通過了解這些信息后，對(duì)電子地圖與最短路徑的結(jié)合有初步的概念，知道研究的主要方向；其次就是對(duì)目前主流的五種最短路徑算法學(xué)習(xí)，對(duì)比，實(shí)現(xiàn)，了解這些算法的原理和實(shí)現(xiàn)步驟；最后以“2011高教社杯全

98、國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽題目”中題為例，具體問題，具體分析，具體解決：</p><p>　　電子地圖與最短路徑算法結(jié)合的前提是電子地圖的繪制，在所舉事例中，已知了各頂點(diǎn)的坐標(biāo)以及頂點(diǎn)間道路連接情況的信息，而這在現(xiàn)實(shí)應(yīng)用上，可以通過信息采集得到。擁有信息后，通過軟件，對(duì)道路建立了數(shù)據(jù)模型，也就是電子地圖的繪制，在這個(gè)過程中，需要繁瑣但又嚴(yán)謹(jǐn)?shù)墓ぷ鳎?lt;/p><p>　　而電子地圖與最短路徑算法結(jié)

99、合的核心是最短路徑算法的實(shí)現(xiàn)，在所舉事例中，題目要求是封鎖路口，也就是需要整體警力在一定時(shí)間內(nèi)到達(dá)指定位置。通過算法編程，實(shí)現(xiàn)了介紹的五大算法中的算法，從而得出了多平臺(tái)到達(dá)多位置的選擇。</p><p>　　通過軟件的調(diào)試，給出了合理的解決方案，從而得出如何進(jìn)行電子地圖與最短路徑的結(jié)合。</p><p><b>　　參考文獻(xiàn)</b></p><p&

100、gt;　　[1] 高隨祥.圖論與網(wǎng)絡(luò)流理論[M].北京:高等教育出版社,2009:1-16.</p><p>　　[2] 陳磊.電子地圖與最短路徑算法的結(jié)合[J].赤峰學(xué)院學(xué)報(bào),2009,25(5):26-27.</p><p>　　[3] 商細(xì)云.城市電子地圖設(shè)計(jì)研究[J].太原重型機(jī)械學(xué)院學(xué)報(bào),2004,25(1):49-53.</p><p>　　[4] 趙明

101、君. 建立動(dòng)態(tài)導(dǎo)航中的電子地圖數(shù)據(jù)結(jié)構(gòu)模型[J].數(shù)字通信世界,2007,7(9):3-9.</p><p>　　[5] 王桂平,王衍.圖論算法理論、實(shí)現(xiàn)及應(yīng)用[M].北京:北京大學(xué)出版社,2011.131-244.</p><p>　　[6] 郭耀煌,李軍.滿載問題的車輛路線安排[J].系統(tǒng)工程學(xué)報(bào),1995,17(2):17-18. </p><p>　　[7]

102、 嚴(yán)寒冰,劉迎春.基于GIS的城市道路網(wǎng)最短路徑算法探討[J].計(jì)算機(jī)學(xué)報(bào),2004,23(2):17-23.</p><p>　　[8] 胡運(yùn)權(quán),郭耀煌,錢頌迪等.運(yùn)籌學(xué)[M].北京:清華大學(xué)出版社,2005.251-285.</p><p>　　[9] 姜啟元.數(shù)學(xué)模型第四版[M].北京:高等教育出版社,2011.73-88.</p><p>　　[10] 郭耀

103、煌.運(yùn)籌學(xué)原理與方法[M].成都:西南交通大學(xué)出版社,1994.112-177.</p><p>　　[11] Triggs B,McLauchlan P,Hartley R,et al.Bundle adjustment-A modern synthesis[J].Vision Algorithms:Theory and Practice,2000,13(5):47-71.</p><p&g

104、t;　　[12] YU Dong-kai,LIU Yu-shu.Study on a routing algorithm based on Ichnography[J]. Journal o f Beijing Institute of Technology,2001,21(1):31-34.</p><p><b>　　附 錄</b></p><p><b

105、>　　程序：lp1003</b></p><p>　　for k=1:1:928</p><p>　　n1=daolu(k,1);</p><p>　　n2=daolu(k,2);</p><p><b>　　if n1<=92</b></p><p><b>　

106、　if n2<=92</b></p><p>　　a=jiedian(n1,2);</p><p>　　b=jiedian(n1,3);</p><p>　　c=jiedian(n2,2);</p><p>　　d=jiedian(n2,3);</p><p>　　plot([a c],[b d]);

107、</p><p><b>　　hold on</b></p><p><b>　　end</b></p><p><b>　　end</b></p><p><b>　　end</b></p><p>　　x1=jiedian(1:

108、20,2);</p><p>　　y1=jiedian(1:20,3);</p><p>　　plot(x1,y1,'ro');</p><p><b>　　hold on</b></p><p>　　for n=1:1:92</p><p>　　x=jiedian(n,2); y

109、=jiedian(n,3);</p><p>　　plot(x,y,'.');</p><p><b>　　hold on</b></p><p><b>　　end</b></p><p>　　for m=1:1:13</p><p>　　t=churu(m

110、,2);a=jiedian(t,2);</p><p>　　b=jiedian(t,3);plot(a,b,'r*');</p><p><b>　　hold on</b></p><p><b>　　end</b></p><p><b>　　程序：shitu</b

111、></p><p>　　for k=1:928</p><p>　　n1=daolu2(k,1);</p><p>　　n2=daolu2(k,2);</p><p>　　if n1<=92 & n2<=92</p><p>　　a=jiedian2(n1,2);</p><

112、;p>　　b=jiedian2(n1,3);</p><p>　　c=jiedian2(n2,2);</p><p>　　d=jiedian2(n2,3);</p><p>　　plot([a c],[b d],'g','linewidth',2);</p><p><b>　　hold on&

113、lt;/b></p><p><b>　　else</b></p><p>　　if n1<=165 & n2<=165 & n1>92 & n2>92</p><p>　　a=jiedian2(n1,2);</p><p>　　b=jiedian2(n1,3);&l

114、t;/p><p>　　c=jiedian2(n2,2);</p><p>　　d=jiedian2(n2,3);</p><p>　　plot([a c],[b d],'y','linewidth',2);</p><p><b>　　hold on</b></p><p&

115、gt;<b>　　else</b></p><p>　　if n1<=319 & n2<=319 & n1>166 & n2>166</p><p>　　a=jiedian2(n1,2);</p><p>　　b=jiedian2(n1,3);</p><p>　　c=ji

116、edian2(n2,2);</p><p>　　d=jiedian2(n2,3);</p><p>　　plot([a c],[b d],'linewidth',2);</p><p><b>　　hold on</b></p><p><b>　　else</b></p>

117、;<p>　　if n1<=371 & n2<=371 & n1>320 & n2>320</p><p>　　a=jiedian2(n1,2);</p><p>　　b=jiedian2(n1,3);</p><p>　　c=jiedian2(n2,2);</p><p>　　d