[發(fā)明專利]一種基于方向?qū)?yōu)的啟發(fā)式最短路徑搜索方法

無效

• 申請(qǐng)?zhí)枺?/td>: 201310317540.8
• 申請(qǐng)日: 2013-07-24
• 公開（公告）號(hào): CN103425753A
• 公開（公告）日: 2013-12-04
• 發(fā)明（設(shè)計(jì)）人: 張豐;杜震洪;劉仁義;房佳;徐聰
• 申請(qǐng)（專利權(quán)）人: 浙江大學(xué)
• 主分類號(hào): G06F17/30
• 分類號(hào): G06F17/30
• 代理公司: 杭州求是專利事務(wù)所有限公司 33200
• 代理人: 張法高

技術(shù)領(lǐng)域

本發(fā)明涉及道路搜索方法，尤其涉及一種基于方向?qū)?yōu)的啟發(fā)式最短路徑搜索方法。

背景技術(shù)

最短路徑問題一直是各類學(xué)科研究的熱點(diǎn)問題，被應(yīng)用于城市規(guī)劃、交通運(yùn)輸、應(yīng)急管理等領(lǐng)域。研究最佳路線問題通常將城市道路網(wǎng)抽象為圖論意義下的網(wǎng)絡(luò)問題,問題的核心就變成了網(wǎng)絡(luò)圖中的最短路徑問題。在網(wǎng)絡(luò)模型中，尋找兩節(jié)點(diǎn)間阻礙最小的路徑；在時(shí)間模型中，計(jì)算兩節(jié)點(diǎn)間用時(shí)最少的路徑；在經(jīng)濟(jì)模型中，尋找該事件的最低消耗方法；這些模型中的關(guān)鍵方法都是最短路徑方法。同時(shí)，該問題也是GIS網(wǎng)絡(luò)分析中的一個(gè)基本問題。我們可以利用GIS技術(shù)，將在交通網(wǎng)絡(luò)分析中的最短路徑問題的研究轉(zhuǎn)化為在矢量地圖中求解最短路徑方法的研究。

現(xiàn)有的最短路徑的基本方法可分為:廣度優(yōu)先搜索法和深度優(yōu)先搜索法。廣度優(yōu)先搜索法的典型方法為Dijkstra方法,它是目前GIS應(yīng)用領(lǐng)域用于求解最短路徑問題的首選方法，同時(shí)也是經(jīng)典方法，其優(yōu)點(diǎn)在于能夠求得初始點(diǎn)到目標(biāo)點(diǎn)之間的所有最短路徑。這種方法在解決單對(duì)頂點(diǎn)之間的最短路徑時(shí)會(huì)產(chǎn)生數(shù)據(jù)冗余，因此不適合應(yīng)用于實(shí)際的求解過程中。目前廣泛被采納的優(yōu)化方法有改進(jìn)的A*方法、K則最優(yōu)路徑方法和最短路徑的蟻群方法等。其中A*方法是人工智能中一種典型的啟發(fā)式搜索方法，也是一種最優(yōu)優(yōu)先搜索方法，該方法在節(jié)點(diǎn)擴(kuò)展過程中使用了啟發(fā)信息，使得方法的搜索方向智能地趨向目標(biāo)節(jié)點(diǎn),從而很大程度上提高了搜索效率。而深度優(yōu)先搜索法還未有普遍認(rèn)可的典型方法。由于其盲目性，導(dǎo)致目前為止利用其對(duì)最短路徑求解的相關(guān)研究較少，但是在道路交通路徑搜索中，深度優(yōu)先搜索法其優(yōu)越性的一面。該方法不僅能夠計(jì)算出最短路徑，同時(shí)可以得到多個(gè)備選優(yōu)化路徑形成最短路徑組，最大程度地滿足用戶對(duì)不同路徑的選擇需求。

王杰臣等基于一種被其稱為圖的節(jié)點(diǎn)弧段聯(lián)合結(jié)構(gòu)表示法，避開采用大規(guī)模數(shù)組，提出了利用深度優(yōu)先原則來計(jì)算最短路徑的方法，從而節(jié)約了存儲(chǔ)空間、提高了運(yùn)算速度，但文章并沒有對(duì)深度優(yōu)先方法本身進(jìn)行改進(jìn)。莊明在深度優(yōu)先搜索法的基礎(chǔ)上,提出了在搜索過程中采用標(biāo)記距離的方法,利用預(yù)先對(duì)路的判斷條件,解決了避免進(jìn)入循環(huán)圈，和不必要的重復(fù)搜索問題,實(shí)現(xiàn)了在含障礙網(wǎng)絡(luò)的單源最短距離求解問題，但該方法需要事先人為地進(jìn)行控制優(yōu)化，要求操作人員對(duì)搜索路網(wǎng)有一定熟悉程度。張連蓬等則是提出一種方向?qū)?yōu)的快速搜索方法，從而提高搜索到最優(yōu)路徑的速度，但該方法依舊需要遍歷整個(gè)節(jié)點(diǎn)網(wǎng)絡(luò)，沒有提高整體搜索速度，尤其對(duì)于具有大量節(jié)點(diǎn)的交通網(wǎng)絡(luò)，必然產(chǎn)生冗余。

發(fā)明內(nèi)容

本發(fā)明的目的是克服現(xiàn)有技術(shù)的不足，提供一種基于方向?qū)?yōu)的啟發(fā)式最短路徑搜索方法。

基于方向?qū)?yōu)的啟發(fā)式最短路徑搜索方法的步驟如下：

1）確定路徑搜索的道路網(wǎng)信息，包括每個(gè)道路節(jié)點(diǎn)的坐標(biāo)信息、道路的長度和道路兩端節(jié)點(diǎn)信息，然后在道路網(wǎng)中選擇出發(fā)節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)，進(jìn)行最短路徑的搜索；

2）將所有節(jié)點(diǎn)狀態(tài)初始化，將道路網(wǎng)所有的節(jié)點(diǎn)狀態(tài)設(shè)置為空，即標(biāo)志為未搜索狀態(tài)，存儲(chǔ)于原始集合中，并將步驟1）中確定的出發(fā)節(jié)點(diǎn)取出，放入開放集合，即作為當(dāng)前正在搜索的當(dāng)前節(jié)點(diǎn)Si；

3）搜索道路網(wǎng)中與當(dāng)前節(jié)點(diǎn)Si相連的節(jié)點(diǎn)，根據(jù)方向?qū)?yōu)原則，排除不滿足方向?qū)?yōu)搜索條件的節(jié)點(diǎn)，同時(shí)排除那些關(guān)閉集合中父節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)Si,即已被擴(kuò)展過的節(jié)點(diǎn)，從而剩下的即為當(dāng)前節(jié)點(diǎn)Si的可擴(kuò)展節(jié)點(diǎn)；

4）更新可擴(kuò)展節(jié)點(diǎn)的F值，F(xiàn)值是以可擴(kuò)展節(jié)點(diǎn)為中間點(diǎn)的最短路徑估算值，并將可擴(kuò)展節(jié)點(diǎn)的父節(jié)點(diǎn)更新為當(dāng)前節(jié)點(diǎn)Si，然后將存在于原始集合中的可擴(kuò)展節(jié)點(diǎn)放入臨時(shí)表；

5）對(duì)臨時(shí)表進(jìn)行排序，將具有最小F值且可擴(kuò)展節(jié)點(diǎn)的父節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)Si的點(diǎn)放入開放集合，并將可擴(kuò)展節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)Si，并重復(fù)步驟3）～步驟5）；若不存在滿足條件的可擴(kuò)展節(jié)點(diǎn)，判斷當(dāng)前節(jié)點(diǎn)Si是否為原始節(jié)點(diǎn)，若不是，則將當(dāng)前節(jié)點(diǎn)Si放入關(guān)閉集合中，選擇當(dāng)前節(jié)點(diǎn)Si的父節(jié)點(diǎn)作為當(dāng)前點(diǎn)Si，重復(fù)步驟3）～步驟5）；若為原始節(jié)點(diǎn)，進(jìn)入步驟6）；

6）道路節(jié)點(diǎn)搜索完畢后，根據(jù)目標(biāo)節(jié)點(diǎn)的父節(jié)點(diǎn)，層層回退至初始節(jié)點(diǎn)，該路徑即為最短路徑。