A*-Variante von Dijkstra

lkbaerenfaenger
Mausschubser
Mausschubser
Beiträge: 44
Registriert: 13. Mär 2012 12:44

A*-Variante von Dijkstra

Beitrag von lkbaerenfaenger »

Hallo,

in der Auflistung der klausurrelevanten Wiki-Seiten findet sich bei Dijkstra der Vermerk, dass man besonderen Augenmerk auf "Further information" legen soll. In diesem Abschnitt wird die Dijkstra-Variante A* "erklärt". D.h. es wird auf einen Abschnitt der Path-Seite verwiesen, "admissible distance function". Ich habe leider absolut keine Chance zu entziffern, was dort (wohl absichtlich unverständlich) versucht wird zu vermitteln. Falls jemand eine Idee hat, was dort stehen könnte, wäre ich sehr dankbar, wenn dieser jemand sein wissen teilen würde. ;)

http://wiki.algo.informatik.tu-darmstad ... p/Dijkstra
http://wiki.algo.informatik.tu-darmstad ... .php/Paths

LG Lucas

Mathematics
Erstie
Erstie
Beiträge: 17
Registriert: 23. Sep 2013 12:12

Re: A*-Variante von Dijkstra

Beitrag von Mathematics »

Prinzipiell geht es hier um eine Modifikation der Kantenlängen im Graphen. Das bedeutet genauer gesagt, dass für Kante e, die von v nach w zeigt, die neue Kantenlänge auf l(e)+h(w)-h(v) gesetzt wird, wobei h eine erstmal (fast) beliebige Funktion ist, die für jeden Knoten eine reelle Zahl ausgibt. Beachtenswert ist nun, dass ein kürzester Pfad vor dieser Modifikation auch danach noch ein kürzester ist und logischerweise umgekehrt. Denn entlang des Pfades rechnen sich beim Addieren der neuen Kantenlängen die h-Werte der inneren Knoten wegen unteschiedlicher Vorzeichen alle heraus, sodass sich die neue Pfadlänge von s nach t nur um +h(t)-h(s) von der alten unterscheidet. Da dieser konstante Zusatz aber auf alle Pfade von s nach t aufaddiert wird, bleibt der kürzeste tatsächlich der kürzeste. Somit kann Dijkstra prinzipiell bedenkenlos auch für die veränderten Kantenlängen verwendet werden, vorausgesetzt die Modifikation lässt alle Kantenlängen weiterhin nichtnegativ (siehe Ungleichung im Wiki).
Was hat das also gebracht? A* soll eingesetzt werden, wenn der kürzeste Pfad von s zu einem bestimmten t (nicht wie bei Dijkstra zu allen andern) gesucht ist. Wenn wir durch unsere künstlichen h-Werte nun Kanten die Richtung t zeigen belohnen (d.h. verkürzen) und andere bestrafen (d.h. verlängern), ist Dijkstra insgesamt hoffentlich schneller, da der Algorithmus ja immer den bisher am schnellsten zu erreichenden noch unbearbeiteten Knoten wählt.

Antworten

Zurück zu „Archiv“