A* Suche

Die A* Suche ist eine Variante der Bestensuche, bei der die Heuristik für die Steuerung der Suche auf der Entfernung zum Ziel basiert.

(defclass a*-search (best-first-search))

(defmethod compare-paths ((this a*-search) path-1 path-2)
  t
  (< (estimate-total-length this path-1)
     (estimate-total-length this path-2)))

(defmethod estimate-total-length ((this a*-search) path)
  t
  (+ (path-length this path)
     (estimate-distance-to-goal this (end-of-path this path))))

Die Methode path-length liefert einen Zahlenwert, der die Weglänge des übergebenen Pfades repräsentiert. Die Methode muss von einer Subklasse überschrieben werden.

(defmethod path-length ((this a*-search) path)
  t
  (throw (quote error) "must override"))

Die Methode estimate-distance-to-goal liefert einen Zahlenwert, der die Entfernung vom übergebenen Zustand bis zum Ziel unterschätzt. Auch diese Methode muss von einer Subklasse überschrieben werden.

(defmethod estimate-distance-to-goal ((this a*-search) node)
  t
  (throw (quote error) "must override"))

Erfolgreich angewendet werden kann die A* Suche zum Beispiel auf das 8 Puzzle, da es bei diesem eine gute Heuristik für die Enfernung zum Ziel gibt.


astar-search.sheet.xml