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

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

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

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

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

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 單目標最短路徑問題4</p><p>　　1.2.3 單對結點間的最短路徑問題4</p><p>　　1.3 電子地圖的基本概念5</p><p>　　1.3.1 電子地圖的基本性質5</p><p>　　1.3.2 電子地圖的一般特點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算法實現(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算法實現(xiàn)8</p><p>　　2.3 SPFA算法9</p><p>　　2.3.1 SPFA算法的思想9</p><p>　　2.3.2 SPFA

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

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

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

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

23、的求解20</p><p><b>　　結 論23</b></p><p><b>　　參考文獻24</b></p><p><b>　　附 錄25</b></p><p><b>　　致 謝28</b></p><

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

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

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

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

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

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

30、</p><p>　　1.1.1 圖的基本概念</p><p>　　一集元素及其之間的某種關系稱之為圖。具體來說，圖通常就是一個二元組，其中集合為頂點集，集合是頂點集中元素組成的無序對的集合，稱為邊集。</p><p><b>　　例1 給定,其中</b></p><p>　　這便定義了一個無向圖,如下</p>

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

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

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

34、都有方向相反的有向邊相連則稱此圖為完全有向圖。</p><p>　　競賽圖：階圖中如果其底圖是無向完全圖，則稱此有向完全圖為競賽圖。</p><p>　　圖1.2 賦權有向圖</p><p>　　1.1.2 鄰接矩陣</p><p>　　鄰接矩陣為儲存圖中“邊”信息的一種方法，為表示各個頂點之間關系的矩陣。設是一個具有個頂點的圖，則圖的鄰接矩

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

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

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

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

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

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

41、成性；</p><p>　　⑵使用電子地圖過程中的交互性：區(qū)別于紙質地圖，可以讓用戶交互操作；</p><p>　?、切畔⒈磉_的多樣性：地圖載負量極大擴展；</p><p>　?、榷嗉壙s放和多尺度數(shù)據(jù)：快速、高效的信息檢索與地圖分析；</p><p>　?、啥嗑S和動態(tài)可視化：使地圖效果更加突出；</p><p>　?、?/p>

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

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

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

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

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

47、頂點（從）的最短路及其長度而言渡數(shù)組中，表示從到的最短路徑上前一個頂點的序號，若，表示從到直達且該路徑最短；反之，采用“倒序追蹤”，得到從到最短路徑的行進路線。初始時，若到之間有邊，則；若到之間無邊，則。</p><p>　　得到初始集合，算法實現(xiàn)的步驟為：</p><p>　?、旁谒鶎闹袑ふ易钚≈怠?；</p><p>　　⑵將對應的改為，表示從到已找到最短

48、路徑；</p><p>　?、窃谝呀?jīng)找到最短路徑后，檢查所有標記數(shù)組所對應的頂點，若頂點與有直接相連的邊，且，說明從直接到的路徑，大于先從到，在從到的路徑，此時修改距離數(shù)組中，過渡數(shù)組中；反之則不需要改動</p><p>　　⑷由改動的距離數(shù)組，標記數(shù)組，過渡數(shù)組組成一個新的集合,重新進行上述步驟，只要標記數(shù)組中所有元素均為。</p><p><b>　　

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

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

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

52、個頂點的序號。</p><p><b>　　算法實現(xiàn)的步驟為：</b></p><p>　　⑴初始時，，選擇一個計數(shù)變量，并令，而若到之間有邊，則；若到之間無邊，則；</p><p>　　⑵比較大小，若小于，則。將改為兩者的最小值，且在原來值的基礎上加一，即；</p><p>　?、侵貜偷诙?，直到0000，此時代表著從

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

75、作為檢索結果所需要的地點信息，根據(jù)用途或屬性的不同可能需要各種不同數(shù)據(jù)信息。這些信息如果用一個地點信息來表示則會顯得冗長，所以有必要準備由多個適當?shù)臄?shù)據(jù)信息構成一個地點信息來共用。在數(shù)據(jù)模型的管理中，可由實現(xiàn)特定檢索方式的檢索關鍵字數(shù)據(jù)，作為檢索結果的共有的基礎索引數(shù)據(jù)，并將其組合為目錄的形式劃分區(qū)域進行管理。</p><p>　　4 電子地圖與最短路徑算法的結合</p><p>　　在把

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

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

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

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

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

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

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

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

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

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

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

87、取出每列的最小值，計入到原本為設為全0的的矩陣A的相應的位置。</p><p>　　對于每一列而言，每列的最小值是最有可能小于3分鐘的，如果最小值都不滿足這個條件，那么對于這列對應的節(jié)點而言，就不存在三分鐘可以到達的平臺,所用程序為：.</p><p>　?、怯纱?，最后每個節(jié)點都會歸屬于某個服務平臺，用編程得出結果并繪制了管轄區(qū)域圖如表4.1.</p><p>　　

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

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

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

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

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

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

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

95、p>　?、侵鹦信袛啵绻承械呐袛嗌蠑?shù)大于所有節(jié)點案發(fā)率平均數(shù)乘以2的話，就把該行中的最大數(shù)字在中置為0。</p><p>　?、戎貜蜕鲜鋈?，五次。</p><p>　　圖4.4 迭代前綜合指標曲線分布與直方圖</p><p>　　表4.3 調整后服務平臺管轄范圍</p><p><b>　　結 論</b>

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

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

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

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

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

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

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

103、煌.運籌學原理與方法[M].成都:西南交通大學出版社,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