基于经典算法的设计技术已被证明对最近几个大规模问题的创新很有用，例如旅行行程和路线挑战。例如，Dijkstra 算法通常用于计算图中的路线，但计算量可能会迅速增加到超出小镇的规模。然而，“分区”道路网络的过程可以通过有效缩小计算过程中搜索的图量来大大加快算法速度。
在本文中，我们将介绍如何使用经典算法的思想设计道路网络的图形分区算法，其中部分内容在WWW 2021的“基于草图的道路网络近似最短路径算法”中进行了介绍。我们的算法使用随机游走，这是一个经典概念，它通过显着减小网络规模来计算最短路线，这与直觉相反，它可以对北美大陆的整个道路网络进行高质量的分区，比具有类似输出质量的其他分区算法快近一个数量级1。
使用图表来建模道路网络
道路网络和图 之间存在着一种众所周知且有用的对应关系，其中交叉口成为节点，道路成为边。
要理解路由如何从分区中受益，请考虑寻找最快路线的最著名解决方案：Dijkstra 算法，该算法采用广度优先搜索的方式工作。Dijkstra 算法从源开始执行详尽的搜索，直到找到目的地。因此，随着源和目的地之间的距离增加，计算速度可能会降低一个数量级。例如，计算华盛顿州西雅图市内的路线比计算从华盛顿州西雅图到加利福尼亚州旧金山的路线更快。此外，即使是都市内的路线，Dijkstra 算法在计算过程中探索的详尽空间量也会导致数秒级的不切实际的延迟。但是，通过识别内部连接较多、与外部连接较少的区域（如纽约州斯塔顿岛），可以将计算分成多个较小的块。
顶部：纽约斯塔顿岛周边的路线问题。底部：对应分区图。蓝色节点表示斯塔顿岛的唯一入口/出口。
考虑从上图中的 A 点开车到 B 点。一旦决定从哪里进入史坦顿岛（Outerbridge 或 Goethals）以及从哪里离开（Verrazzano），问题就可以分解为三个较小的驾驶部分：到入口、出口，然后使用最佳可用路线到达目的地。这意味着路线算法只需要考虑这些特殊点（信标）即可在 A 点和 B 点之间导航，从而可以更快地找到最短的准确路径。
请注意，只有在信标数量不太多的情况下，信标才有用 - 信标越少，需要添加的快捷方式就越少，搜索空间就越小，计算速度就越快 - 因此，好的分区应该具有相对较少的组件数量（即道路网络的特定区域） 的信标。
以斯塔顿岛为例，现实生活中的道路网络有许多信标（特殊点，如桥梁、隧道或山口），导致某些区域连接良好（例如，拥有大型街道网格），而其他区域连接不良（例如，只能通过几座桥梁到达的岛屿）。问题变成了如何有效地定义组件并确定连接道路网络的最小信标数量。
我们的分割算法
因为两个组件之间的每个连接都是一个潜在的信标，所以我们采取的方法是为了确保信标不会太多，以最小化组件之间的连接数量来划分道路网络。
为此，我们首先将网络划分为两个平衡的（即大小相似）部分，同时最小化连接这两个部分的道路数量，从而导致每个部分中的信标与道路的比例实际上很小。然后，该算法继续将网络一次分为两部分，直到所有部分都达到所需大小（就内部道路数量而言），从而产生有用的多部分分区。这里有一个谨慎的平衡。如果尺寸太小，我们会得到太多的信标；而如果它太大，那么它只对长路线有用。因此，尺寸留作输入参数，并在算法最终确定时通过实验确定。
虽然有许多分区方案，例如METIS（用于一般网络）、PUNCH和惯性流（均针对道路网络进行了优化），但我们的解决方案基于惯性流算法，并经过增强，可以在整个大陆和城市中高效运行。
道路网络的平衡划分
如上所述，如何将以图形表示的道路网络划分为两个平衡的部分？ 第一步是通过将紧密连接的节点分组在一起来缩小图形，这使我们能够加快接下来的双向分区阶段。这就是随机游走有用的地方。
随机游动具有许多有用的理论特性，这就是为什么它们被用于研究从森林中蚊子的运动到热扩散等一系列主题的原因。与我们的应用最相关的是，它们往往会“被困”在内部连接良好但外部连接较差的区域。考虑在史坦顿岛的街道上随机行走固定步数：由于出口道路相对较少，大多数步数发生在岛内，走出岛外的概率很低。
随机游走的图示。假设蓝色图表是与史坦顿岛相对应的假想道路网络。进行 50 次随机游走，全部从中间点开始。每次随机游走持续 10 步或直到走出岛屿。每个节点的数字表示随机游走访问了多少次。最后，岛内的任何节点的访问频率都远高于岛外的节点。
在找到这些小组件之后，这些小组件将是高度连接的节点组合在一起（例如上例中的斯塔顿岛），算法将每个组收缩为一个新的单个节点。
通过查找节点组（中）并将每组合并为单个“超级”节点（右）来减小原始图的大小（左） 。此处的示例是手动选择的，以更好地说明算法的其余部分。
该算法的最后步骤是将这个小得多的图分成两部分，然后将这个小图上的分割细化为道路网络原始图上的分割。然后我们使用惯性流算法在较小的图上找到切割，使信标（即被切割的边）与节点的比率最小化。
该算法评估不同的方向。对于每个方向，我们找到最小化前 10% 和后 10% 节点之间的边切割（例如信标）数量的划分
找到小图上的切点后，算法会执行细化步骤，将切点投影回道路网络的原始图。
结论
这项研究表明，经典算法为解决大规模问题提供了许多有用的工具。图分区可用于将大规模图问题分解为较小的子问题，以便独立和并行解决 - 这在 Google 地图中尤为重要，因为该分区算法可用于高效计算路线。
致谢
我们感谢我们的合作者 Google Research 的 Lisa Fawcett、Sreenivas Gollapudi、Kostas Kollias、Ravi Kumar、Andrew Tomkins、Ameya Velingker 以及 Google Maps 的 Pablo Beltran、Geoff Hulten、Steve Jackson 和 Du Nguyen。
评论