滅火救援最優路徑算法探究

梁 溪

（海南省公安消防總隊司令部信息通信處,570100）

0 引言

隨著我國經濟以及城市化建設的快速發展，我國城市人口、財富、生產、建筑越來越趨于集中化，火災的發生極容易產生巨大的經濟損失以及人員傷亡。現代城市消防滅火救援系統中的一項重要任務就是決定最優的消防出警路線，所謂最優出警路線即消防車能在火災事故發生時，在最短的時間內達到火災現場進行滅火救援行為。

目前，最短路徑算法發展已經趨于完善，其中有十幾種最短路徑算法被國內外學者普遍研究，其中包括迪杰斯特拉Dijkstra算法、啟發式A* 算法、動態規劃方法、神經網絡、蟻群算法、遺傳算法、進化算法以及DNA算法等。本文在深入研究了Dijkstra算法的基礎上，提出了一種新型的改進Dijkstra算法。

1 經典Dijkstra算法

1995年，荷蘭數學家E.W.Dijkstra首次提出了Dijkstra算法，它是目前在求解最短路徑問題上理論最完善、應用最廣泛的一種經典算法。

經典Dijkstra算法可描述如下：

（2）T←N；

（3）從T中選取具有最小權的結點k，d(k)=min[d(j),j∈T]；S(k)=permanently labeled；

（4）如果得到k=t，表示算法結束 ；

（6）T←T={k}，轉到步驟（3）。

2 改進Dijkstra算法

2.1 存儲結構的優化

在實際交通路網中，道路大多數為單行車道，道路具有方向限制，所以我們應該使用有向圖來表示交通路網。而且，交通路網中每個道路結點所連接的路段一般為3-5個，屬于稀疏圖。此時，更適合使用鄰接表存儲結構，該存儲結構具有節省空間、易于實現且易于擴充更新數據域等優點，且更加能全面真實的反映路網特征方面。

有向圖中的結點Node類可描述道路交叉口，有向圖中的弧Edge類可描述路段。所有路段的距離即Edge的長度可以用Mapinfo軟件中自帶的測距函數來實現測距功能。其中，每個節點包含以下信息：結點編號ID、結點的出邊表edge_list、longitude、latitude等。而每條弧要包含以下信息：弧頭ID（Star_Node_ID）、弧尾 ID（End_Node_ID）以及權值 Weight。

用C#語言描述鄰接表存儲結構：

2.2 搜索區域的限定

減小算法的搜索規模是提高算法效率的一項關鍵技術。Nordbeck根據交通路網的特性提出了基于橢圓限制的最優路徑算法，設交通路網中起點為S，終點為D，中間的某個節點為N，N與S之間距離為 ，N與D之間距離為 ，則限制條件為。此時，則形成了一個橢圓形的搜索區域。該方法雖然減少了搜索結點，但并沒有提高算法的效率，非線性運算增加了算法的運算量。王曉麗提出了基于平行四邊形限制的最優路徑算法，這種方法省去了非線性計算，但是仍然在計算量上有很大的增加，因為橢圓變成多邊形要經過坐標軸旋轉和平移等過程。

本文提出了一種簡單易于實現的區域搜索限制模型，設給定起點為S，終點為D，則區域搜索限制模型可由公式(1)描述：

D(i ,j)為Mapinfo中自帶的測距函數，表示的是節點i與點 j之間的幾何距離，是由結點的地理坐標直接計算得出。k為區域控制參數，k越大，搜索區域越大，搜索出最優路徑的幾率也就越大，計算量也越大，反之則得到最優路徑的幾率就越小，計算量越小。所以，選擇一個合適的k值顯得至關重要，既可以避免搜索區域過大結點過多，又可以搜索到最優路徑。

2.3 雙向查找規則

為了得到更快速的搜索過程，本文在考慮規則的基礎上，提出了雙向查找規則應用于最優路徑搜索系統中。雙向查找規則的基本思想是從兩個端點同時開始搜索，相遇后即停止搜索，這樣，搜索速度較之單向搜索快了一倍，路徑減少了一半。設 D(S,i)、D(N,i)分別為起點S和終點N到結點i的最短路徑的長度，P(S,i)，P(N,i)分別表示從 S,N 到結點i的前一結點的最短路徑的長度。每個結點都存在一個標號｛D(S,i),P(S,j ),D(N,i),P(N,i )｝。

3 實驗結果及分析

本文將改進Dijkstra算法進行試驗驗證，試驗數據取自于市區地圖數據，經過處理后得到符合項目要求的路網數據。其中節點數為3187，路段數為4515。試驗得到傳統Dijkstra算法和優化Dijkstra算法的搜索結果比較如表1所示。根據源點和終點的不同，表1列出2組數據。

表1 實驗對照表

4 結論

本文在基于傳統的Dijkstra算法的基礎上，提出了三個方面的優化策略，分別是搜索區域的限定、存儲結構的優化以及雙向查找規則。改進后的Dijkstra算法具有節省存儲空間以及提高算法運行效率的優點。本文提出的優化算法是針對算法本身的，對于實際的消防出警有一定的理論參考，但是在實際應用中，實時的交通信息對最優路徑的選擇存在很大的影響。隨著全球定位系統和路徑導航系統的不斷發展，研究更加符合實時交通的消防滅火救援最優路徑有著重大的現實意義。

[1]唐文武,施曉東,朱大奎.GIS中使用改進的Dijkstra算法實現最短路徑的計算[J].中國圖象圖形學報,2000,5(12): 1019～1023.

[2]Amit.Amit ’s notes about path-finding [Z].http://www-cs-students.stanford.edu/～amitp/gameprog.html.

[3]梁娟,郭軍麗,魏勇.利用動態規劃算法求解最短路徑[J].河南機電高等專科學校學報,2006,14( 5):30～31.

[4]紀其進.一種基于脈沖耦合神經網絡的最短路徑算法[ J].小型微型計算機系統, 2005, 26(5): 826～829.

[5]黃貴玲,高西全, 靳松杰,談飛洋.基于蟻群算法的最短路徑問題的研究和應用[J].計算機工程與應用,2007,43(13) :233～235.

[6]孫霞,黃席樾,楊祖元,向長城.基于改進遺傳算法的城市交通動態最優路徑求解[J].計算機工程與應用,2007, 43(30) :245～248.

[7]馮琦, 周德云.基于微分進化算法的時間最優路徑規劃[J].計算機工程與應用, 2005, 12: 74～75,222.

[8]許進,張雷.DNA計算機原理、進展及難點(Ⅰ):生物計算系統及其在圖論中的應用[J].計算機學報,2003,26(1): 1～11.

[9]NORDBECKS, RYSTEDT B.Computer Cartography Shortest Route Programs[M].Sweden:The Royal University of Lund,1969.

[10]王曉麗, 楊兆升,呂旭濤,等.平行四邊形限制最短路徑算法及其在交通網絡中的應用[ J].吉林工業大學學報, 2006,36(1):123-127.