常用的地图导航和路径规划算法

曾山
2023-12-01

作者:李传学
链接:https://www.zhihu.com/question/24870090/answer/73834896
来源:知乎
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
 

明确一点,基本的图搜索算法dijkstra是无法满足互联网地图检索实时响应这种性能要求,所以各家公司都有各自的预处理方法:分层或者预计算。具体采用何种方式,这取决于采取的加速算法相关。在2008年前后,以KIT(http://algo2.iti.kit.edu/routeplanning.php)为主的研究院产出了多个路径规划加速算法,其中以contraction hierarchies 和 highway hierarchies较出名,加之微软研究院提出的Customizable Route Planning,与传统的A-star,基本上支撑了目前工业界地图产品的路径规划服务。

A-star:https://en.wikipedia.org/wiki/A*_search_algorthm

CH:http://algo2.iti.kit.edu/schultes/hwy/contract.pdf

HH:http://algo2.iti.kit.edu/documents/routeplanning/esa06HwyHierarchies.pdf

CRP:http://research.microsoft.com/pubs/145688/crp-sea.pdf

 类似资料: