Tiefen- und Breitensuche

Tiefen- und Breitensuche sind Algorithmen, die sich von der allgemeinen Suche in Graphen ableiten. Die beiden Algorithmen verwenden eine Liste als Agenda.

(defclass list-search (search))

(defmethod make-agenda ((this list-search)) t
  nil)

(defmethod is-empty-agenda? ((this list-search) agenda) t
  (null? agenda))

(defmethod head-of-agenda ((this list-search) agenda) t
  (first agenda))

(defmethod tail-of-agenda ((this list-search) agenda) t
  (rest agenda))

Die Methode combine-agenda ist der Teil, der sich zwischen der Tiefen- und der Breitensuche unterscheidet. Sie wird in den Klassen depth-first-search und breadth-first-search überschrieben.

Bei der Tiefensuche werden die neuen Pfade an den Anfang der Agenda gestellt.

(defclass depth-first-search (list-search))

(defmethod combine-agenda ((this depth-first-search) agenda paths) t
  (append paths agenda))

Bei der Beitensuche ist es umgekehrt, die neuen Pfade werden ans Ende der Agenda angehängt.

(defclass breadth-first-search (list-search))

(defmethod combine-agenda ((this breadth-first-search) agenda paths) t
  (append agenda paths))

Die Breitensuche kann beispielsweise verwendet werden, um das Problem der Wasserkrüge zu lösen.


depth-breadth-first-search.sheet.xml