The FastMap Algorithm for Shortest Path Computations
The FastMap Algorithm for Shortest Path Computations
复制标题
最短路径计算的 FastMap 算法
DOI：
10.24963/ijcai.2018/198
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
T. K. S. Kumar
中科院分区：
文献类型：
--
作者：
L. Cohen;T. Uras;Shiva Jahangiri;Aliyah Arunasalam;Sven Koenig;T. K. S. Kumar
我们提出了一种新的预处理算法，用于将给定边加权无向图的节点嵌入到欧几里得空间中。该空间中任意两个节点之间的欧几里德距离近似于给定图中它们之间的最短路径的长度。稍后，在运行时，可以使用欧几里得距离作为启发式，通过 A* 搜索来计算任意两个节点之间的最短路径。我们的预处理算法称为 FastMap，受到同名数据挖掘算法的启发，并以接近线性的时间运行。因此，FastMap 比使用半定规划生成欧几里得嵌入的竞争方法快几个数量级。 FastMap 还产生可接受的且一致的启发式，因此保证了最短路径的生成。此外，FastMap 适用于一般无向图，对于这些图，许多传统启发式方法（例如曼哈顿距离启发式方法）尚未明确定义。根据经验，我们证明使用 FastMap 启发式的 A* 搜索与使用其他最先进的启发式（例如微分启发式）的 A* 搜索具有竞争力。
We present a new preprocessing algorithm for embedding the nodes of a given edge-weighted undirected graph into a Euclidean space. The Euclidean distance between any two nodes in this space approximates the length of the shortest path between them in the given graph. Later, at runtime, a shortest path between any two nodes can be computed with an A* search using the Euclidean distances as heuristic. Our preprocessing algorithm, called FastMap, is inspired by the data-mining algorithm of the same name and runs in near-linear time. Hence, FastMap is orders of magnitude faster than competing approaches that produce a Euclidean embedding using Semidefinite Programming. FastMap also produces admissible and consistent heuristics and therefore guarantees the generation of shortest paths. Moreover, FastMap applies to general undirected graphs for which many traditional heuristics, such as the Manhattan Distance heuristic, are not well defined. Empirically, we demonstrate that A* search using the FastMap heuristic is competitive with A* search using other state-of-the-art heuristics, such as the Differential heuristic.