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

無效

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

1.一種基于方向?qū)?yōu)的啟發(fā)式最短路徑搜索方法，其特征在于它的步驟如下：

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

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

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

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

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

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

2.根據(jù)權(quán)利要求1所述的一種基于方向?qū)?yōu)的啟發(fā)式最短路徑搜索方法，其特征在于所述的步驟4）為：獲取當前節(jié)點Si的每個可擴展節(jié)點對應(yīng)的F值，F(xiàn)值是從起始節(jié)點出發(fā)，經(jīng)過當前節(jié)點Si和該擴展點,到達目標節(jié)點的估算值，對于原始集合中的可擴展節(jié)點，能直接更新F值和賦值可擴展節(jié)點的父節(jié)點為當前節(jié)點Si，并放入臨時集合中，用來篩選下一搜索節(jié)點；對于關(guān)閉表中的可擴展節(jié)點，需要比較之前的F值和現(xiàn)在的F值大小，若現(xiàn)在的路徑花銷較小，則更新原有的F值，將關(guān)閉表中的可擴展節(jié)點的父節(jié)點賦值為當前節(jié)點Si，同時對關(guān)閉表中的可擴展節(jié)點的子節(jié)點采用級聯(lián)更新。

3.根據(jù)權(quán)利要求1所述的一種基于方向?qū)?yōu)的啟發(fā)式最短路徑搜索方法，其特征在于所述的步驟5）為：判斷臨時表中是否存在父節(jié)點為當前節(jié)點Si的節(jié)點，若存在，將具有最小F值的節(jié)點取出，作為當前節(jié)點Si,并重復(fù)步驟3）～步驟5）；若不存在，說明當前節(jié)點Si的所有節(jié)點都被搜索過，則需要判讀當前節(jié)點Si是否為初始節(jié)點，若是，則說明所有從初始節(jié)點出發(fā)的所有可擴展節(jié)點都已搜索完畢，循環(huán)結(jié)束；若不是，則重新回退到當前節(jié)點Si的父節(jié)點，進行搜索，即將當前節(jié)點Si的父節(jié)點作為當前節(jié)點Si,?并重復(fù)步驟3）～步驟5）。