路径规划算法研究

开始进行路径规划算法的分析和研究，所有的研究都是针对该网站提供的论文，进行简单的学习分析，尽量使用简单的语言，提取核心思想

网址：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：，如需转载请自行联系原作者