路径规划-CH算法

发表于 分类于

1. 概述

CH(Contraction Hierarchies)是道路网络最短路径算法之一，其应用收缩(contract)节点的方法将节点分层，显著提高了最短路径的搜索速度。

CH算法涵盖数据预处理和路径搜索两个方面，预处理通过收缩节点生成路网图的层次结构，搜索过程利用层次图搜索

理解CH算法需要弄懂两个问题：

  • 怎么通过收缩(contract)节点
  • 怎么在分层后的网络中进行路径查询

2. 整理思想

  • 道路网形成的带权有向图G(V,E,c)是一个平面结构
  • 对于路网图G中的节点，按照某些维度、对每个节点都定义一个优先级level，某种程度上可以认为这个优先级就是节点在图G中的重要性
  • 然后沿垂直方向将图中的每个节点做沉降，使得每个节点在垂直方向上的高度与其在图G中的优先级一致，沿着节点的高度形成层次结构
  • 寻找s→t的最短路径时，分别从s和t做正向和反向Dijkstra，Dijkstra的每一步都沿着高度大于当前节点高度的方向搜索，形成两个端点开始向上爬图的搜索过程，双方相遇的某个顶点即为最短路径。由此降低节点搜索规模、加速搜索性能
  • 由于G中搜索是向上方向，因此当沉降某个节点v破坏了剩余节点的连通性和最短距离时，需要在剩余节点中添加shortcut边E’保持图的语义不变，形成图G*(V,E+E’,c+c’)

通俗理解

  • 找两点s,t之间的最优路径，通常是找到s和t点附近的交通枢纽s’和t’，找到s’和t’之间的最优路径，再s和t的局部区域内，再分别找到s-s’以及t-t’的最优路径，这样就能快速找到s-t的最优路径
  • 假设s-t存在最优路径s-v1-v2-…-vn-t，那么必然可以将这些节点分成不同的等级，并预先算出低等级点到重要节点的距离和路线，这样算s-t的路线就可以利用预先算好的路线距离快速寻找

伪代码

3. 收缩节点 (Contraction )

根据图G中所有节点更具重要性，存储到一个优先级队列中，其中优先级最低的节点在队顶。 收缩(contract)节点就是将队列中优先级最小的节点删除，并添加捷径(shortcut)以保证最短路径的不变性。

3.1. 需要添加捷径(shortcut)

若收缩(contract)节点u时找到一条最短路径P(v,u,w)则需要添加一条权职为w(v,u)+w(u,w)捷径(shortcut)，流程如下图：

3.2. 不需要添加捷径(shortcut)

收缩(contract)节点u时找到一条路径P(v,x,y,w)其权重小于P(v,u,w)，则说明存在路径P(v,u,w)不使最短路径则不需要添加捷径(shortcut)。

witness：

  • 对于u-v-w，witness就是存在u-w的一条路径，不经过v且起距c(u,w)⇐c(u,w)+(v,w)，也即这条路径可以证明u-v-w不是u-w的唯一最短路径
  • witness的计算: 对于节点v，从v的上游邻接点发起dijkstra搜索寻找到v的下游邻接点的最短路径

3.3. 节点顺序选择(Node Order Selection)

应用优先级队列存储节点，其中最小优先级节点在队列顶端。 在更新节点的优先级时可能会影响其他的节点，为了有效的解决这种问题CH采用以下三种技术：

  • Lazy Updates: 更新队顶节点后，若此节点任然在队顶则移除，若此节点不再对新对顶节点继续更新。重复过程直到确定最小优先级节点并删除
  • 更新节点的优先级后，同时更新其相邻的节点的优先级
  • 周期性的更新所有节点优先级，并重新构建优先级队列

3.4. Node Level

综上所知，对图G(V,E,c)可以构造任一的node level形成层次结构并保证搜索结果的正确性，但是层次结构的好坏决定搜路性能好坏，因此计算node level的方法就是CH算法的关键

CH中定义了几个要素来构建node level：

  • 边的差异性 (edge-difference)

    • Edge diff定义为将一个节点v从图中去掉后，需要新增的shortcut边数量 - 删除的原始边的数量
    • 图中含义是去掉某个几点可以使图变的稀疏程度，更稀疏的效果更佳
    • 现实理解对应越重要的点越延后处理，比如优先去掉边缘节点而不是枢纽节点

  • 均匀性 (Uniformity)

    • 目的是使最终形成的层次图更均衡、更扁平，这样搜索过程中需要遍历的高度降低、提升效率，主要有以下几个方面

      • neighbours: 去掉某个几点v后，下一次尽量避免处理v的邻接点
      • shortcut: 避免使shortcut边折叠的层次过多，过多代表着从shortcut一端到达另一端需要更多层次，还原的时候也需要跟多的消耗
      • depth: 表示某个节点在结果层次树里的高度，根节点的话代表的就是整个树的高度，目的也是为把图压的更扁平

    • Notice

      • 节点的层次(level)和高度(depth)是不同的，如下图中节点共有5个层次、level(a)=5，但是depth(a)=2
             a
          / /| \
         b / |  \
          /  |   d
        c    |
             e

  • 深度 (Depth)

3.5. 结束条件

  • 限制被处理的节点个数
  • 限制最短路径的边数

3.6. Contraction cost

  • contraction过程中两个主要过程，一是选择当前最小优先级的节点，二是去掉当前点后要判断是否需要添加shortcut，这是contraction的主要消耗，尤其是后者，因此要在计算时间和准确性之间做妥协
  • lazy update:：contraction一个节点都可能带来remain_graph中某些遥远的节点的重要性发生变化，因此精确的做法是每处理一个节点都全局重算一次剩余所有节点的优先级，但是这样代价太高，因此只在处理某个节点的时候才重新计算当前节点的优先级，如果优先级更新后依然最小则处理，如果已不是最小节点，则重新取下一个最小优先级的节点。这个过程是在局部做了优先级更新，但是全局上不能保证
  • limit search space：witness计算过程中会发起dijkstra搜索，在找不到最短路径或最短路径节点数很多的情况下，这个搜索规模会非常庞大，因此在witness path搜索的过程中会限制dijkstra搜索的最大规模，比如最多执行多少hop
  • 存在witness但没找到的情况：这种情况需要添加shortcut边，shortcut边是冗余的、但是对图的语义和正确性没有影响

3.7. Contraction后图的结构

  • 平面图上理解：平面图G上加shortcut边
  • 立体层面理解：倒立树, 每个树叉的根都是某个局部最优路径的顶点，同时又是整个路网中的某个中间节点

4. 路径搜索

路径搜索的第一步是找到源节点到目的节点的最短路径，其中可能包含捷径(shortcut)，第二步是将最短路径中捷径解开(unpack)以得到原图中的路径

4.1. 搜索最短路径

对于源节点s采用前向搜索，对于目的节点t采用后向搜索，搜索时应用Dijkstra算法

  • 前向搜索(Forward )：以节点s的优先级为最低优先级，搜索优先级高的节点
  • 后向搜索(Backward)：以节点t的优先级为最低优先级，搜索有优先级高的节点

  • 图(a): 描述了源节点u到目的节点z的最短路径搜索流程，其中u→v为前向搜索，z→v为后向搜索

  • 图(b): 描述了源节点u到目的节点y的最短路径搜索流程，其中u→v为前向搜索，y→v为后向搜

    （普通箭头表示原图路径，虚线表示捷径，红色箭头表示查找到得最短路径）

4.2. 中止条件

不可以在前向搜索与后向搜索第一次相遇时停止搜索，要所有相关路径搜索完成后才能结束，这样才能保证最短路径的正确性

第一相遇结束问题说明：

图中为节点s到节点t的搜索过程，s的前向搜索第一找到x节点，t的后向搜索第一次找到的也使x节点，若此时结束搜索，路径<s,x,t>并不是最短路径。需要继续搜索余下节点y后才找到最短路径<s,y,t>

4.3. 结果路径还原 (Unpack)

由于每一个捷径(shortcut)都是由两条边组成，因此依据此原理不断将最短路径中捷径(shortcut)解开(unpack)即可，例最短路径<u,z>的解开流程如下图：

（普通箭头为原图边，红色箭头为搜索到得最短路劲，虚线为捷径(shortcut)）

5. 算法分析

  • 算法正确性
    • 从G中contranction一个节点v的时候
      • 如果remain_graph G’中v的邻接点间连通语义不变、即这个节点有无v对G’都没有影响、不会影响结果的正确性
      • 如果remain_graph G’中v的领节点间连通语义发生了变化、则需要添加shortcut边代表原始边、维持图的语义不变，确保结果的正确性
  • 为什么向上搜索
    • 对G中某个点v做contraction处理后，从remain_graph G’中出发的点都不会下降到v，也即没有向下的搜索过程，如果每个节点都是一个独立的level的话、则必然也不存在平行的搜索，因此搜索必然是向上的
  • 为什么是快的
    • 搜索空间小：n个节点可以形成n个层次，搜索过程是向上的，因此随着层级上升，搜索空间越来越小
    • 最优路径预计算和缓存：shortcut边实际上代表的是某两个点之间的最短路径，比如一层嵌套shortcut边代表的是跨越一个中间节点的两点简的最短路径，预处理过程实际上在计算和存储某两点间最短路线和距离的过程

6. 局限

  • 基于静态图，不支持动态更新，应用上比如实时路况
  • 对于起终点s-t，如果存在多条距离相同的路径，CH只能找一条

7. 参考文献

  1. Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks 
  2. Contraction Hierarchies briefly explained