Contraction Hierarchies.pdf

简介：
《Contraction Hierarchies》是一篇关于高效路径查找算法的研究论文，提出了一种快速计算图中两点间最短路径的方法。 CH（Contraction Hierarchies）是一种快速且简单的层次化路网路由算法，在文档《Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks》中被作者Robert Geisberger介绍。这项技术出自卡尔斯鲁厄工业大学理论信息学研究所的毕业论文，该论文于2008年7月1日完成，指导教授包括Peter Sanders和Dominik Schultes博士。 CH算法的核心概念是节点收缩过程，在这个过程中逐个移除图中的节点，并在剩余部分添加捷径边以保持最短路径的距离。这一方法生成了包含原图与捷径边的收缩层次结构（CH），并定义了一种基于节点选择的重要顺序，用以优化双向迪杰斯特拉算法（bidirectional Dijkstra algorithm）。通过这种方式，在正向搜索中仅松弛指向更重要节点的边，并在反向搜索中只考虑来自重要节点的边，从而大大减少了搜索空间。 为了确定这种重要的节点排序方式，CH使用了一种基于优先队列的方法。每个节点的优先级是根据收缩后图中的稀疏性以及其他因素计算得出的一个线性组合值。通过选择合适的权重项组合，可以生成不同需求下的层次结构。 与先前的最佳层次化迪杰斯特拉技术相比，CH算法能够将查询时间减少五倍，并且其存储开销为负数——意味着用于距离计算的数据结构比原始图占用更少的空间。因此，它被广泛应用于多种路径规划技术的基础之上，包括多对多路由、中转节点路由、目标导向路由以及移动和动态场景下的性能优化。 在实际应用方面，CH算法已在诸如Bing地图的导航系统等服务中得到采用。其价值在于能够显著提高路径计算效率，并且适应于交通网络的变化情况（例如因道路封闭或拥堵导致的道路变化）。此外，它不仅适用于汽车导航，还支持步行和自行车等多种出行方式。 由于具备出色的性能与低资源消耗的特点，CH算法已经成为研究界及工业领域中不可或缺的工具，在地图服务以及地理信息系统等应用中被广泛集成。在互联网地图服务日益成为日常生活一部分的时代背景下，CH算法对于确保这些服务的速度和可靠性起到了关键作用。