[發明專利]用于道路網的最短路徑搜索方法及裝置

有效

• 申請號: 201410446777.0
• 申請日: 2014-09-03
• 公開（公告）號: CN104266656B
• 公開（公告）日: 2017-06-06
• 發明（設計）人: 李國良;馮建華;陳碩;朱璇
• 申請（專利權）人: 清華大學;北京三星通信技術研究有限公司
• 主分類號: G01C21/34
• 分類號: G01C21/34;G06F19/00
• 代理公司: 北京清亦華知識產權代理事務所(普通合伙)11201
• 代理人: 張大威

技術領域

本發明涉及地圖搜索技術領域，特別涉及一種用于道路網的最短路徑搜索方法及裝置。

背景技術

最短路徑問題是圖論研究中的一個經典算法問題，旨在尋找圖(由結點和路徑組成的)中兩結點之間的最短路徑。相關技術中，例如Dijkstra算法是傳統的解決方法，主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。然而，Dijkstra算法雖然能得出最短路徑的最優解，但是遍歷計算的節點過多，導致效率低，不能很好地滿足實時性要求。

發明內容

本發明旨在至少在一定程度上解決上述相關技術中的技術問題之一。

為此，本發明的一個目的在于提出一種效率高，能滿足實時性要求的用于道路網的最短路徑搜索方法。

本發明的另一個目的在于提出一種用于道路網的最短路徑搜索裝置。

為達到上述目的，本發明一方面實施例提出了一種用于道路網的最短路徑搜索方法，包括以下步驟：將道路網分割為多個子網絡；根據所述多個子網絡生成樹狀結構道路網絡，其中，所述樹狀結構道路網絡中每個節點為一個子網絡；計算所述樹狀結構道路網絡中同一層的子網絡的邊界節點之間的最短路徑；輸入查詢點和目標點；根據所述樹狀結構道路網絡中同一層的子網絡的邊界節點之間的最短路徑通過動態規劃算法得到所述查詢點和目標點之間的初始最短路徑；以及對所述初始最短路徑進行補充以獲取所述查詢點和目標點之間完整的最短路徑。

根據本發明實施例提出的用于道路網的最短路徑搜索方法，通過將道路網分割為多個子網絡以生成樹狀結構道路網絡，并且計算同一層的子網絡的邊界節點之間的最短距離，從而當輸入查詢點和目標點時，實現快速得到查詢點和目標點之間的初始最短路徑，并對初始最短路徑進行補充以獲取完整的最短路徑，不但效率高，而且很好地滿足實時性要求。

另外，根據本發明上述實施例的用于道路網的最短路徑搜索方法還可以具有如下附加的技術特征：

進一步地，在本發明的一個實施例中，所述計算所述樹狀結構道路網絡中同一層的子網絡的邊界節點之間的最短路徑，進一步包括：如果所述邊界節點為葉子節點，則計算并保存所述葉子節點的每一個邊界點到每一個落在所述葉子節點的道路網絡的邊界節點之間的最短距離的距離矩陣；如果所述邊界節點為中間節點，則計算并保存所述中間節點的所有子節點的邊界點中每兩個邊界點之間的最短距離的距離矩陣。

進一步地，在本發明的一個實施例中，通過以下公式得到所述查詢點和目標點之間的初始最短路徑，所述公式為：

minPath(q,Gi-1(q))＝min qi in Border(Gi(q))(minPath(q,qi)+minPath(qi,Gi-1(q)))，

其中，Gi(q)表示邊界節點，Border(Gi(q)表示Gi(q)中的所有邊界點。

進一步地，在本發明的一個實施例中，所述對所述初始最短路徑進行補充以獲取所述查詢點和目標點之間完整的最短路徑，進一步包括：對所述初始最短路徑的每一對邊界點之間的路徑進行差分，并從對應的子網絡的距離矩陣中引入新的邊界點進行補充。

進一步地，在本發明的一個實施例中，上述方法還包括：如果所述查詢點和所述目標點未處于同一層的子網絡，則通過Dijkstra算法獲取所述完整的最短路徑。

本發明另一方面實施例提出了一種用于道路網的最短路徑搜索方法，包括：生成模塊，用于將道路網分割為多個子網絡，并根據所述多個子網絡生成樹狀結構道路網絡，其中，所述樹狀結構道路網絡中每個節點為一個子網絡；計算模塊，用于計算所述樹狀結構道路網絡中同一層的子網絡的邊界節點之間的最短路徑；以及獲取模塊，當輸入查詢點和目標點時，用于根據所述樹狀結構道路網絡中同一層的子網絡的邊界節點之間的最短路徑通過動態規劃算法得到所述查詢點和目標點之間的初始最短路徑，并且對所述初始最短路徑進行補充以獲取所述查詢點和目標點之間完整的最短路徑。

根據本發明實施例提出的用于道路網的最短路徑搜索裝置，通過將道路網分割為多個子網絡以生成樹狀結構道路網絡，并且計算同一層的子網絡的邊界節點之間的最短距離，從而當輸入查詢點和目標點時，實現快速得到查詢點和目標點之間的初始最短路徑，并對初始最短路徑進行補充以獲取完整的最短路徑，不但效率高，而且很好地滿足實時性要求。

另外，根據本發明上述實施例的用于道路網的最短路徑搜索裝置還可以具有如下附加的技術特征：