李克文,朱虹吉

(中國(guó)石油大學(xué) 計(jì)算機(jī)與通信工程學(xué)院,青島 266580)

大型油庫(kù)消防救援尋路算法改進(jìn)①

李克文,朱虹吉

(中國(guó)石油大學(xué) 計(jì)算機(jī)與通信工程學(xué)院,青島 266580)

大型油庫(kù)區(qū)的地形不同于城市、山地等復(fù)雜的地形,雖然范圍較大,但是油庫(kù)區(qū)地形十分規(guī)整,油罐等建筑排列整齊,且在儲(chǔ)油罐區(qū)的道路是筆直暢通的.根據(jù)這些特點(diǎn),將標(biāo)準(zhǔn)的A*尋路算法進(jìn)行改進(jìn).一方面,根據(jù)油庫(kù)地形結(jié)構(gòu)簡(jiǎn)單,搜索節(jié)點(diǎn)相對(duì)少的特點(diǎn),對(duì)A*算法中搜索Open表中節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)進(jìn)行改進(jìn),采用排序算法提高了搜索效率;另一方面,根據(jù)儲(chǔ)油罐區(qū)道路筆直暢通的特點(diǎn),將道路分為有障礙路段和無(wú)障礙路段,分而治之,提高整體的尋路效率.實(shí)驗(yàn)證明,將兩種改進(jìn)方法進(jìn)行結(jié)合,尋路時(shí)間明顯縮短,平均搜索效率提高6.86%.

油庫(kù)火災(zāi);人工智能;A*算法;快速排序;分層尋路

強(qiáng)勁的工業(yè)增長(zhǎng)和不斷提升的國(guó)內(nèi)水平近一步加大了中國(guó)對(duì)能源的需求,而在這些能源中,石油扮演著不可或缺的重要角色.油庫(kù)區(qū)則是最重要的生產(chǎn)和儲(chǔ)備場(chǎng)所,是危險(xiǎn)物質(zhì)的集中地,火災(zāi)事故則是油庫(kù)安全問(wèn)題的重中之重.一旦發(fā)生油氣泄漏,甚至是起火爆炸,其造成的危害不可估量.所以,當(dāng)事故發(fā)生時(shí),救援人員、車(chē)輛如何能以最快最有效最合理的方式進(jìn)入到事故現(xiàn)場(chǎng)就成了應(yīng)急救援中十分關(guān)鍵的一個(gè)環(huán)節(jié).在三維模擬演練系統(tǒng)中,電腦控制的角色能否最快找到最佳路徑成為了能否完成滅火救援任務(wù)的關(guān)鍵.當(dāng)下主流的最短路徑搜索算法主要定位在貪心算法上,研究更加有效的數(shù)據(jù)結(jié)構(gòu)和搜索算法,從而降低算法的時(shí)間和復(fù)雜度.貪心算法的主要代表是Dijkstra算法,其思想是以起始點(diǎn)為中心向外層層擴(kuò)展,直到擴(kuò)展到終點(diǎn)為止.Dijkstra算法雖然能夠算出路徑的最優(yōu)解,但是由于其建立計(jì)算節(jié)點(diǎn)過(guò)多,所以效率很低.A*算法則是當(dāng)下游戲中非玩家控制角色(NPC)在地圖中智能尋路應(yīng)用最廣泛的算法.二者相比: Dijkstra算法計(jì)算原點(diǎn)到其他所有點(diǎn)的最短路徑長(zhǎng)度,而A*算法目標(biāo)在于點(diǎn)與點(diǎn)的最短路徑;其次Dijkstra算法更多建立在抽象的圖論層面,A*算法則可以更有效的應(yīng)用在實(shí)際地圖的尋路中;除此而外,Dijstra算法的本質(zhì)是廣度優(yōu)先搜索,所以空間復(fù)雜度和時(shí)間復(fù)雜度都比較高,而A*是通過(guò)計(jì)算到原點(diǎn)的代價(jià)和目標(biāo)點(diǎn)的估計(jì)代價(jià),是一種啟發(fā)式算法.A*算法引入的啟發(fā)信息提高了搜索的效率.

目前的A*尋路算法存在一些不足之處:當(dāng)搜索地形復(fù)雜,搜索節(jié)點(diǎn)的數(shù)量會(huì)非常巨大,這樣就會(huì)降低A*算法的效率;另一方面,在搜索的地形中,部分道路是筆直且無(wú)障礙物的,如果此時(shí)繼續(xù)調(diào)用A*算法尋路,也會(huì)影響到整體的尋路效率.本文分析A*算法,針對(duì)大型油庫(kù)區(qū)的地形的特點(diǎn),結(jié)合前人所提出的方法,我們對(duì)A*算法提出改進(jìn),并在油庫(kù)火災(zāi)三維模擬演練系統(tǒng)中進(jìn)行驗(yàn)證.

1 A*算法

1.1 A*算法的基本原理

二十世紀(jì)六十年代,經(jīng)典的A*算法在P.E.Hart等人發(fā)表的一篇關(guān)于啟發(fā)式搜索算法的文章中被提出.到目前為止,A*算法是最有效的路徑尋優(yōu)算法,也是被人們應(yīng)用最為廣泛的人工智能尋路算法.

A*算法的基本思想:核心為一個(gè)估價(jià)函數(shù)F(n)= G(n)+H(n),其中F(n)代表當(dāng)前節(jié)點(diǎn)n的啟發(fā)函數(shù),其值為從起始節(jié)點(diǎn)經(jīng)過(guò)n節(jié)點(diǎn)到達(dá)終點(diǎn)的總代價(jià),G(n)是從起始節(jié)點(diǎn)到達(dá)當(dāng)前n節(jié)點(diǎn)的實(shí)際消耗代價(jià),H(n)則表示從當(dāng)前節(jié)點(diǎn)n到達(dá)終點(diǎn)的估計(jì)消耗代價(jià).由此函數(shù)能得到每個(gè)節(jié)點(diǎn)的代價(jià),通過(guò)該啟發(fā)函數(shù),在當(dāng)前節(jié)點(diǎn)計(jì)算下一步能到達(dá)節(jié)點(diǎn)的F值,通過(guò)搜索,找到具有最小估價(jià)值F的點(diǎn),然后繼續(xù)往下搜索.A*算法中有兩個(gè)表,Open表和Closed表,分別存放未擴(kuò)展節(jié)點(diǎn)和已擴(kuò)展的節(jié)點(diǎn).A*尋路算法的基本過(guò)程為:

第一步:把起始點(diǎn)加入到Open表中.

第二步:查找Open表:

如果Open表為空,則表示尋路失敗;尋找Open表中F值最低的節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn),并將其存入到Closed表中.

如果當(dāng)前點(diǎn)為目標(biāo)節(jié)點(diǎn),則尋路成功,轉(zhuǎn)到第四步.

第三步:對(duì)相鄰的每個(gè)節(jié)點(diǎn)進(jìn)行如下操作:

如果該節(jié)點(diǎn)不可通過(guò)或者已經(jīng)在Closed表中,放棄該節(jié)點(diǎn).

如果該節(jié)點(diǎn)不在Open表中,把它添加進(jìn)去,并記錄F,G和H值.

如果該節(jié)點(diǎn)已經(jīng)在Open表中,進(jìn)行F值的比較,選擇具有較小F值的節(jié)點(diǎn),并重新計(jì)算該節(jié)點(diǎn)的G值和F值.

如果相鄰節(jié)點(diǎn)搜索完畢,則轉(zhuǎn)向第二步;否則,轉(zhuǎn)向第三步.

第四步:保存路徑,根據(jù)Closed表中節(jié)點(diǎn)信息,進(jìn)行逆向提取,從而得到路徑.

經(jīng)典的A*算法中Open表采用保存當(dāng)前節(jié)點(diǎn)相鄰的可以作為下一個(gè)節(jié)點(diǎn)的節(jié)點(diǎn),也就是將要搜索的節(jié)點(diǎn);Closed表用來(lái)保存通過(guò)計(jì)算得出來(lái)的Open表中適合算法要求的節(jié)點(diǎn).

2 A*算法的改進(jìn)

2.1 對(duì)Open表搜索速度優(yōu)化

在標(biāo)準(zhǔn)的A*算法中,Open表中搜索具有最小F值的節(jié)點(diǎn)是路徑搜索過(guò)程中最緩慢的部分.特別是當(dāng)搜索的地形復(fù)雜時(shí),搜索節(jié)點(diǎn)的數(shù)量會(huì)大大增加,這時(shí)候進(jìn)行A*算法搜索,會(huì)反復(fù)搜索這個(gè)龐大的Open表,此時(shí)A*算法中搜索Open表的效率會(huì)明顯的下降,從而影響到整體的搜索效率.標(biāo)準(zhǔn)A*算法的Open表中節(jié)點(diǎn)通常是無(wú)序的,這樣就給搜索增加了難度.一個(gè)與搜索地形相匹配的存儲(chǔ)方式,可以提高搜索效率;不匹配的存儲(chǔ)方式,使得搜索效率降低,將嚴(yán)重影響路徑搜索的時(shí)間.

大型油庫(kù)區(qū)的地形通常情況下是十分規(guī)整的,油罐、廠房等建筑物排列整齊.網(wǎng)格化以后的油庫(kù)區(qū)地圖跟大部分復(fù)雜的游戲地圖比較,搜索節(jié)點(diǎn)較少.針對(duì)該特點(diǎn),本文對(duì)Open表中節(jié)點(diǎn)存儲(chǔ)方式進(jìn)行改進(jìn),根據(jù)表中F值的大小對(duì)節(jié)點(diǎn)進(jìn)行排序來(lái)提高搜索效率.比如,Open表中F值按照從小到大的順序進(jìn)行排列,每次想要找到最小的F值節(jié)點(diǎn),只要選取Open表中的第一個(gè)節(jié)點(diǎn)即可.目前,有很多的排序方法可以應(yīng)用到Open表的節(jié)點(diǎn)排序.

本文采用快速排序方法對(duì)Open表中節(jié)點(diǎn)進(jìn)行排序.通過(guò)一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分,其中一部分的所有數(shù)據(jù)都比另外一部分?jǐn)?shù)據(jù)要小,然后再按照此方法對(duì)這兩部分?jǐn)?shù)據(jù)進(jìn)行快速排序,整個(gè)排序過(guò)程可以遞歸進(jìn)行,以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列.對(duì)于A*算法中Open列表來(lái)說(shuō),從比較新元素的F值和列表中元素的F值開(kāi)始,如果新元素的F值較小,則讓新元素與1/4處的節(jié)點(diǎn)進(jìn)行比較;如果比1/4處節(jié)點(diǎn)的F值還小,那就和1/8處的F值進(jìn)行比較;以此類(lèi)推,不斷進(jìn)行折半比較,直到找到合適的位置,進(jìn)行插入.如果一開(kāi)始F值比中間節(jié)點(diǎn)的值大,則以同樣的方法向后比較.

從上述分析中可以看出,由于大型油庫(kù)區(qū)地形規(guī)整,建筑物排列整齊的特點(diǎn),大大降低了搜索節(jié)點(diǎn)的數(shù)量,不存在搜索節(jié)點(diǎn)過(guò)多,而導(dǎo)致搜索效率下降的情況,所以使用快速排序算法對(duì)Open列表進(jìn)行排序,可以有效地提高對(duì)Open列表的搜索速度.本文中我們將對(duì)此進(jìn)行實(shí)現(xiàn),并通過(guò)實(shí)驗(yàn)進(jìn)行證明其有效性.

2.2 油庫(kù)的儲(chǔ)油罐區(qū)分層尋路方法

大型油庫(kù)的儲(chǔ)油罐區(qū)地形的特點(diǎn):罐體周?chē)缆肥枪P直且無(wú)障礙的.如果此時(shí)繼續(xù)調(diào)用A*算法進(jìn)行路徑搜索然后再通過(guò)此路段,無(wú)疑會(huì)降低整體的尋路效率.故本文結(jié)合該特點(diǎn),提出改進(jìn):即對(duì)儲(chǔ)油罐區(qū)沒(méi)有障礙物且筆直的道路進(jìn)行標(biāo)記,我們稱(chēng)其為無(wú)礙路段,當(dāng)我們進(jìn)行路徑搜索,到達(dá)一個(gè)無(wú)礙路段時(shí),且要通過(guò)此無(wú)礙路段,此時(shí)我們放棄調(diào)用A*尋路算法,讓尋路者直接通過(guò)該區(qū)域,到達(dá)此無(wú)礙路段的另一個(gè)端點(diǎn),繼續(xù)尋路;當(dāng)尋路者到達(dá)障礙物附近區(qū)域時(shí),為有礙路段,我們繼續(xù)調(diào)用A*算法尋找最優(yōu)路徑,從而構(gòu)成無(wú)礙路段和有礙路段分而治之的尋路思想,提高路徑尋路的效率.圖1為該分層算法的流程圖.

圖1 分層尋路算法流程圖

3 改進(jìn)尋路算法在油庫(kù)火災(zāi)三維模擬演練系統(tǒng)中的應(yīng)用

3.1 算法在系統(tǒng)中的實(shí)現(xiàn)

本文以C++為編程語(yǔ)言,基于vs2010程序開(kāi)發(fā)平臺(tái),引用第三方API函數(shù)庫(kù)對(duì)三維油庫(kù)火災(zāi)模擬演練系統(tǒng)進(jìn)行了實(shí)現(xiàn).在多人協(xié)同模擬演練模塊,我們對(duì)本文所提出的改進(jìn)A*算法進(jìn)行了應(yīng)用.本系統(tǒng)中的A*算法的估價(jià)函數(shù)H,我們采用曼哈頓距離進(jìn)行估價(jià),即:

其中,X代表目標(biāo)節(jié)點(diǎn)在地圖中的橫坐標(biāo),Y代表目標(biāo)節(jié)點(diǎn)在地圖中的縱坐標(biāo);X’代表當(dāng)前節(jié)點(diǎn)在地圖中的橫坐標(biāo),Y‘代表當(dāng)前節(jié)點(diǎn)在地圖中的縱坐標(biāo).圖2為系統(tǒng)中油庫(kù)區(qū)的俯視圖;圖3為網(wǎng)格化后的地圖,其中黃色區(qū)域?yàn)檎系K物區(qū)域不能穿過(guò),綠色為起始點(diǎn),紅色為目標(biāo)節(jié)點(diǎn),藍(lán)色最優(yōu)路徑.在圖3路徑的基礎(chǔ)上,假設(shè)部分路段在施工,禁止通行的情況下,在圖4中我們以黑色表示,重新搜索后的路徑為圖4中所示.

圖2 油庫(kù)區(qū)俯視圖

圖3 網(wǎng)格化的油庫(kù)區(qū)地圖

3.2 改進(jìn)尋路算法與標(biāo)準(zhǔn)A*算法的對(duì)比實(shí)驗(yàn)

本節(jié)內(nèi)容將三種算法:標(biāo)準(zhǔn)A*算法、采用快速排序優(yōu)化Open表后的A*算法、采用分層搜索A*算法以及綜合了兩次改進(jìn)后的尋路算法,比較這幾種算法的搜索時(shí)間.網(wǎng)格化以后的油庫(kù)區(qū)地圖為34*18的網(wǎng)格圖形.實(shí)驗(yàn)中,我們選擇10組不同的起始點(diǎn)與終點(diǎn)作為實(shí)驗(yàn)路徑,路徑長(zhǎng)度逐漸增長(zhǎng),每組路徑我們進(jìn)行10次運(yùn)算,記錄搜索時(shí)間并取其平均值,通過(guò)比較搜索時(shí)間來(lái)證明改進(jìn)后的尋路算法提高了搜索效率.其中一次搜索結(jié)果如圖5,輸出了本次搜索的最優(yōu)路徑所經(jīng)過(guò)的節(jié)點(diǎn)坐標(biāo)以及搜索時(shí)間.圖5中:0為通路,1為由起始點(diǎn)搜索后得到的路徑,2為終點(diǎn),3為障礙物.

圖4 設(shè)置障礙物后的新路徑

圖5 搜索的路徑和時(shí)間數(shù)據(jù)

實(shí)驗(yàn)一:在系統(tǒng)中調(diào)用標(biāo)準(zhǔn)A*算法來(lái)進(jìn)行實(shí)驗(yàn),記錄其搜索時(shí)間,并算出每組數(shù)據(jù)的平均值.

實(shí)驗(yàn)二:由于標(biāo)準(zhǔn)A*算法中,影響搜索速度比較大的因素就是對(duì)Open表中F值的查找,本文采用了快速排序?qū)pen表進(jìn)行優(yōu)化,使Open表中的節(jié)點(diǎn)按照F值從一開(kāi)始就由小到大的順序進(jìn)行排列.本部分我們用優(yōu)化Open表的方法進(jìn)行實(shí)驗(yàn),與實(shí)驗(yàn)一采用相同10組路徑進(jìn)行實(shí)驗(yàn),記錄時(shí)間并算出每組數(shù)據(jù)平均值.實(shí)驗(yàn)三:針對(duì)油庫(kù)區(qū)儲(chǔ)油罐區(qū)道路筆直且無(wú)障礙的特點(diǎn),提出分層搜索的改進(jìn)方法,將道路分為無(wú)礙路段和有礙路段,當(dāng)尋路體到達(dá)該路段,且需要通過(guò)該路段時(shí),我們放棄調(diào)用A*算法,使其直接通過(guò).如圖6,綠色路段為無(wú)礙路段.本部分用分層搜索算法進(jìn)行實(shí)驗(yàn),與實(shí)驗(yàn)一采用相同10組路徑,記錄時(shí)間并算出每組數(shù)據(jù)平均值.

圖6 分層設(shè)計(jì)后的地形圖

實(shí)驗(yàn)四:本部分我們綜合上述兩種改進(jìn)方法,即在對(duì)Open表進(jìn)行快速排序的基礎(chǔ)上進(jìn)行分層路徑搜索,對(duì)比標(biāo)準(zhǔn)A*算法的搜索時(shí)間,實(shí)驗(yàn)方法同上.

通過(guò)四組實(shí)驗(yàn),得到的搜索時(shí)間表1,對(duì)比折線圖7.

通過(guò)實(shí)驗(yàn)數(shù)據(jù),我們得出以下結(jié)論:

① 實(shí)驗(yàn)過(guò)程中,通過(guò)分析實(shí)驗(yàn)數(shù)據(jù),結(jié)果表明在起始點(diǎn)和終點(diǎn)相同的情況下,如圖3、圖4,在地形相對(duì)復(fù)雜的圖4中,搜索得到的路徑長(zhǎng)度增加,搜索時(shí)間也隨之增加,由此可以分析得出,隨著地形越復(fù)雜程度的增加,尋路算法的搜索效率會(huì)降低.

② 對(duì)Open表進(jìn)行排序后的A*算法搜索時(shí)間相對(duì)于標(biāo)準(zhǔn)A*算法有了提高.分析其原因,我們對(duì)標(biāo)準(zhǔn)A*算法中無(wú)序的Open進(jìn)行排序,F值最小的節(jié)點(diǎn)即為Open表的第一個(gè)節(jié)點(diǎn),從而減少了對(duì)Open表搜索的花費(fèi).

③ 采用分層搜索后,明顯提高了路徑搜索的速度.分析其原因,由于在無(wú)礙路段上,我們放棄使用A*算法進(jìn)行搜索,故減少了搜索的節(jié)點(diǎn)數(shù)量,從而提高了搜索的效率,有效減少了路徑搜索時(shí)間.

④ 我們從實(shí)驗(yàn)數(shù)據(jù)中可以看到綜合了兩次改進(jìn)的尋路算法,路徑搜索時(shí)間明顯縮短,通過(guò)數(shù)據(jù)計(jì)算得出采用綜合改進(jìn)后的尋路算法進(jìn)行尋路,最優(yōu)路徑搜索效率平均提高6.86%.

表1 各組實(shí)驗(yàn)平均搜索時(shí)間對(duì)比

圖7 各組實(shí)驗(yàn)搜索時(shí)間對(duì)比折線圖

4 總結(jié)

A*尋路算法是當(dāng)下應(yīng)用最廣泛的智能尋路算法,但是當(dāng)搜索地形復(fù)雜,隨著搜索節(jié)點(diǎn)數(shù)量的增加,A*算法的搜索效率將受到影響,其中,搜索最緩慢的部分是對(duì)Open表中無(wú)序節(jié)點(diǎn)的搜索.本文結(jié)合大型油庫(kù)區(qū)地形規(guī)整,結(jié)構(gòu)簡(jiǎn)單的搜索節(jié)點(diǎn)相對(duì)少特點(diǎn),對(duì)Open表進(jìn)行了排序,優(yōu)化了節(jié)點(diǎn)的存儲(chǔ)方式,提高了Open表的查找效率;另外,本文針對(duì)油庫(kù)的儲(chǔ)油罐區(qū)道路筆直無(wú)障礙的特點(diǎn)提出了分層搜索的思想,進(jìn)一步提高了整體的搜索效率.目前對(duì)A*算法的改進(jìn)主要集中在對(duì)A*算法搜索節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)和估價(jià)函數(shù)上,本文結(jié)合了實(shí)際搜索地形特點(diǎn),不同路段影響搜索效率因素不同,分別進(jìn)行了改進(jìn),將改進(jìn)辦法相結(jié)合后應(yīng)用到整體的路徑搜索中,有效的提高了最短搜索效率.

筆者基于vs2010開(kāi)發(fā)平臺(tái),用C++作為程序開(kāi)發(fā)語(yǔ)言實(shí)現(xiàn)了油庫(kù)火災(zāi)三維模擬演練系統(tǒng),并在系統(tǒng)中的多人協(xié)同模擬演練模塊中對(duì)本文所提出的改進(jìn)算法進(jìn)行了實(shí)現(xiàn).結(jié)果表明,改進(jìn)后的尋路算法效果明顯,提高了救援隊(duì)伍尋路運(yùn)算的速度,且路徑真實(shí)有效,搜索效率平均提高6.86%,為本系統(tǒng)提供了更加真實(shí)的訓(xùn)練效果,使油庫(kù)消防救援尋路效率得到了有效的改善.

1張海濤,程蔭杭.基于A*算法的全局路徑搜索.微計(jì)算機(jī)信息,2007,204(17):238–239,308.

2 Cao W.Application of an improved A*algorithm in route planning.Proc.of WRI Global Congress on Intelligent Systems(GCIS’09).2009.253–257.

3 Qi MJ,Sun HN,Gao GF.Research on an improved algorithm for shortest path searching in urban traffic based on GIS. Proc.of Electrical and Control Engineering International Conference.2011.1184–1187.

4 Eriksson G,Kitok A.Automatic loading and dumping using vehicle guidance in a Swedish mine.Proc.of the First InternationalSymposium on MineMechanization and Automation.1991,6.15-33–15-44.

5賈慶軒,陳鋼,孫漢旭,鄭雙奇.基于A～*算法的空間機(jī)械臂避障路徑規(guī)劃.機(jī)械工程學(xué)報(bào),2010,46(13):109–115.

6劉浩,鮑遠(yuǎn)律.A*算法在矢量地圖最優(yōu)路徑搜索中的應(yīng)用.計(jì)算機(jī)仿真,2008,(4):253–257.

7李志建,鄭新奇,王淑晴,楊鑫.改進(jìn)A～*算法及其在GIS路徑搜索中的應(yīng)用.系統(tǒng)仿真學(xué)報(bào),2009,21(10):3116–3119.

8熊壬浩,劉羽.A*算法的改進(jìn)及并行化.計(jì)算機(jī)應(yīng)用, 2015,35(7):1843–1848.

9顧青,豆風(fēng)鉛,馬飛.基于改進(jìn)A*算法的電動(dòng)車(chē)能耗最優(yōu)路徑規(guī)劃.農(nóng)業(yè)機(jī)械學(xué)報(bào),2015,46(12):316–322.

10張仁平,周慶忠,熊偉,王紅旗.A～*算法改進(jìn)算法及其應(yīng)用.計(jì)算機(jī)系統(tǒng)應(yīng)用,2009,18(9):98–100,107.

11陳剛,付少鋒,周利華.A～*算法在游戲地圖尋徑中的幾種改進(jìn)策略研究.科學(xué)技術(shù)與工程,2007,7(15):3731–3736.

12張前哨.基于A*算法的地圖尋徑的研究[碩士學(xué)位論文].武漢:武漢科技大學(xué),2005.

13馬飛,楊皞屾,顧青,孟宇.基于改進(jìn)A*算法的地下無(wú)人鏟運(yùn)機(jī)導(dǎo)航路徑規(guī)劃.農(nóng)業(yè)機(jī)械學(xué)報(bào),2015,46(7):303–309.

14王殿君.基于改進(jìn)A～*算法的室內(nèi)移動(dòng)機(jī)器人路徑規(guī)劃.清華大學(xué)學(xué)報(bào)(自然科學(xué)版),2012,(8):1085–1089.

15張靜,萬(wàn)書(shū)亭,陳海宏.基于改進(jìn)路網(wǎng)分層和A～*算法的最優(yōu)路徑研究.華北電力大學(xué)學(xué)報(bào)(自然科學(xué)版),2012,39(5): 12–16.

16任波,周燾,于雷.基于改進(jìn)A～*算法的飛行器三維航跡規(guī)劃算法.系統(tǒng)工程與電子技術(shù),2008,30(2):324–326.

17高慶吉,于詠生,胡丹丹.基于改進(jìn)A*算法的可行性路徑搜索及優(yōu)化.中國(guó)民航學(xué)院學(xué)報(bào),2005,23(4):42–45.

18單偉,孟正大.基于改進(jìn)A～*算法的平滑路徑設(shè)計(jì).東南大學(xué)學(xué)報(bào)(自然科學(xué)版),2010,(S1):155–161.

19錢(qián)紅昇,葛文鋒,鐘鳴,葛銘.基于分層的改進(jìn)*算法在路徑規(guī)劃中的應(yīng)用.計(jì)算機(jī)工程與應(yīng)用,2014,50(7):225–229.

20周小鏡.基于改進(jìn)A*算法的游戲地圖尋徑的研究[碩士學(xué)位論文].重慶:西南大學(xué),2011.

Improved Pathfinding Algorithm for the Rescue of Large Oil File

LI Ke-Wen,ZHU Hong-Ji

(College of Computer and Communication Engineering,China University of Petroleum,Qingdao 266580,China)

The large oil depot map is different from city and mountainous region whose maps are complex.The map of large oil depot is very regular,oil tanks and other buildings arranged neatly and the roads of the oil tank area are straight. On the basis,the classic A*algorithm is improved in this paper.On the one hand,according to the characteristics that the map of oil depot is simple and the number of search nodes is relatively small,the data structure of the Open table in the A*algorithm is improved,to accelerate the search speed and the ranking algorithm is used to improve the search efficiency.On the other hand,because roads in the oil depot are straight,so we divide roads into two parts:roads with obstacles and barrier free roads,to improve the search efficiency.Experimental results show that,with the combination of the two improved methods,the time of searching roads is declined definitely by 6.86%.

oil depot fire;artificial intelligence;A*algorithm;quicksort;hierarchical road search

2016-08-08;收到修改稿時(shí)間:2016-10-10

10.15888/j.cnki.csa.005759