【正文】 ................................................................... 23 算法優(yōu)化前后對(duì)比 ............................................................................. 25 第 5 章 總結(jié)與展望 ................................................................................................ 26 全文總結(jié) .................................................................................................... 26 展望 ............................................................................................................ 26 參考文獻(xiàn) ..................................................................................................................... 27 附 錄 ....................................................................................................................... 29 致 謝 ....................................................................................................................... 35 1 第 1章 概述 國(guó)內(nèi)外最短路徑算法概況 國(guó)內(nèi)外最短路徑研究的主流與方向 最短路徑這一重要問(wèn) 題早在 20世紀(jì)初就已經(jīng)得到人們的高度重視，當(dāng)時(shí)也有許多科學(xué)家研究這一重要問(wèn)題的求解方法。因此，在優(yōu)化算法中計(jì)算的節(jié)點(diǎn)數(shù)大幅減少，提高了算法的速度。傳統(tǒng) Dijkstra算法在求解節(jié)點(diǎn)間最短路徑時(shí)，對(duì)已標(biāo)識(shí)節(jié)點(diǎn)以外的大量節(jié)點(diǎn)進(jìn)行了計(jì)算，從而影響了算法的速度。 畢業(yè)設(shè)計(jì)（論文） 題 目 基于 Dijkstra 的最短路徑搜索算法的優(yōu)化及應(yīng)用 姓 名 學(xué) 號(hào) 專(zhuān)業(yè)班級(jí) 指導(dǎo)教師 分 院 完成日期 I 摘 要 最短路徑分析是 GIS地理網(wǎng)絡(luò)分析功能中的一個(gè)關(guān)鍵問(wèn)題。 Dijkstra算法是計(jì)算最短路徑的經(jīng)典算法， 是許多工程解決最短路徑問(wèn)題的理論基礎(chǔ) 。 本文 在對(duì)傳統(tǒng) Dijkstra算法分析的基礎(chǔ)上，對(duì)其進(jìn)行了優(yōu)化，優(yōu)化算法只對(duì)最短路徑上節(jié)點(diǎn)的鄰居做了處理 ， 而不涉及到其他節(jié)點(diǎn)。本文通過(guò)實(shí)驗(yàn)和實(shí)際應(yīng)用對(duì)改進(jìn)后的算法進(jìn)行了驗(yàn)證。但直到 1959年荷蘭計(jì)算機(jī)科學(xué)家 Edsger Wybe Dijkstra (迪杰斯特拉 )才給出這一問(wèn)題求解的基本思想，并給出了算法。后來(lái)這個(gè)算法就成了眾所周知的 Dijkstra算法，也成為了一代經(jīng)典。特別是近 10年來(lái)，智能控制技術(shù)在路徑規(guī)劃問(wèn)題中得到廣泛的應(yīng)用，人們的研究興趣也逐漸從對(duì)前兩類(lèi)算法的改進(jìn)轉(zhuǎn)到了對(duì)第三類(lèi)算法的進(jìn)一步研究中。第一方面為最短路徑問(wèn)題（完全信息情況下）。這些算法已成為確定情況下的經(jīng)典算法。 [2] 2 國(guó)內(nèi)外主流算法及其簡(jiǎn)要展開(kāi) A*算法 [3] A*（ AStar)算法是一種靜態(tài)路網(wǎng)中求解最短路最有效的方法。保證找到最短路徑（最優(yōu)解的）條件，關(guān)鍵在于估價(jià)函數(shù) h(n)的選?。汗纼r(jià)值 h(n)= n 到目標(biāo)節(jié)點(diǎn)的 距離實(shí)際值，這種情況下，搜索的點(diǎn)數(shù)多，搜索范圍大，效率低。如果 估價(jià)值 實(shí)際值 , 搜索的點(diǎn)數(shù)少，搜索范圍小，效率高，但不能保證得到最優(yōu)解。 A*算法是人工智能中一種典型的啟發(fā)式搜索算法， 算法的創(chuàng)新之處在于選擇了下一個(gè)被探索的結(jié)點(diǎn)時(shí)引入了已知的路網(wǎng)信息和目標(biāo)點(diǎn)信息，對(duì)當(dāng)前點(diǎn)與終點(diǎn)的距離進(jìn)行評(píng)估，作為選擇下一路徑結(jié)點(diǎn)的依據(jù)。在城鎮(zhèn)地價(jià)定級(jí)估價(jià)中，不考慮路網(wǎng)，可采用柵格八方 向法。 它不用遍歷整個(gè)搜索空間，而是根據(jù)所選擇的啟發(fā)式函數(shù)朝著最有希望的方向前進(jìn)。 遺傳算法 [4] 遺傳算法 （ Geic Algorithms，簡(jiǎn)稱(chēng) GA） 是模擬達(dá)爾文的遺傳選擇和自然淘汰的生物進(jìn)化過(guò)程的計(jì)算模型。 GA 把每一個(gè)可 能的解編碼為一個(gè)向量，稱(chēng)為一個(gè)染色體，向量的每一個(gè)元素稱(chēng)為基因。并按預(yù)定的目標(biāo)函數(shù)對(duì)每個(gè)染色體進(jìn)行評(píng)價(jià)，根據(jù)其結(jié)果給出一個(gè)適應(yīng)度的值。由于新群體的成員是上一代群體的優(yōu)秀者，因而在總體上優(yōu)于上一代。上述 GA 的工作過(guò)程可用圖 簡(jiǎn)要描述。算法反復(fù)選擇具有最短路徑估計(jì)的頂點(diǎn) i∈ V—S，并將 i加入 S中，對(duì) i的所有出邊進(jìn)行松弛（本文第 2章節(jié)將對(duì)經(jīng)典 Dijkstra算法做詳細(xì)研究）。 （ 2）原始 Dijkstra 算法在運(yùn)行時(shí)一般將網(wǎng)絡(luò)節(jié)點(diǎn)分為未標(biāo)記節(jié)點(diǎn)、臨時(shí)標(biāo)記節(jié)點(diǎn)和永久標(biāo)記節(jié)點(diǎn) 3 種類(lèi)型。根據(jù)算法的描述可知對(duì)臨時(shí)標(biāo)記節(jié)點(diǎn)的遍歷成為 Dijkstra 算法的瓶頸，影響了算法的執(zhí)行效率。每天開(kāi)車(chē)去上班，應(yīng)該選擇哪條公路才能使自己到公司的費(fèi)用最低、時(shí)間最少，這是最短路徑的問(wèn)題；在網(wǎng)絡(luò)路由中，怎樣選擇最優(yōu)的路由路徑，這也是最短路徑問(wèn)題；在交通旅游、城市規(guī)劃以及電網(wǎng)架設(shè)中怎樣使其耗費(fèi)的資金最少，這還是最短路徑問(wèn)題。 最短路徑算法是計(jì)算機(jī)科學(xué)與地理信息科學(xué)等領(lǐng)域研究的熱點(diǎn)，其算法有很多種，其中傳統(tǒng)的 Dijkstra 算法一般用于計(jì)算一個(gè)源節(jié)點(diǎn)到所有其他節(jié)點(diǎn)的最小代價(jià)路徑，并且能夠適應(yīng)網(wǎng)絡(luò)拓 撲的變化，性能穩(wěn)定，因而可以在運(yùn)輸路線(xiàn)規(guī)劃等領(lǐng)域都應(yīng)用廣泛。但 Dijkstra 算法隨著節(jié)點(diǎn)數(shù) N 的增大，其計(jì)算效率和存儲(chǔ)效率越低。算法優(yōu)化思想：首先從與起點(diǎn) s 直接相連的相鄰節(jié)點(diǎn)幾個(gè) NBk 中選擇距離最小的節(jié)點(diǎn) k 作為轉(zhuǎn)接點(diǎn)，同時(shí)將 k 劃歸為表示集合 S（初始時(shí)， S 為 {s}）。重復(fù)上述過(guò)程，直到所有的節(jié)點(diǎn)都被標(biāo)識(shí)過(guò)，即 │S│=N，算法結(jié)束。 ③ Dijkstra 算法的核心步驟，即從具有臨時(shí)標(biāo)號(hào)的節(jié)點(diǎn)中搜索與起點(diǎn)距離最小的節(jié)點(diǎn)，如果具有臨時(shí)標(biāo)號(hào)的節(jié)點(diǎn)無(wú)序地存放在數(shù)組中，則每次迭代都要把所有未獲得永久標(biāo)號(hào)的都掃描一遍，所以將具有臨時(shí)標(biāo)號(hào)的節(jié)點(diǎn)按與起點(diǎn)距離大小進(jìn)行排序則可以節(jié)省每次掃描的時(shí)間，提高查詢(xún)速率。 6 第 2章 Dijkstra經(jīng)典算法研究 Dijkstra 算法的原理及應(yīng)用 Dijkstra算法原理 Dijkstra算法是 1959年由 E． W． Dijkstra提出的圖論中求最短路徑的一個(gè)著名的算法，使用其可以求得圖中一點(diǎn)到其他各頂點(diǎn)的最短路徑。網(wǎng)絡(luò)中所有結(jié)點(diǎn)首先初始化為未標(biāo)記結(jié)點(diǎn)，在搜索過(guò)程中和最短路徑中的結(jié)點(diǎn)相連通的結(jié)點(diǎn)為臨時(shí)標(biāo)記結(jié)點(diǎn)，每次循環(huán)都是從臨時(shí)標(biāo)記結(jié)點(diǎn)中搜索距源點(diǎn)路徑長(zhǎng)度最短的結(jié)點(diǎn)作為永久標(biāo)記結(jié)點(diǎn)，直至找到目標(biāo)結(jié)點(diǎn)或者所有的結(jié)點(diǎn)都成為永久標(biāo)記結(jié)點(diǎn)來(lái)結(jié)束算法。求解從起源點(diǎn) s到點(diǎn) j的最短路徑算法的基本過(guò)程如下： 1)初始化。 2)檢驗(yàn)從所有已標(biāo)記的點(diǎn) k 到其直接連接的未標(biāo)記的點(diǎn) j的距離，并設(shè)置：wj=min{ wj, wk+dkj }式中， dkj 是從點(diǎn) k到 j的直接連接距離。從所有未標(biāo)記的結(jié)點(diǎn)中，選取 wj中最小的一個(gè) i： wi=min wj，（所有未標(biāo)記的點(diǎn) j），點(diǎn) i就被選為最短路徑中的一點(diǎn)，并設(shè)為已標(biāo)記的。從已標(biāo)記的點(diǎn)中找到直接連接到點(diǎn) i的點(diǎn) j*，作為前一點(diǎn) ， 設(shè)置： i=j*。如果所有點(diǎn)已標(biāo)記，則算法完全推出，否則，記 k=i，轉(zhuǎn)到 2)再繼續(xù)。 例 :北京的小湯山醫(yī)院已經(jīng)投入使用了 ,在抗擊非典的戰(zhàn)役中發(fā)揮了重要的作用。各個(gè)醫(yī)院之間的路程和各醫(yī)院到小湯山之間的路程已知 (有可能沒(méi)有直通道路 ),由于非典病人的特殊性 ,在往小湯山轉(zhuǎn)運(yùn)的過(guò)程中只能在收治病人的醫(yī)院中轉(zhuǎn)。 8 給定問(wèn)題的算法分析 : 1)初始化：起點(diǎn)的最短路徑為 0，其他頂點(diǎn)的最短路徑為 ∞，所有頂點(diǎn)未標(biāo)號(hào)。若無(wú)法找到，則說(shuō)明所有頂點(diǎn)已標(biāo)號(hào)，或者所有的未標(biāo)號(hào)頂點(diǎn)都是無(wú)法到達(dá)的，轉(zhuǎn) 5)。更新方法如下： 如果 i的最短路徑邊 ij 的長(zhǎng)度 j目前的最短路徑，則 j的最短路徑更新為 i的最短路徑邊 ij的長(zhǎng)度，否則不變（也就是意味著通過(guò) i走向 j比原來(lái)的方向走向 j能獲得更短的路徑）。 5)輸出結(jié)果。 如節(jié)點(diǎn)數(shù)為 n的圖，用 Dijkstra算法計(jì)算最短路徑總共需要迭代 n一 1次，每次迭代都新加一個(gè)節(jié)點(diǎn)到臨時(shí)節(jié)點(diǎn)集合中 ，由于第 i次迭代時(shí)不在臨時(shí)節(jié)點(diǎn)集合中的節(jié)醫(yī)院 1 已 標(biāo)號(hào) 距離 0 醫(yī)院 2 已 標(biāo)號(hào) 距離 ∞ 醫(yī)院 3 已 標(biāo)號(hào) 距離 4 醫(yī)院 4 已 標(biāo)號(hào) 距離 9 12 4 5 6 醫(yī)院 1 已 標(biāo)號(hào) 距離 0 醫(yī)院 2 未標(biāo)號(hào) 距離 12 醫(yī)院 3 已 標(biāo)號(hào) 距離 4 醫(yī)院 4 以 標(biāo)號(hào) 距離 9 12 4 5 6 11 點(diǎn) 數(shù)為 ni．即第 i次迭代需對(duì) ni個(gè)節(jié)點(diǎn)進(jìn)行處理，因此其所需的處理數(shù)為11( 1)() 2ninnni?????? ，對(duì) n個(gè)節(jié)點(diǎn)網(wǎng)絡(luò)的時(shí)間復(fù)雜度是 O(n2)。 下一個(gè)例子說(shuō)明 Dijkstra算法存在的缺陷： 例：圖 G(V， E， W)，求從 v1出發(fā)到其 它各個(gè)頂點(diǎn)的最短路徑長(zhǎng)度。當(dāng)選出 v4后，需要對(duì) U中的各個(gè)頂點(diǎn)的距離進(jìn)行調(diào)整，在調(diào)整過(guò)程中利用到 wi =min{wi， w4+d4i}其中 i≠1， 4(1， 4已經(jīng)在 S中 )即需要對(duì) wi和 w4+d4i進(jìn)行比較，但我們?cè)趯?duì) w3,w5,w7進(jìn)行調(diào)整時(shí)可以發(fā)現(xiàn)由于 d43，d45， d47 ? E(G)即它們的權(quán)值為 ∞，所以調(diào)整時(shí)是沒(méi)有必要進(jìn)行 比較的，在這里多進(jìn)行了 3次比較。 以 Dijkstra 算法為基礎(chǔ)算法進(jìn)行優(yōu)化的原因 Dijkstra算法與其他主流算法的比較 [5] 搜索速度比較 對(duì) 5張圖分別采用 Dijkstra算法、 A*算法、遺傳算法進(jìn)行路徑規(guī)劃，他們各自花費(fèi)的時(shí)間如表 。對(duì)于實(shí)際地圖而言，由于節(jié)點(diǎn)與道路的數(shù)量一般都很的大， Dijkstra算法在搜索速度方 13 面弱勢(shì)明顯。 對(duì) 5張地圖分別采用三種算法進(jìn)行路徑規(guī)劃，三者各自搜索到最短路徑的情況如表 。 表 三種算法在搜索質(zhì)量方面的對(duì)比 節(jié)點(diǎn)數(shù) Dijkstra算法 A*算法 遺傳算法 16 15(100%) 12(80%) 15(100%) 32 31(100%) 25(81%) 29(94%) 43 42(100%) 32(76%) 38(90%) 62 61(100%) 40(66%) 56(92%) 78 77(100%) 45(58%) 71(92%) 由表 ：當(dāng)?shù)貓D節(jié)點(diǎn)個(gè)數(shù)和弧數(shù)量比較多時(shí)， Dijkstra算法是一種遍歷算法，每次能保證 100%搜索到最短路徑，遺傳算法搜索到最短路徑的成功率比Dijkstra算法低一些， A*算法最低，且這種差距在節(jié)點(diǎn)數(shù)和弧數(shù)量越大時(shí)更加明顯。在對(duì)現(xiàn)實(shí)問(wèn)題中的交通圖初始化為網(wǎng)絡(luò)拓?fù)鋱D時(shí)，雖然終點(diǎn)已知，而源點(diǎn) 尚未確定，但依據(jù)常識(shí)離案發(fā)地段最近的派出所應(yīng)為案發(fā)地段所在轄區(qū) 派出所，或其周邊派出所，也就是源點(diǎn)的選取范圍可以確定。 第二類(lèi)優(yōu)化算法 ——改進(jìn)算法的存儲(chǔ)結(jié)構(gòu) 在實(shí)際工作中，還要建立起空間數(shù)據(jù)結(jié)構(gòu)。對(duì)于網(wǎng)絡(luò)數(shù)據(jù)的存儲(chǔ)，傳統(tǒng)的是采用圖論中的鄰接矩陣方法，其存儲(chǔ)量為 N N(N為網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù) )。若采用鄰接表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，其存儲(chǔ)量為 E(E為節(jié)點(diǎn)列表中，同節(jié)點(diǎn)關(guān)聯(lián)的所有邊的數(shù)目 )，可節(jié)省大量的存儲(chǔ)空間，尤其是在表示與節(jié)點(diǎn)和邊相關(guān)信息較多的地理網(wǎng)絡(luò)時(shí)，更為有效。 NET框架提供的特殊類(lèi)Hashtable。與數(shù)組類(lèi)似，集合類(lèi)可以把對(duì)象放入容器中，然后再取出．但集合的使用方法與數(shù)組不同，擁有用于插入和刪除項(xiàng)的專(zhuān)用方法。 15 本文對(duì) Dijkstra 優(yōu)化算法的研究 本文采用第一類(lèi)優(yōu)化算法減小搜索范圍的思路對(duì) Dijkstra算法進(jìn)行優(yōu)化。其時(shí)間復(fù)雜度為 O(N2)；采用鄰接矩陣存儲(chǔ)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，需要 (NN)的存儲(chǔ)空間，隨著節(jié)點(diǎn)數(shù) N的增大，其計(jì)算效率和存儲(chǔ)效率越低。 優(yōu)化算法思路 Dijkstra算法基本方法：設(shè) wj是從源點(diǎn) s到節(jié)點(diǎn) j的最短路徑長(zhǎng)度； pj是從 s到 j的最短路徑中 j點(diǎn)的前一節(jié)點(diǎn)。 Step1：在 T中找到節(jié)點(diǎn) i