K : A heuristic search algorithm for finding the k shortest paths


Dateien zu dieser Ressource

Dateien Größe Format Anzeige

Zu diesem Dokument gibt es keine Dateien.

ALJAZZAR, Husain, Stefan LEUE, 2011. K : A heuristic search algorithm for finding the k shortest paths. In: Artificial Intelligence. 175(18), pp. 2129-2154. ISSN 0004-3702. Available under: doi: 10.1016/j.artint.2011.07.003

@article{Aljazzar2011heuri-19330, title={K : A heuristic search algorithm for finding the k shortest paths}, year={2011}, doi={10.1016/j.artint.2011.07.003}, number={18}, volume={175}, issn={0004-3702}, journal={Artificial Intelligence}, pages={2129--2154}, author={Aljazzar, Husain and Leue, Stefan} }

We present a directed search algorithm, called K<sup>⁎</sup>, for finding the k shortest paths between a designated pair of vertices in a given directed weighted graph. K<sup>⁎</sup> has two advantages compared to current k-shortest-paths algorithms. First, K<sup>⁎</sup> operates 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<sup>⁎</sup> can be guided using heuristic functions. We prove the correctness of K<sup>⁎</sup> and determine its asymptotic worst-case complexity when using a consistent heuristic to be the same as the state of the art, O(m+nlogn+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<sup>⁎</sup> 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<sup>⁎</sup> can use less time and memory compared to the most efficient k-shortest-paths algorithms known so far. Publ. in: Artificial intelligence ; 175 (2011), 18. - S. 2129-2154 2012-05-22T09:47:30Z terms-of-use 2011 K<sup>⁎</sup> : A heuristic search algorithm for finding the k shortest paths Leue, Stefan Aljazzar, Husain 2012-05-22T09:47:30Z eng Leue, Stefan Aljazzar, Husain

Das Dokument erscheint in:

KOPS Suche


Mein Benutzerkonto