Bestensuche

Die Bestensuche ist ein Algorithmus, der sich von der allgemeinen Suche in Graphen ableitet.

(defclass best-first-search (search))

Die Bestensuche unterscheidet sich von Tiefen- und Breitensuche durch eine andere Reihenfolge, in der die Knoten besucht werden. Deshalb verwendet die Bestensuche keine Liste als Agenda, sondern eine Prioritätswarteschlange (hier ein Pairing Heap).
 
(defmethod make-agenda ((this best-first-search))
  t
  (new pairing-heap (curry (compare-paths this _ _))))

(defmethod is-empty-agenda? ((this best-first-search) (agenda pairing-heap))
  t
  (is-empty? agenda))

(defmethod head-of-agenda ((this best-first-search) (agenda pairing-heap))
  t
  (head agenda))

(defmethod tail-of-agenda ((this best-first-search) (agenda pairing-heap))
  t
  (tail agenda))

(defmethod combine-agenda ((this best-first-search) (agenda pairing-heap) paths)
  t
  (dolist (path paths agenda)
    (setq agenda (insert-into agenda path))))

Die Methode compare-paths bestimmt die Richtung der Suche. Wenn die Methode t oder einen anderen Wert ungleich nil als Resultat liefert, wird path-1 vor path-2 von der Suche berücksichtigt. Diese Methode muss in einer Subklasse überschrieben werden. Typischerweise werden nur die Enden der Pfade für den Vergleich herangezogen.

(defmethod compare-paths ((this best-first-search) path-1 path-2)
  t
  (throw (quote error) "must override"))

Wie bei allen Anwendungen der allgemeinen Suche müssen die Methoden get-start-node, get-next-nodes und is-goal-node? in einer Subklasse überschrieben werden, denn diese spezifizieren das konkrete, zu lösende Problem. Die Suche wird von der Methode find-path durchgeführt.


best-first-search.sheet.xml