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

梁 溪

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

0 引言

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

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

1 經(jīng)典Dijkstra算法

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

經(jīng)典Dijkstra算法可描述如下：

（2）T←N；

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

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

（6）T←T={k}，轉(zhuǎn)到步驟（3）。

2 改進(jìn)Dijkstra算法

2.1 存儲結(jié)構(gòu)的優(yōu)化

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

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

用C#語言描述鄰接表存儲結(jié)構(gòu)：

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

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

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

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

2.3 雙向查找規(guī)則

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

3 實驗結(jié)果及分析

本文將改進(jìn)Dijkstra算法進(jìn)行試驗驗證，試驗數(shù)據(jù)取自于市區(qū)地圖數(shù)據(jù)，經(jīng)過處理后得到符合項目要求的路網(wǎng)數(shù)據(jù)。其中節(jié)點數(shù)為3187，路段數(shù)為4515。試驗得到傳統(tǒng)Dijkstra算法和優(yōu)化Dijkstra算法的搜索結(jié)果比較如表1所示。根據(jù)源點和終點的不同，表1列出2組數(shù)據(jù)。

表1 實驗對照表

4 結(jié)論

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

[1]唐文武,施曉東,朱大奎.GIS中使用改進(jìn)的Dijkstra算法實現(xiàn)最短路徑的計算[J].中國圖象圖形學(xué)報,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].河南機(jī)電高等?？茖W(xué)校學(xué)報,2006,14( 5):30～31.

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

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

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

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

[8]許進(jìn),張雷.DNA計算機(jī)原理、進(jìn)展及難點(Ⅰ):生物計算系統(tǒng)及其在圖論中的應(yīng)用[J].計算機(jī)學(xué)報,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)絡(luò)中的應(yīng)用[ J].吉林工業(yè)大學(xué)學(xué)報, 2006,36(1):123-127.