路徑規劃算法研究

開始進行路徑規劃算法的分析和研究，所有的研究都是針對該網站提供的論文，進行簡單的學習分析，盡量使用簡單的語言，提取核心思想

網址：http://algo2.iti.kit.edu/schultes/hwy/utrecht.pdf

在所有的描述中，不會提供任何的插圖和相關的數學表達式，相關的參考資料，均可從提供的網址

中搜尋到

目前使用的是歐洲的路網，作為道路的搜尋模型，大約有1800萬個節點，完全符合大型複雜的路網結構

的條件

假設起始點S(source)和目的點t(target)之間的半徑為R

1）采用單純的Dijkstra算法

搜尋的半徑是PI*R*R

2)采用bidirectional Dijkstra算法（雙向搜尋)

搜尋的半徑大概是2*PI*(R/2)*(R/2)

是以第二種算法比第一種算法節省了一半的搜尋範圍

即使是雙向搜尋，效率仍然非常低下，但是可以通過下面的處理提供進一步優化的方向

1）額外的資料  例如：節點坐标

不僅僅儲存道路之間的長度，還儲存節點坐标，路徑的規劃點實際上還是不會偏離起點和終點的連線

2）預處理（preprocessing)->輔助資料（auxiliary data) 例如：路标

3）圖的特殊屬性 例如：平坦（planar),分層的(hierarchical)

如下提供加快路徑規劃的方案：

Contraction Hierarchies(CH)  分層思想

Highway-Node Routing

路網分層算法的基礎

http://algo2.iti.kit.edu/schultes/hwy/thesisSlides.pdf

研究網址

<a href="http://www.policyalmanac.org/games/binaryHeaps.htm" target="_blank">http://www.policyalmanac.org/games/binaryHeaps.htm</a>

<a href="http://mgrenier.me/2011/06/pathfinding-concept-the-basics/" target="_blank">http://mgrenier.me/2011/06/pathfinding-concept-the-basics/</a>

<a href="http://algo2.iti.kit.edu/schultes/hwy/demo/" target="_blank">http://algo2.iti.kit.edu/schultes/hwy/demo/</a>

    本文轉自fengyuzaitu 51CTO部落格，原文連結http://blog.51cto.com/fengyuzaitu/1738693：，如需轉載請自行聯系原作者