K* : heuristics-guided, on-the-fly k shortest paths search

Zitieren

Dateien zu dieser Ressource

Prüfsumme: MD5:891091b8f1adb1690afad678a829544b

ALJAZZAR, Husain, Stefan LEUE, 2010. K* : heuristics-guided, on-the-fly k shortest paths search

@inproceedings{Aljazzar2010heuri-21288, title={K* : heuristics-guided, on-the-fly k shortest paths search}, year={2010}, author={Aljazzar, Husain and Leue, Stefan}, note={Paper presented at: Sixth Workshop on Model Checking and Artificial Intelligence (MoChArt) 2010} }

<rdf:RDF xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" xmlns:bibo="http://purl.org/ontology/bibo/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:dcterms="http://purl.org/dc/terms/" xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > <rdf:Description rdf:about="https://kops.uni-konstanz.de/rdf/resource/123456789/21288"> <dcterms:issued>2010</dcterms:issued> <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/21288"/> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2013-03-12T13:19:01Z</dc:date> <dc:contributor>Leue, Stefan</dc:contributor> <dcterms:abstract xml:lang="eng">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 of 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 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.</dcterms:abstract> <dc:contributor>Aljazzar, Husain</dc:contributor> <dcterms:title>K* : heuristics-guided, on-the-fly k shortest paths search</dcterms:title> <dc:creator>Aljazzar, Husain</dc:creator> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2013-03-12T13:19:01Z</dcterms:available> <dc:language>eng</dc:language> <dcterms:rights rdf:resource="http://nbn-resolving.org/urn:nbn:de:bsz:352-20140905103605204-4002607-1"/> <dc:creator>Leue, Stefan</dc:creator> <dc:rights>deposit-license</dc:rights> </rdf:Description> </rdf:RDF>

Dateiabrufe seit 01.10.2014 (Informationen über die Zugriffsstatistik)

aljazzar_212881.pdf 90

Das Dokument erscheint in:

KOPS Suche


Stöbern

Mein Benutzerkonto