Uninformierte Suche

Die gemeinsame Beschränkung

Diese Verfahren können einen Zustand nicht danach beurteilen, wie vielversprechend er ist. Sie erkunden den Raum nach einem festen Muster, bis sie zufällig auf das Ziel stoßen. Der Unterschied zwischen ihnen liegt allein darin, welchen Knoten sie als Nächsten von der Grenze nehmen.

Breitensuche

Sie expandiert zuerst alle Knoten der aktuellen Tiefe, dann die der nächsten — Ebene für Ebene. Damit findet sie garantiert die Lösung mit den wenigsten Schritten. Der Preis ist der Speicher: Sie muss die gesamte Ebene vorhalten, was mit jeder Tiefenstufe um den Verzweigungsfaktor wächst. Dieser Speicherbedarf, nicht die Rechenzeit, ist in der Praxis die Grenze.

Tiefensuche

Sie verfolgt einen Zweig bis zum Ende, bevor sie zurückgeht und den nächsten probiert. Ihr Vorteil ist der geringe Speicherbedarf: Nur der aktuelle Pfad muss vorgehalten werden. Dafür ist sie weder vollständig noch kostenoptimal — in einem unendlichen Zweig läuft sie beliebig lange weiter, und der erste gefundene Weg muss nicht der kürzeste sein.

Uniforme Kostensuche

Sie expandiert stets den Knoten mit den geringsten bisherigen Pfadkosten. Damit findet sie auch dann die günstigste Lösung, wenn die Schritte unterschiedlich teuer sind. Dieses Verfahren ist unter dem Namen seines Erfinders bekannter: Es ist der Algorithmus von Dijkstra (1959).

Iterative Vertiefung

Der verbreitete Kompromiss führt wiederholt eine Tiefensuche mit wachsender Tiefenbeschränkung aus: erst bis Tiefe 1, dann bis 2, und so fort. Das wirkt verschwenderisch, ist es aber kaum — der weitaus größte Teil der Knoten liegt ohnehin in der untersten Ebene. So verbindet das Verfahren den geringen Speicherbedarf der Tiefen- mit der Vollständigkeit der Breitensuche.

Abgrenzung

Sobald eine Schätzung der Restentfernung zur Verfügung steht, lässt sich die Suche gezielt lenken — das leistet eine Heuristik, und darauf beruht die A*-Suche.