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.
(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.