10.2 Sequentielles Suchen

Die Organisation der Suche hängt davon ab, ob der Zustandsraum einen Graphen bildet oder einen Baum. Beim Baum kann ein Zustand nur über einen Weg erreicht werden (z.B. 0/1 -Integer-Linear-Programming), beim Graphen gibt es mehrere Wege zu einem Zustand, und es muß überprüft werden, ob der Zustand bereits erzeugt wurde.

Backtracking ist eine Tiefensuche, die bei der ersten zulässigen Lösung endet. Bei geordnetem Backtracking wird die Reihenfolge beim Besuchen der Söhne eines Knotens durch eine Heuristik bestimmt.

Depth-First Branch- & -Bound ist eine Tiefensuche, die den Zustandsraum abläuft und dabei aufgrund einer Schätzung solche Teile ausläßt, die die momentan vorhandene Lösung nicht verbessern können.

Iterative Deepening ist eine tiefenbeschränkte Tiefensuche, bei der die maximale Tiefe schrittweise erhöht wird. D.h., wurde innerhalb der Suchtiefe k keine zulässige Lösung gefunden, so wird eine komplett neue Suche gestartet mit einer größeren Suchtiefe, z.B. k + 1 . Auf diese Weise wird eine Lösung mit den wenigsten Kanten gefunden, aber nicht notwendigerweise mit dem billigsten Weg.

Iterative Deepening A ^* (IDA ^* ) benutzt die l -Werte der Knoten (d.h. g(x) + h(x) ), um die Suche zu begrenzen. Es wird eine Tiefensuche durchgeführt mit einer vorgegebenen Kostenschranke b . Falls l (x) > b , so wird nicht weiter expandiert. Wird keine Lösung innerhalb der momentanen Kostenschranke gefunden, wird eine neue Suche mit einer größeren Kostenschranke gestartet. Die erste Kostenschranke ist l (s) mit s = Startknoten. Wegen g(s) = 0 folgt l (s) = h(s) . Das Minimum der l -Werte der erzeugten, aber wegen der Kostenschranke nicht weiter verfolgten Knoten aus Suche i wird zur Kostenschranke für Suche i + 1 . Falls h zulässig ist, so findet IDA ^* das Optimum.

Teil des Zustandsraums bei Tiefensuche für ein 8-Puzzle-Problem

Zur Verwaltung der Tiefensuche bietet sich ein Keller an, auf dem die unbesuchten Alternativen zusammen mit ihren Vaterknoten abgelegt sind.

Zustandsgraph und Kellerinhalt bei Tiefensuche

Best First Search operiert nicht wie Depth First Search am letzten besuchten Knoten, sondern an dem Knoten mit der größten Erfolgsaussicht. Hierfür entsteht Speicherbedarf proportional zur Größe des durchsuchten Zustandsraums.
Der A ^* -Algorithmus expandiert jeweils den Knoten mit dem niedrigsten l -Wert. Dessen Söhne kommen auf die sogenannte OPEN-List (es sei denn, sie befinden sich bereits dort), der expandierte Knoten kommt auf die CLOSED-List (es sei denn, er befindet sich bereits dort).