滅火救援最優(yōu)路徑算法探究

梁 溪

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

0 引言

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

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

1 經(jīng)典Dijkstra算法

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

經(jīng)典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}，轉(zhuǎn)到步驟（3）。

2 改進Dijkstra算法

2.1 存儲結構的優(yōu)化

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

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

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

2.2 搜索區(qū)域的限定

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

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

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

2.3 雙向查找規(guī)則

為了得到更快速的搜索過程，本文在考慮規(guī)則的基礎上，提出了雙向查找規(guī)則應用于最優(yōu)路徑搜索系統(tǒng)中。雙向查找規(guī)則的基本思想是從兩個端點同時開始搜索，相遇后即停止搜索，這樣，搜索速度較之單向搜索快了一倍，路徑減少了一半。設 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算法進行試驗驗證，試驗數(shù)據(jù)取自于市區(qū)地圖數(shù)據(jù)，經(jīng)過處理后得到符合項目要求的路網(wǎng)數(shù)據(jù)。其中節(jié)點數(shù)為3187，路段數(shù)為4515。試驗得到傳統(tǒng)Dijkstra算法和優(yōu)化Dijkstra算法的搜索結果比較如表1所示。根據(jù)源點和終點的不同，表1列出2組數(shù)據(jù)。

表1 實驗對照表

4 結論

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

[1]唐文武,施曉東,朱大奎.GIS中使用改進的Dijkstra算法實現(xiàn)最短路徑的計算[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]梁娟,郭軍麗,魏勇.利用動態(tài)規(guī)劃算法求解最短路徑[J].河南機電高等專科學校學報,2006,14( 5):30～31.

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

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

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

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

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

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

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