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

淩亂°似流年 2022-04-11 14:19 744阅读 0赞

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

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

A-star：[https://en.wikipedia.org/wiki/A][https_en.wikipedia.org_wiki_A]\*\_search\_algorthm

CH：[http://algo2.iti.kit.edu/schultes/hwy/contract.pdf][http_algo2.iti.kit.edu_schultes_hwy_contract.pdf]

HH：[http://algo2.iti.kit.edu/documents/routeplanning/esa06HwyHierarchies.pdf][http_algo2.iti.kit.edu_documents_routeplanning_esa06HwyHierarchies.pdf]

CRP：[http://research.microsoft.com/pubs/145688/crp-sea.pdf][http_research.microsoft.com_pubs_145688_crp-sea.pdf]

[http_algo2.iti.kit.edu_routeplanning.php]: https://link.zhihu.com/?target=http%3A//algo2.iti.kit.edu/
[https_en.wikipedia.org_wiki_A]: https://link.zhihu.com/?target=https%3A//en.wikipedia.org/wiki/A
[http_algo2.iti.kit.edu_schultes_hwy_contract.pdf]: https://link.zhihu.com/?target=http%3A//algo2.iti.kit.edu/schultes/hwy/contract.pdf
[http_algo2.iti.kit.edu_documents_routeplanning_esa06HwyHierarchies.pdf]: https://link.zhihu.com/?target=http%3A//algo2.iti.kit.edu/documents/routeplanning/esa06HwyHierarchies.pdf
[http_research.microsoft.com_pubs_145688_crp-sea.pdf]: https://link.zhihu.com/?target=http%3A//research.microsoft.com/pubs/145688/crp-sea.pdf