一種基於方向尋優的啟發式最短路徑搜索方法
2023-05-05 23:18:16
專利名稱：一種基於方向尋優的啟發式最短路徑搜索方法
技術領域：
本發明涉及道路搜索方法，尤其涉及一種基於方向尋優的啟發式最短路徑搜索方法。
背景技術：
最短路徑問題一直是各類學科研究的熱點問題，被應用於城市規劃、交通運輸、應急管理等領域。研究最佳路線問題通常將城市道路網抽象為圖論意義下的網絡問題，問題的核心就變成了網絡圖中的最短路徑問題。在網絡模型中，尋找兩節點間阻礙最小的路徑；在時間模型中，計算兩節點間用時最少的路徑；在經濟模型中，尋找該事件的最低消耗方法；這些模型中的關鍵方法都是最短路徑方法。同時，該問題也是GIS網絡分析中的一個基本問題。我們可以利用GIS技術，將在交通網絡分析中的最短路徑問題的研究轉化為在矢量地圖中求解最短路徑方法的研究。現有的最短路徑的基本方法可分為:廣度優先搜索法和深度優先搜索法。廣度優先搜索法的典型方法為Dijkstra方法，它是目前GIS應用領域用於求解最短路徑問題的首選方法，同時也是經典方法，其優點在於能夠求得初始點到目標點之間的所有最短路徑。這種方法在解決單對頂點之間的最短路徑時會產生數據冗餘，因此不適合應用於實際的求解過程中。目前廣泛被採納的優化方法有改進的A*方法、K則最優路徑方法和最短路徑的蟻群方法等。其中A*方法是人工智慧中一種典型的啟發式搜索方法，也是一種最優優先搜索方法，該方法在節點擴展過程中使用了啟發信息，使得方法的搜索方向智能地趨向目標節點，從而很大程度上提高了搜索效率。而深度優先搜索法還未有普遍認可的典型方法。由於其盲目性，導致目前為止利用其對最短路徑 求解的相關研究較少，但是在道路交通路徑搜索中，深度優先搜索法其優越性的一面。該方法不僅能夠計算出最短路徑，同時可以得到多個備選優化路徑形成最短路徑組，最大程度地滿足用戶對不同路徑的選擇需求。王傑臣等基於一種被其稱為圖的節點弧段聯合結構表示法，避開採用大規模數組，提出了利用深度優先原則來計算最短路徑的方法，從而節約了存儲空間、提高了運算速度，但文章並沒有對深度優先方法本身進行改進。莊明在深度優先搜索法的基礎上，提出了在搜索過程中採用標記距離的方法，利用預先對路的判斷條件，解決了避免進入循環圈，和不必要的重複搜索問題，實現了在含障礙網絡的單源最短距離求解問題，但該方法需要事先人為地進行控制優化，要求操作人員對搜索路網有一定熟悉程度。張連蓬等則是提出一種方向尋優的快速搜索方法，從而提高搜索到最優路徑的速度，但該方法依舊需要遍歷整個節點網絡，沒有提高整體搜索速度，尤其對於具有大量節點的交通網絡，必然產生冗餘。
發明內容
本發明的目的是克服現有技術的不足，提供一種基於方向尋優的啟發式最短路徑搜索方法。
基於方向尋優的啟發式最短路徑搜索方法的步驟如下:I)確定路徑搜索的道路網信息，包括每個道路節點的坐標信息、道路的長度和道路兩端節點信息，然後在道路網中選擇出發節點和目標節點，進行最短路徑的搜索；2)將所有節點狀態初始化，將道路網所有的節點狀態設置為空，即標誌為未搜索狀態，存儲於原始集合中，並將步驟I)中確定的出發節點取出，放入開放集合，即作為當前正在搜索的當前節點Si ；3)搜索道路網中與當前節點Si相連的節點，根據方向尋優原則，排除不滿足方向尋優搜索條件的節點，同時排除那些關閉集合中父節點為當前節點Si，即已被擴展過的節點，從而剩下的即為當前節點Si的可擴展節點；4)更新可擴展節點的F值，F值是以可擴展節點為中間點的最短路徑估算值，並將可擴展節點的父節點更新為當前節點Si，然後將存在於原始集合中的可擴展節點放入臨時表;5)對臨時表進行排序，將具有最小F值且可擴展節點的父節點為當前節點Si的點放入開放集合，並將可擴展節點作為當前節點Si，並重複步驟3) 步驟5);若不存在滿足條件的可擴展節點，判斷當前節點Si是否為原始節點，若不是，則將當前節點Si放入關閉集合中，選擇當前節點Si的父節點作為當前點Si，重複步驟3) 步驟5);若為原始節點，進入步驟6)； 6)道路節點搜索完畢後，根據目標節點的父節點，層層回退至初始節點，該路徑即為最短路徑。所述的步驟4)為:獲取當前節點Si的每個可擴展節點對應的F值，F值是從起始節點出發，經過當前節點Si和該擴展點，到達目標節點的估算值，對於原始集合中的可擴展節點，能直接更新F值和賦值可擴展節點的父節點為當前節點Si，並放入臨時集合中，用來篩選下一搜索節點；對於關閉表中的可擴展節點，需要比較之前的F值和現在的F值大小，若現在的路徑花銷較小，則更新原有的F值，將關閉表中的可擴展節點的父節點賦值為當前節點Si,同時對關閉表中的可擴展節點的子節點採用級聯更新。所述的步驟5)為:判斷臨時表中是否存在父節點為當前節點Si的節點，若存在，將具有最小F值的節點取出，作為當前節點Si，並重複步驟3) 步驟5);若不存在，說明當前節點Si的所有節點都被搜索過，則需要判讀當前節點Si是否為初始節點，若是，則說明所有從初始節點出發的所有可擴展節點都已搜索完畢，循環結束；若不是，則重新回退到當前節點Si的父節點，進行搜索，即將當前節點Si的父節點作為當前節點Si，並重複步驟3) 步驟5)。本發明首先通過對擴展節點進行方向性選擇，縮小了搜索的範圍，提高了方法的效率，避免對不必要的結點的搜索。同時，引入啟發式搜索方法，採用啟發函數的思想，優先選擇權值較低的點進行擴展，降低了原有方法的盲目性，提高找到搜索最短路徑的效率。
:圖1是本發明的方向尋優原則示意圖；圖2是本發明的啟發式方法示意圖；圖3是基於方向尋優的啟發式最短路徑搜索方法流程圖示意圖。
具體實施方式
:如圖1所示，在一般的城市道路交通網中，最短路徑所經道路結點一般都位於起點和終點一定範圍的內，因此通過建立適當的篩選條件，選擇符合條件的節點，可以提高計算效率，避免對不必要的結點的搜索，因此本方法採用了方向尋優原則，在擴展當前節點之前，首先，計算出兩個夾角值Θ1和Θ 2，判斷該節點是否在當前節點和終點的距離範圍內。如圖2，建立以當前節點為原點0，以原點到終點I連線方向為X軸的直角坐標系，Θ I為擴展節點2，當前節點O和終點I之間的夾角，Θ 2為擴展節點2，終點I和當前節點O之間的夾角。當Θ1和Θ 2同時滿足小於90°時，才將其納入當前節點的可擴展節點集合中。該步驟相當於對數據節點進行預處理。計算公式:
權利要求
1.一種基於方向尋優的啟發式最短路徑搜索方法，其特徵在於它的步驟如下: 1)確定路徑搜索的道路網信息，包括每個道路節點的坐標信息、道路的長度和道路兩端節點信息，然後在道路網中選擇出發節點和目標節點，進行最短路徑的搜索； 2)將所有節點狀態初始化，將道路網所有的節點狀態設置為空，即標誌為未搜索狀態，存儲於原始集合中，並將步驟I)中確定的出發節點取出，放入開放集合，即作為當前正在搜索的當前節點Si ； 3)搜索道路網中與當前節點Si相連的節點，根據方向尋優原則，排除不滿足方向尋優搜索條件的節點，同時排除那些關閉集合中父節點為當前節點Si，即已被擴展過的節點，從而剩下的即為當前節點Si的可擴展節點； 4)更新可擴展節點的F值，F值是以可擴展節點為中間點的最短路徑估算值，並將可擴展節點的父節點更新為當前節點Si，然後將存在於原始集合中的可擴展節點放入臨時表； 5)對臨時表進行排序，將具有最小F值且可擴展節點的父節點為當前節點Si的點放入開放集合，並將可擴展節點 作為當前節點Si，並重複步驟3) 步驟5);若不存在滿足條件的可擴展節點，判斷當前節點Si是否為原始節點，若不是，則將當前節點Si放入關閉集合中，選擇當前節點Si的父節點作為當前點Si，重複步驟3) 步驟5);若為原始節點，進入步驟6)； 6)道路節點搜索完畢後，根據目標節點的父節點，層層回退至初始節點，該路徑即為最短路徑。
2.根據權利要求1所述的一種基於方向尋優的啟發式最短路徑搜索方法，其特徵在於所述的步驟4)為:獲取當前節點Si的每個可擴展節點對應的F值，F值是從起始節點出發，經過當前節點Si和該擴展點，到達目標節點的估算值，對於原始集合中的可擴展節點，能直接更新F值和賦值可擴展節點的父節點為當前節點Si，並放入臨時集合中，用來篩選下一搜索節點；對於關閉表中的可擴展節點，需要比較之前的F值和現在的F值大小，若現在的路徑花銷較小，則更新原有的F值，將關閉表中的可擴展節點的父節點賦值為當前節點Si，同時對關閉表中的可擴展節點的子節點採用級聯更新。
3.根據權利要求1所述的一種基於方向尋優的啟發式最短路徑搜索方法，其特徵在於所述的步驟5)為:判斷臨時表中是否存在父節點為當前節點Si的節點，若存在，將具有最小F值的節點取出，作為當前節點Si，並重複步驟3) 步驟5);若不存在，說明當前節點Si的所有節點都被搜索過，則需要判讀當前節點Si是否為初始節點，若是，則說明所有從初始節點出發的所有可擴展節點都已搜索完畢，循環結束；若不是，則重新回退到當前節點Si的父節點，進行搜索，即將當前節點Si的父節點作為當前節點Si，並重複步驟3) 步驟5)。
全文摘要
本發明公開了一種基於方向尋優的啟發式最短路徑搜索方法。該方法首先對當前節點的可擴展節點進行方向性選擇，縮小了節點搜索的範圍。然後根據啟發式搜索函數，對滿足要求的節點的路徑估算值進行比較，優先選擇權值較低的點進行擴展，並記錄下其父節點信息。通過深度優先的方式，步步深入搜索道路節點，直至所有可擴展節點都被遍歷為止。本發明的優點在於利用方向尋優的原則大大降低了節點的遍歷個數，提高了搜索速度，同時引入啟發式函數能夠降低深度優先方法在擴展節點時的盲目性，優先考慮最優節點進行擴展，從而能夠在搜索早期找到最短路徑，還能夠提供多條備選路徑。
文檔編號G06F17/30GK103226581SQ20131011412
公開日2013年7月31日 申請日期2013年4月2日 優先權日2013年4月2日
發明者杜震洪, 張豐, 劉仁義, 房佳, 徐聰 申請人:浙江大學