Das erste Beispiel ist in Anlehnung an den Text von Bortfeldt entwickelt.
Das Problem beim A* - Algorithmus ist, eine angemessene Schätzfunktion für die restliche Länge des Weges von einer Ecke zu einer Zielecke des Graphen zu finden. Wie schon vorher angemerkt: Es gibt nämlich nicht die richtige Schätzfunktion. Beachten Sie, dass die Schätzfunktion optimistisch sein muss, d.h. sie darf die Kosten keinesfalls zu hoch schätzen!
Beim 8-Puzzle sind die Kosten sehr einfach zu definieren: Jede Verschiebung hat den Wert 1. Hat man von der Ausgangsstellung zu einer Zwischenstellung also beispielsweise 5 Verschiebungen durchgeführt, dass ist der Wert von g(n) = 5. Braucht man nach der Schätzung noch 4 weitere Verschiebungen, dann ist der Wert der geschätzten Restkosten h(n) = 4 und damit f(n) = 9. Beachten Sie, dass der "richtige" Wert auch 10, 11, ... sein kann. |
|
Das Beispielprogramm verwendet die zweite Variante. Es ist nach bei Bortfeldt angegegebenen Daten etwas günstiger als das erste.