【正文】 概述 國內(nèi)外最短路徑算法概況 國內(nèi)外最短路徑研究的主流與方向 最短路徑這一重要問 題早在 20世紀初就已經(jīng)得到人們的高度重視，當時也有許多科學家研究這一重要問題的求解方法。但直到 1959年荷蘭計算機科學家 Edsger Wybe Dijkstra (迪杰斯特拉 )才給出這一問題求解的基本思想，并給出了算法。當時的 Dijkstra提出的這一算法主要解決的問題是從固定的一個點到其他各點的最短路徑問題。后來這個算法就成了眾所周知的 Dijkstra算法，也成為了一代經(jīng)典。 [1] 現(xiàn)今比較流行的最短路徑規(guī)劃算法主要有以下三類：第一類是基于圖論理論的算法；如 Dijkstra及其改進算法， Floyd算法等 ；第二類則是基于傳統(tǒng)人工智能理論的算法，如 A*機器改進算法，深度有限、寬度有限算法等；第三類則是基于智能控制技術的算法，如人工神經(jīng)網(wǎng)絡算法、遺傳算法等。特別是近 10年來，智能控制技術在路徑規(guī)劃問題中得到廣泛的應用，人們的研究興趣也逐漸從對前兩類算法的改進轉(zhuǎn)到了對第三類算法的進一步研究中。 當前對于最短路徑的相關研究主要包含兩方面。第一方面為最短路徑問題（完全信息情況下）。在這種確定情況下最短路徑問題的研究中， Bellman（ 1958）、Dijkstra（ 1959）和 Dreyfus（ 1969）已發(fā)展出許多高效 算法。這些算法已成為確定情況下的經(jīng)典算法。在不確定的情況下最短路徑問題的研究包含以下幾個方面：Frank（ 1969）和 Mirchandani（ 1976）研究了路段長度隨機變化的且非時間獨立的情況下的最短路徑問題； Loui（ 1983）、 Muethy 和 Sarkar（ 1996）考慮不同的費用函數(shù)研究最短路徑問題，他們的結(jié)論是當目標是期望最短路徑時問題轉(zhuǎn)化為將邊的權重用期望值表示的最短路徑問題； Hall（ 1986）、 LiPing Fu 和 （ 1998）、Elise 和 Hani（ 2020）研究了路段長度 隨機變化且時間獨立情況下的最短路徑問題；Tomas 和 Rajeev 研究了路段長度為區(qū)間范圍的最短路徑問題。 [2] 2 國內(nèi)外主流算法及其簡要展開 A*算法 [3] A*（ AStar)算法是一種靜態(tài)路網(wǎng)中求解最短路最有效的方法。公式表示為： f(n)=g(n)+h(n) 其中 f(n) 是節(jié)點 n 從初始點到目標點的估價函數(shù)， g(n) 是在狀態(tài)空間中從初始節(jié)點到 n 節(jié)點的實際代價， h(n)是從 n 到目標節(jié)點最佳路徑的估計代價。保證找到最短路徑（最優(yōu)解的）條件，關鍵在于估價函數(shù) h(n)的選?。汗纼r值 h(n)= n 到目標節(jié)點的 距離實際值，這種情況下，搜索的點數(shù)多，搜索范圍大，效率低。但能得到最優(yōu)解。如果 估價值 實際值 , 搜索的點數(shù)少，搜索范圍小，效率高，但不能保證得到最優(yōu)解。估價值與實際值越接近，估價函數(shù)取得就越好。 A*算法是人工智能中一種典型的啟發(fā)式搜索算法， 算法的創(chuàng)新之處在于選擇了下一個被探索的結(jié)點時引入了已知的路網(wǎng)信息和目標點信息，對當前點與終點的距離進行評估，作為選擇下一路徑結(jié)點的依據(jù)。通用的 A*算法可采用四方向，八方向，對于矢量路網(wǎng)則可采用遍歷相連路徑法進行路徑探索。在城鎮(zhèn)地價定級估價中，不考慮路網(wǎng)，可采用柵格八方 向法。通過 A*算法可以尋找任何一個因素因子與其它各點之間的最短路徑。 它不用遍歷整個搜索空間，而是根據(jù)所選擇的啟發(fā)式函數(shù)朝著最有希望的方向前進。它的搜索速度雖然較快，理論上也能找到最優(yōu)解，但在實際應用過程中往往由于啟發(fā)式函數(shù)選取不當而經(jīng)常找不到最短路徑，搜索的成功率并不是很高。 遺傳算法 [4] 遺傳算法 （ Geic Algorithms，簡稱 GA） 是模擬達爾文的遺傳選擇和自然淘汰的生物進化過程的計算模型。它的思想源于生物遺傳學和適者生存的自然規(guī)律，是具有 ―生存 +檢測 ‖的迭代過程的搜索算法。 GA 把每一個可 能的解編碼為一個向量，稱為一個染色體，向量的每一個元素稱為基因。所有染色體組成群體。并按預定的目標函數(shù)對每個染色體進行評價，根據(jù)其結(jié)果給出一個適應度的值。算法開始時先隨機地產(chǎn)生一些染色體，計算其適應度，根據(jù)適應度對諸染色體進行選擇、交換、變異等遺傳操作，剔除適應度 3 低的染色體，留下適應度高的染色體。由于新群體的成員是上一代群體的優(yōu)秀者，因而在總體上優(yōu)于上一代。 GA 就這樣反復迭代，直至滿足某種預定的優(yōu)化指標。上述 GA 的工作過程可用圖 簡要描述。 圖 遺傳算法工作原理示意圖 Dijkstra算法 Dijkstra算法的基本思想是，設置一個頂點的集合 S，從源點 S到集合中的各頂點的最終最短路徑的權值均已經(jīng)確定。算法反復選擇具有最短路徑估計的頂點 i∈ V—S，并將 i加入 S中，對 i的所有出邊進行松弛（本文第 2章節(jié)將對經(jīng)典 Dijkstra算法做詳細研究）。 Y 問題的初始（侯選）解 種群滿足預定指標 編碼為染色體（向量） 種群 P（ t） 計算各染色體適應度 通過遺傳運算存優(yōu)去劣 種群 P（ t+1） 復制 交換 變異 種群 P（ t） ?種群 P（ t+1） 解碼染色體 問題解答空間 N 4 經(jīng)典 Dijkstra算法 存在的問題 （ 1）原始 Dijkstra 算法在存儲圖形數(shù)據(jù)和運算時，基于網(wǎng)絡的權矩陣，需要根據(jù)其節(jié)點與距離之間的關系，形成關聯(lián)矩陣、鄰接矩陣與距離矩陣，需要定義 NN的數(shù)組來存儲 數(shù)據(jù)，其中 N 為網(wǎng)絡的節(jié)點數(shù)，當網(wǎng)絡的節(jié)點數(shù)較大時，將占用大量的計算機內(nèi)存。 （ 2）原始 Dijkstra 算法在運行時一般將網(wǎng)絡節(jié)點分為未標記節(jié)點、臨時標記節(jié)點和永久標記節(jié)點 3 種類型。網(wǎng)絡中所有節(jié)點首先初始化為未標記節(jié)點，在搜索過程中和最短路徑節(jié)點相連通的節(jié)點為臨時標記節(jié)點，每一次循環(huán)都是從臨時標記節(jié)點中搜索距離原點路徑長度最短的節(jié)點作為永久標記節(jié)點，直至找到目標節(jié)點或者所有節(jié)點都成為永久標記節(jié)點才結(jié)束算法。根據(jù)算法的描述可知對臨時標記節(jié)點的遍歷成為 Dijkstra 算法的瓶頸，影響了算法的執(zhí)行效率。 研究的意義 隨著社會的不斷進步，最短路徑算法在人們的日常生活顯得越來越重要。每天開車去上班，應該選擇哪條公路才能使自己到公司的費用最低、時間最少，這是最短路徑的問題；在網(wǎng)絡路由中，怎樣選擇最優(yōu)的路由路徑，這也是最短路徑問題；在交通旅游、城市規(guī)劃以及電網(wǎng)架設中怎樣使其耗費的資金最少，這還是最短路徑問題。由此可見對最短路徑問題的研究是非常有意義的。 最短路徑算法是計算機科學與地理信息科學等領域研究的熱點，其算法有很多種，其中傳統(tǒng)的 Dijkstra 算法一般用于計算一個源節(jié)點到所有其他節(jié)點的最小代價路徑，并且能夠適應網(wǎng)絡拓 撲的變化，性能穩(wěn)定，因而可以在運輸路線規(guī)劃等領域都應用廣泛。 本文研究目標和內(nèi)容 Dijkstra 算法的空間復雜度 O(N2)，采用鄰接矩陣存儲網(wǎng)絡拓撲結(jié)構，需要（ NN）的存儲空間，查詢速率較快，在數(shù)秒內(nèi)即可完成查詢，所用時間在用戶的容忍范圍內(nèi)。但 Dijkstra 算法隨著節(jié)點數(shù) N 的增大，其計算效率和存儲效率越低。所以針對地理信息中的海量信息需要尋求算法優(yōu)化，對 Dijkstra 算法優(yōu)化的思 5 路主要有： ① 縮小節(jié)點的搜索范圍，只對最短路徑上節(jié)點的鄰居作處理，而不涉及相離節(jié)點的其他節(jié)點。算法優(yōu)化思想：首先從與起點 s 直接相連的相鄰節(jié)點幾個 NBk 中選擇距離最小的節(jié)點 k 作為轉(zhuǎn)接點，同時將 k 劃歸為表示集合 S（初始時， S 為 {s}）。然后對 k 另據(jù)集合與表示集合的差集，（ NBk S）中節(jié)點 j 的 wj值進行更新，從標識集合 S 中所有節(jié)點的鄰居集合的并集與標識集合 S 的差集（ ∪ NBi S,i∈ S）中選擇一個 wk值最小的節(jié)點作為下一個轉(zhuǎn)接點，并劃歸為到標識集合 S 中。重復上述過程，直到所有的節(jié)點都被標識過，即 │S│=N，算法結(jié)束。 ② 由于現(xiàn)實中只需要查詢起點和終點間的最短路徑，而不需要求出起點到多有節(jié)點的最短路徑，所以根據(jù)需要只要找到起 點到終點的最短距離即可退出循環(huán)處理過程，縮短查詢時間。 ③ Dijkstra 算法的核心步驟，即從具有臨時標號的節(jié)點中搜索與起點距離最小的節(jié)點，如果具有臨時標號的節(jié)點無序地存放在數(shù)組中，則每次迭代都要把所有未獲得永久標號的都掃描一遍，所以將具有臨時標號的節(jié)點按與起點距離大小進行排序則可以節(jié)省每次掃描的時間，提高查詢速率。 ④ 改進數(shù)據(jù)的組織結(jié)構，用類或結(jié)構體來組織節(jié)點、線路并建立拓撲關系可以提高數(shù)據(jù)搜索效率。 6 第 2章 Dijkstra經(jīng)典算法研究 Dijkstra 算法的原理及應用 Dijkstra算法原理 Dijkstra算法是 1959年由 E． W． Dijkstra提出的圖論中求最短路徑的一個著名的算法，使用其可以求得圖中一點到其他各頂點的最短路徑。原始的 Dijkstra算法將網(wǎng)絡結(jié)點分成 3部分：未標記結(jié)點、臨時標記結(jié)點和永久標記結(jié)點。網(wǎng)絡中所有結(jié)點首先初始化為未標記結(jié)點，在搜索過程中和最短路徑中的結(jié)點相連通的結(jié)點為臨時標記結(jié)點，每次循環(huán)都是從臨時標記結(jié)點中搜索距源點路徑長度最短的結(jié)點作為永久標記結(jié)點，直至找到目標結(jié)點或者所有的結(jié)點都成為永久標記結(jié)點來結(jié)束算法。 假設每個點都有一對標號 (wj, pj)，其中 wj 是從起源點 s到點 j的最短路徑的長度 (從頂點到其本身的最短路徑是零路 (沒有弧的路 )，其長度等于零 )； pj 則是從 s到 j的最短路徑中 j點的前一點。求解從起源點 s到點 j的最短路徑算法的基本過程如下： 1)初始化。起源點設置為： ① ws=0, ps為空； ② 所有其他點 : wi=∞, pi=?； ③ 標記起源點 s，記 k=s,其他所有點設為未標記的。 2)檢驗從所有已標記的點 k 到其直接連接的未標記的點 j的距離，并設置：wj=min{ wj, wk+dkj }式中， dkj 是從點 k到 j的直接連接距離。 3)選取下一個點。從所有未標記的結(jié)點中，選取 wj中最小的一個 i： wi=min wj，（所有未標記的點 j），點 i就被選為最短路徑中的一點，并設為已標記的。 4)找到點 i的前一點。從已標記的點中找到直接連接到點 i的點 j*，作為前一點 ， 設置： i=j*。 5)標記點 i。如果所有點已標記，則算法完全推出，否則，記 k=i，轉(zhuǎn)到 2)再繼續(xù)。 7 Dijkstra算法最短路徑應用演示 圖 Dijkstra算法最短路徑應用 演示圖 表 從 0節(jié)點到 4節(jié)點的最短路徑 循環(huán) 紅點集 S K D{0} D{1} D{2} D{3} D{4} P{0} P{1} P{2} P{3} P{4} 初始化 {0} 0 10 ∞ 30 100 1 0 1 0 0 1 {0,1} 1 0 10 60 30 100 1 0 1 0 0 2 {0,1,3} 3 0 10 50 30 90 1 0 3 0 3 3 {0,1,3,2} 2 0 10 50 30 60 1 0 3 0 2 4 {0,1,3,2,4} 4 0 10 50 30 60 1 0 3 0 2 Dijkstra算法應用 給定簡單無向圖 G,指定一頂點 Vi為起點 ,對于任意 Vj∈ G 且 i≠j,求 Vi到 Vj 的最短路徑的長度。 例 :北京的小湯山醫(yī)院已經(jīng)投入使用了 ,在抗擊非典的戰(zhàn)役中發(fā)揮了重要的作用?，F(xiàn)在 ,在北京市內(nèi)有若干家收治非典病人的醫(yī)院。各個醫(yī)院之間的路程和各醫(yī)院到小湯山之間的路程已知 (有可能沒有直通道路 ),由于非典病人的特殊性 ,在往小湯山轉(zhuǎn)運的過程中只能在收治病人的醫(yī)院中轉(zhuǎn)?，F(xiàn)在 ,黨和政府交給了你一個光榮而艱巨的任務 ,計算出小湯山到市內(nèi)各收治醫(yī)院的最短路徑 ,為抗非事業(yè)做出你應有的 貢獻。 8 給定問題的算法分析 : 1)初始化：起點的最短路徑為 0，其他頂點的最短路徑為 ∞，所有頂點未標號。 2)在所有未標號的頂點中找出最短路徑最短的頂點 i。若無法找到，則說明所有頂點已標號，或者所有的未標號頂點都是無法到達的，轉(zhuǎn) 5)。 3)更改所有與 i直接相鄰的未標號頂點的最短路徑。更新方法如下： 如果 i的最短路徑邊 ij 的長度 j目前的最短路徑，則 j的最短路徑更新為 i的最短路徑邊 ij的長度，否則不變（也就是意味著通過 i走向 j比原來的方向走向 j能獲得更短的路徑）。 4)轉(zhuǎn) 2。 5)輸出結(jié)果。 例 : 找所有未標號中距離最短的頂點為 醫(yī)院 1,將 1做標號 ,更新與 1相鄰的 2和 3的距離 醫(yī)院 1 未標號 距離 0 醫(yī)院 2 未標號 距離 ∞ 醫(yī)院 3 未標號 距離 ∞ 醫(yī)院 4 未標號 距離 ∞ 12 4 5 6 9 找所有未標號中距離最短的頂點為 醫(yī)院 3,將 3做標號 ,更新與 1相鄰的 4的距離 找所有未標號中距離最短的頂點為 醫(yī)院 4,將 4做標號 ,更新與 1相鄰的 2的距離 (因