K*: A heuristic search algorithm for finding the k shortest paths
K*: A heuristic search algorithm for finding the k shortest paths
复制标题
DOI：
10.1016/j.artint.2011.07.003
复制
发表时间：
2011-12-01
影响因子：
14.4
通讯作者：
Leue, Stefan
中科院分区：
文献类型：
--
作者：
Aljazzar, Husain;Leue, Stefan
我们提出了一个有向搜索算法，称为K*，在给定的有向加权图中找到指定的一对顶点之间的k条最短路径。与现有的k-最短路径算法相比，K* 有两个优点。首先，K* 是动态操作的，这意味着它不需要图显式可用并存储在空闲内存中。将根据需要生成图形的部分。一下可以使用启发式函数来引导K*。我们证明了K* 的正确性，并确定其渐近最坏情况下的复杂性时，使用一致的启发式是相同的最先进的，O（m + n log n + k），相对于运行时间和空间，其中n是顶点数和m是图的边数。我们提出了一个实验评估K* 通过将其应用到路线规划问题，以及随机模型检查的反例生成。实验结果表明，由于使用启发式，在飞行中搜索K* 可以使用更少的时间和内存相比，最有效的k-最短路径算法到目前为止。(C)2011 Elsevier B. V.保留所有权利。
We present a directed search algorithm, called K*, for finding the k shortest paths between a designated pair of vertices in a given directed weighted graph. K* has two advantages compared to current k-shortest-paths algorithms. First, K* operates on-the-fly, which means that it does not require the graph to be explicitly available and stored in slain memory. Portions of the graph will be generated as needed. Second. K* can be guided using heuristic functions. We prove the correctness of K* and determine its asymptotic worst-case complexity when using a consistent heuristic to be the same as the state of the art, O(m + n log n + k), with respect to both runtime and space, where n is the number of vertices and m is the number of edges of the graph. We present an experimental evaluation of K* by applying it to route planning problems as well as counterexample generation for stochastic model checking. The experimental results illustrate that due to the use of heuristic, on-the-fly search K* can use less time and memory compared to the most efficient k-shortest-paths algorithms known so far. (C) 2011 Elsevier B.V. All rights reserved.