vorige nächste

Das Verfahren


Beim A* - Algorithmus bedient man sich einer Schätzfunktion für die restliche Länge des Weges von einer Ecke zu einer Zielecke des Graphen. Schätzfunktion bedeutet, dass man nicht die tatsächliche restliche Länge bestimmen kann und muss. Die Berechnung darf nicht ein "Ablaufen" des Graphen Ecke für Ecke bis zum Ziel notwendig machen, dann hätte man nichts gewonnen!

Sie muss allein aus den Zuständen der aktuellen Ecke und der Zielecke im Graphen zu bestimmen sein. Ein Beispiel beim tsp: Man verwende einfach die Luftliniendistanz zum Ziel.

Die Bewertungsfunktion hat die Form

f = g + h

Dabei gibt es für jeden Randpunkt des Expansionsgraphen einen Wert, man kann daher auch f(n) = g(n) + h(n) schreiben und meint mit dem n einen Index über die o.a. Punkte.

Die Bedeutung von g und h ist einfach nachvollziehbar, da sich die Werte der Bewertungsfunktion aus den beiden Anteilen g(n) der Kosten des speziellen Knoten im schon expandierten Teil und dem Wert für den Rest zusammensetzen. [Einerseits haben alle Knoten, von denen aus wir weiter gehen können, verschiedenen "Vorlauf", so dass sich die Bewertungsfunktionswerte in diesem Abschnitt bereits unterscheiden, andererseits ist der Weg zum Ziel von diesen aus ebenfalls unterschiedlich, so dass auch noch im unbekannten Teil des Gesamtweges für jeden Knoten andere Werte zu berücksichtigen sind.]

Wenn man nun diese Werte zu jedem Knoten exakt kennen würde, hätte man eine ideale Funktion f. Statt dessen hat man aber für den noch unbekannten Rest nur den Schätzwert h(n). In ihr liegt auch der Freiraum -nicht nur des Verfahrens- sondern auch im Geschick des Anwenders. Es gibt nämlich nicht die richtige Schätzfunktion.
Wie erfolgreich dieses Verfahren ist, hängt natürlich entscheidend von der Güte der Restkostenfunktion ab. Erstaunlicherweise darf sie keinesfalls die Kosten zu hoch schätzen!