Es gibt mehrere Varianten der Suche in Graphen:

- die Tiefen- und Breitensuche,
- die Bestensuche und
- die A* Suche.

Das Grundprinzip aller Varianten ist gleich, deshalb bietet sich das Template Method Pattern für die Realisierung an. Der gemeinsame Teil der Algorithmen wird als Methoden für die Klasse search definiert.

(defclass search ())

Die drei Methoden get-start-node, get-next-nodes und is-goal-node? dienen dazu, den Startknoten, den Graph und die Zielknoten festzulegen. Sie müssen für die Anwendung des Suchalgorithmus in einer Subklasse überschrieben werden.

(defmethod get-start-node ((this search)) t
  (throw nil "must override"))

(defmethod get-next-nodes ((this search) node) t
  (throw nil "must override"))

(defmethod is-goal-node? ((this search) node) t
  (throw nil "must override"))

Die folgenden vier Methoden legen die Repräsentation von Pfaden fest - eine Liste von Knoten in umgekehrter Reihenfolge. Das heißt, dass der Endknoten des Pfads das erste Element der Liste ist.

(defmethod make-singleton-path ((this search) node) t
  (list node))

(defmethod extend-path ((this search) path node) t
  (cons node path))

(defmethod end-of-path ((this search) path) t
  (first path))

(defmethod is-cyclic-path? ((this search) path) t
  (member? (first path) (rest path)))

Die Suche basiert auf einer Agenda. Sie enthält die Pfade, die noch untersucht werden müssen.

Die Realisierungen der Agenda unterscheiden sich in den verschiedenen Varianten der Suche. Die Methoden zum Umgang mit der Agenda sind deswegen hier abstrakt. Sie werden in Subklassen überschrieben.

Eine leere Agenda wird von der Methode make-agenda erzeugt. Die Methode combine-agenda kombiniert eine Agenda und eine Liste von Pfaden. Die Methoden is-empty-agenda?, head-of-agenda und tail-of-agenda werden benutzt, wenn die Suche die Agenda abarbeitet.

(defmethod make-agenda ((this search)) t
  (throw nil "must override"))

(defmethod combine-agenda ((this search) agenda paths) t
  (throw nil "must override"))

(defmethod is-empty-agenda? ((this search) agenda) t
  (throw nil "must override"))

(defmethod head-of-agenda ((this search) agenda) t
  (throw nil "must override"))

(defmethod tail-of-agenda ((this search) agenda) t
  (throw nil "must override"))

In jedem Schritt wird ein Pfad aus der Agenda entnommen. Dann wird geprüft, ob das Ziel erreicht ist oder der Pfad eine Schleife bildet (den selben Knoten zwei mal enthält). Wenn beides nicht zutrifft, werden neue Pfade berechnet. Das passiert, indem der aktuelle Pfad um mögliche Folgeknoten erweitert wird. Die neuen Pfade werden zur Agenda hinzugefügt.

(defmethod find-path ((this search)) t
  (find-path
     this
     (combine-agenda
       this
       (make-agenda this)
       (list (make-singleton-path this (get-start-node this))))))

(defmethod find-path ((this search) agenda) t
  (unless (is-empty-agenda? this agenda)
    (let
      ((path (head-of-agenda this agenda)))
      (cond
        ((is-goal-node? this (end-of-path this path))
          path)
        ((is-cyclic-path? this path)
          (find-path this (tail-of-agenda this agenda)))
        (t
          (find-path this
            (combine-agenda this
              (tail-of-agenda this agenda)
              (map-with
                (curry (extend-path this path _))
                (get-next-nodes this (end-of-path this path))))))))))