K* : heuristics-guided, on-the-fly k shortest paths search
K* : heuristics-guided, on-the-fly k shortest paths search
复制标题
K* ：启发式引导、动态 k 个最短路径搜索
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
S. Leue
中科院分区：
文献类型：
--
作者：
Husain Aljazzar;S. Leue
本文提出了一种搜索算法K-∗，用于寻找给定有向赋权图中指定顶点对之间的k条最短路径。与现有的∗算法相比，K-KSP算法作为一种有向算法有两个优点。首先，K∗动态执行，这意味着它不需要图形显式可用并存储在主内存中。图表的各个部分将根据需要生成。其次，可以使用启发式函数来引导K∗。我们讨论了K-∗的性质，包括它的正确性，以及它的渐近最坏情况的复杂性，已经被证明是关于运行时和空间的Ofo(m+nlogn+k)，其中n是图的顶点数，m是图的边数。我们报告的实验结果表明，与目前已知的最有效的k-最短路径算法相比，K-∗算法具有更好的性能。在其他工作中，已经证明K∗可以有效地计算随机模型检验的反例。
We present a search algorithm, called K∗, for finding the k shortest paths (KSP) between a designated pair of vertices in a given directed weighted graph. As a directed algorithm, K∗ has two advantages compared to current KSP algorithms. First, K∗ performs on-the-fly, which means that it does not require the graph to be explicitly available and stored in main memory. Portions of the graph will be generated as needed. Second, K∗ can be guided using heuristic functions. We discuss the properties of K∗, including its correctness, and its asymptotic worst-case complexity, which has been shown to be ofO(m+n logn+ k) with respect to both runtime and space, where n is the number of vertices andm is the number of edges of the graph. We report on experimental results which illustrate the favorable performance of K∗ compared to the most efficient k-shortest-paths algorithms known so far. In other work it has been shown that K∗ can be used to efficiently compute counterexamples for stochastic model checking.
影响因子：
7.4
作者：
Aljazzar, Husain;Leue, Stefan
通讯作者：
Leue, Stefan
用于概率模型检查的定向启发式反例生成：比较评估
DOI：
10.1145/1808877.1808883
发表时间：
2010
期刊：
影响因子：
--
作者：
Husain Aljazzar;Matthias Kuntz;Florian Leitner-Fischer;Stefan Leue
通讯作者：
Stefan Leue