【文章內(nèi)容簡介】 為距離 4+邊 2,4 的長度 距離 2,所以不更新 ) 醫(yī)院 1 已 標號 距離 0 醫(yī)院 2 未標號 距離 ∞ 醫(yī)院 3 已 標號 距離 4 醫(yī)院 4 未標號 距離 9 12 4 5 6 醫(yī)院 1 已 標號 距離 0 醫(yī)院 2 未標號 距離 ∞ 醫(yī)院 3 未標號 距離 4 醫(yī)院 4 未標號 距離 ∞ 12 4 5 6 10 找所 有未標號中距離最短的頂點為 醫(yī)院 2,將 2做標號 ,已沒有與 2相鄰的未標號頂點需要更新了 再次找所有未標號中距離最短的頂點已找不到 ,得結(jié)果 d(2)=12,d(3)=4,d(4)=9. Dijkstra算法的優(yōu)缺點 Dijkstra 算法能夠保證 100%找到最優(yōu)解，但其搜索速度較慢，搜索效率非常低，時間花費較多，一般只能用于離線的路徑規(guī)劃問題。 如節(jié)點數(shù)為 n的圖，用 Dijkstra算法計算最短路徑總共需要迭代 n一 1次，每次迭代都新加一個節(jié)點到臨時節(jié)點集合中 ，由于第 i次迭代時不在臨時節(jié)點集合中的節(jié)醫(yī)院 1 已 標號 距離 0 醫(yī)院 2 已 標號 距離 ∞ 醫(yī)院 3 已 標號 距離 4 醫(yī)院 4 已 標號 距離 9 12 4 5 6 醫(yī)院 1 已 標號 距離 0 醫(yī)院 2 未標號 距離 12 醫(yī)院 3 已 標號 距 離 4 醫(yī)院 4 以 標號 距離 9 12 4 5 6 11 點 數(shù)為 ni．即第 i次迭代需對 ni個節(jié)點進行處理，因此其所需的處理數(shù)為11( 1)() 2ninnni?????? ，對 n個節(jié)點網(wǎng)絡的時間復雜度是 O(n2)。在實際應用當中，使用 Dijkstra算法查找最短路徑時耗費大量的時間進行數(shù)據(jù)的比較，本文對 Dijkstra算法進行分析，通過改變算法實現(xiàn)減少不必要節(jié)點計算的時間，提高算法的效率達到對其進行優(yōu)化。 下一個例子說明 Dijkstra算法存在的缺陷： 例：圖 G(V， E， W)，求從 v1出發(fā)到其 它各個頂點的最短路徑長度。 圖 權圖 G 解： wi表示由源 v1到點 vi的最短距離； S表示已求出最短路徑的頂點集合，其初始值為 S{v1}； k表示剛選出的頂點的編號；選出 vk后修改 U中各頂點的距離的方法為：wi=min{wi， dki}； 下表通過 Dijkstra算法來求解圖 ： v1 初始 第一步 第二步 第三步 … v2 15 9 v3 ∞ ∞ v4 4 v5 ∞ ∞ v6 ∞ 10 v7 ∞ ∞ S={v1} v4 v2 k 12 w S v1,v4 v1,v2,v4 在上表中選出頂點 v4加入到 S時一共進行了 6次比較，其中四次是與 ∞作比較，也就是說這四次完全沒有必要進行比較。當選出 v4后，需要對 U中的各個頂點的距離進行調(diào)整，在調(diào)整過程中利用到 wi =min{wi， w4+d4i}其中 i≠1， 4(1， 4已經(jīng)在 S中 )即需要對 wi和 w4+d4i進行比較，但我們在對 w3,w5,w7進行調(diào)整時可以發(fā)現(xiàn)由于 d43，d45， d47 ? E(G)即它們的權值為 ∞，所以調(diào)整時是沒有必要進行 比較的，在這里多進行了 3次比較。后面的各步也都出現(xiàn)類似的情況 (后略 )，尤其是當圖的邊數(shù)相對較少時更為明顯。 以 Dijkstra 算法為基礎算法進行優(yōu)化的原因 Dijkstra算法與其他主流算法的比較 [5] 搜索速度比較 對 5張圖分別采用 Dijkstra算法、 A*算法、遺傳算法進行路徑規(guī)劃，他們各自花費的時間如表 。 表 三種算法在搜索速度上的對比 節(jié)點數(shù) 搜索速度 Dijkstra算法 A*算法 遺傳算法 16 1 1 2 32 4 2 4 43 7 3 6 62 15 5 9 78 25 7 12 由表 ：當?shù)貓D節(jié)點個數(shù)和弧的條數(shù)比較少時，三種算法所花費的時間差不多，當節(jié)點個數(shù)和弧的條數(shù)比較多時， A*算法最快，遺傳算法其次，Dijkstra算法最慢，而且這種差距將隨節(jié)點和弧數(shù)量的增加而變得更加明顯。對于實際地圖而言，由于節(jié)點與道路的數(shù)量一般都很的大， Dijkstra算法在搜索速度方 13 面弱勢明顯。 搜索成功率比較 對于具有 n個節(jié)點的地圖，其待規(guī)劃節(jié)點的個數(shù)為 n1（除起點節(jié)點外，其他均可作為待規(guī)劃節(jié)點），由于每個待規(guī)劃節(jié)點對應于一條最短路徑，所以對每張具有n個節(jié)點的 地圖而言，應該規(guī)劃出 n1條最短路徑。 對 5張地圖分別采用三種算法進行路徑規(guī)劃，三者各自搜索到最短路徑的情況如表 。表中括號外數(shù)據(jù)為各算法實際得到最短路徑數(shù)，括號內(nèi)數(shù)據(jù)則為各算法實際得到路徑數(shù)和應該規(guī)劃出的最短路徑數(shù) n1之比。 表 三種算法在搜索質(zhì)量方面的對比 節(jié)點數(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%) 由表 ：當?shù)貓D節(jié)點個數(shù)和弧數(shù)量比較多時， Dijkstra算法是一種遍歷算法，每次能保證 100%搜索到最短路徑，遺傳算法搜索到最短路徑的成功率比Dijkstra算法低一些， A*算法最低，且這種差距在節(jié)點數(shù)和弧數(shù)量越大時更加明顯。 14 第 3章 Dijkstra優(yōu)化算法研究 多種 Dijkstra 優(yōu)化算法的研究 [6] 第一類優(yōu)化算法 ——減小算法中成功搜索的搜索范圍 減小算法中成功搜索的搜索范圍以盡 快到達目標節(jié)點。在對現(xiàn)實問題中的交通圖初始化為網(wǎng)絡拓撲圖時，雖然終點已知，而源點 尚未確定，但依據(jù)常識離案發(fā)地段最近的派出所應為案發(fā)地段所在轄區(qū) 派出所，或其周邊派出所，也就是源點的選取范圍可以確定。利用 MapObjects2組件提供 的 (expression)記錄集篩選方法，根據(jù)案發(fā)地段 (終點 )的不同，動態(tài)選取案發(fā)地段所在轄區(qū)及相鄰轄區(qū)的道路圖層及派出所圖層數(shù)據(jù)進行最短路徑查詢，從而有效地減少了拓撲圖中節(jié)點總數(shù) n的值。 第二類優(yōu)化算法 ——改進算法的存儲結(jié)構 在實際工作中，還要建立起空間數(shù)據(jù)結(jié)構。網(wǎng)絡數(shù)據(jù)結(jié)構使用的是 ―邊和節(jié)點 ‖的數(shù)據(jù)結(jié)構，該數(shù)據(jù)結(jié)構是建立在圖論的基礎上，節(jié)點可用來定義邊的連接關系。對于網(wǎng)絡數(shù)據(jù)的存儲，傳統(tǒng)的是采用圖論中的鄰接矩陣方法，其存儲量為 N N(N為網(wǎng)絡中節(jié)點數(shù) )。通常的地理網(wǎng)絡，盡管節(jié)點很多，但與節(jié)點相關聯(lián)的節(jié)點數(shù)目并不多，一般都為稀疏圖，將會浪費大量的空間。若采用鄰接表的鏈式存儲結(jié)構，其存儲量為 E(E為節(jié)點列表中，同節(jié)點關聯(lián)的所有邊的數(shù)目 )，可節(jié)省大量的存儲空間，尤其是在表示與節(jié)點和邊相關信息較多的地理網(wǎng)絡時，更為有效。但鄰接表卻難 以判斷兩節(jié)點之間的關系，因此本文提出利用。 NET框架提供的特殊類Hashtable。 .NET框架包含特殊類，比如通常所說的集合類用于存儲對象。與數(shù)組類似，集合類可以把對象放入容器中，然后再取出．但集合的使用方法與數(shù)組不同，擁有用于插入和刪除項的專用方法。使用 Hashtable最大的優(yōu)點就是大大降低數(shù)據(jù)存儲和查找的時間花費，幾乎可看成是常數(shù)時間。 15 本文對 Dijkstra 優(yōu)化算法的研究 本文采用第一類優(yōu)化算法減小搜索范圍的思路對 Dijkstra算法進行優(yōu)化。 優(yōu)化算法的目標 Dijkstra算法用來求解圖上從任 一節(jié)點 (源點 )到其余各節(jié)點的最短路徑。其時間復雜度為 O(N2)；采用鄰接矩陣存儲網(wǎng)絡拓撲結(jié)構，需要 (NN)的存儲空間，隨著節(jié)點數(shù) N的增大，其計算效率和存儲效率越低。針對此問題，提出了 Dijkstra算法的改進，本文在對傳統(tǒng) Dijkstra算法分析的基礎上，對其進行了優(yōu)化，優(yōu)化算法只對最短路徑上節(jié)點的鄰居做處理，而不涉及到其他節(jié)點。 優(yōu)化算法思路 Dijkstra算法基本方法：設 wj是從源點 s到節(jié)點 j的最短路徑長度； pj是從 s到 j的最短路徑中 j點的前一節(jié)點。 S是標識集合； T是未標識集合； M是節(jié)點集合． dij提節(jié)點 i到節(jié)點 j的距離 (i與 j直接相連，否則 dij = ∞)．算法步驟如下： Step0： S = {s}； T = MS； wj = dij(j∈ T， s與 j直接相連 )或 wj = ∞(j ∈ T， s與 j不直接相連 )。 Step1：在 T中找到節(jié)點 i，使 s到 i的距離最小，并將 i劃歸到 S。 (可從與 s直接相連的 j中考慮 ) 若 dsi = min dsj j與 s直接相連，則將 i劃歸到 S中，即 S ={s， i}， T = T{i}； j∈ T pi =s。 Step2：修改 T中 j節(jié)點的 wj值： wj = min(wj,wi + dij)；若 wj值改變，則 pj = i． j∈ T i∈ S Step3：選定所有的 wj最小值，并將其劃歸到 S中： wi = min wj； S=S∪ {i}； T=T{i}；若 │S│= n, 所有節(jié)點已標識，則算法終 j∈ T 止，否則，轉(zhuǎn)人 Step2。 通過分析傳統(tǒng) Dijkstra算法的基本思路，傳統(tǒng) Dijkstra算法存在如下兩點不足： 16 (1)當從未標記節(jié)點集合 T中選定一個節(jié)點 k作為轉(zhuǎn)接點后時，需掃描未標記節(jié)點集合 T中的節(jié)點 j并更新其 wj值，而未標記節(jié)點集合 T中往往包含 大量與轉(zhuǎn)接節(jié)點 k 不直接相連的節(jié)點 i(即 dki = ∞)； (2)在未標記節(jié)點集合 T中選擇一個 w值最小的節(jié)點作為下一個轉(zhuǎn)接節(jié)點，然而下一個轉(zhuǎn)接節(jié)點往往是與標記節(jié)點集合 S中的節(jié)點直接相連的。 優(yōu)化算法描述 基于上述兩點不足，對傳統(tǒng) Dijkstra算法進行優(yōu)化，算法優(yōu)化思路為：首先從源點 s的鄰居集合 NBS(與 s直接相連的節(jié)點集合 )中選擇距離最小的鄰居節(jié)點 k作為轉(zhuǎn)接點，同時將劃歸到標識集合 S(初始時， S為 {s})。然后對 k鄰居集合與標識集合的差集 (NBk S)中節(jié)點的值進行更新，從標識集合 s中所有節(jié)點的鄰居集合 的并集與標識集合的差集 (∪ NBs S， i∈ S)中選擇一個 wk值最小的節(jié)點作為下一個轉(zhuǎn)接點，并劃歸到標識集合 S中。重復上述過程，直到所有的節(jié)點都被標識過，即 │S│=n，算法結(jié)束。 設 NBi為節(jié)點 i的鄰居集合； S為標識集合； wj是從源點 s到節(jié)點 j的最短路徑長度； pj是從 s到 j的最短路徑中 j點的前一節(jié)點； dij是節(jié)點 i到節(jié)點 j的距離。算法步驟如下： Step0：初始化 S = {s}； wi = dsi(i∈ NBs)；否則 = ∞(I ? NBs)； pi=s。 Step1：若 dsk = min dsj ，則 S = S ∪ { k}。 j∈ NBs Step2：修改 NBk S中的 wj值： wj = min { wj,wk +dkj }；若 wj值改變，則 pj = k。 j∈ NBs S Step3：選定 NBi S(i∈ S)中的 wj最小值，并將其劃歸到 s中： wk = min wj； S = S ∪ {k}；若 │s│= n；所有節(jié)點已標識，則算法終止， j∈∪ NBs–S i∈ S 否則，轉(zhuǎn)到 Step2． 圖 G7，對 G7分別用 Dijkstra算法和優(yōu)化了的 Dijkstra算法進行求解，則可得從 v1到其余各節(jié)點的最短路徑。 17 圖 非負權值圖 經(jīng)典 Dijkstra算法求解過程： Step0：初始化 S = (v1)， w1 = 0， T = (v2,v4, v3,v5, v6,v7)； Step1： w4 = d14 = mind1j = 2（ d12 = d14，任選其一，本文選 v4）， S = (v1,v4)， T = j∈ T (v2,v3,v5,v6,v7)； Step2： T = (v2,v3,v5,v6,v7) w2 = min{w2， w4 + d42}= min{2， 4}= 2， w3 = min{w3， w4 + d43}= min{5,5} = 5 2 = w2， w5 = min{w5， w4 + d45} = {∞， 3} = 3 2 = w2， w6 = min{w6， w4 + d46} = ∞， () w7 = min{w7， w4 + d47} = ∞，