Zustandsraumsuche

Die Zustandsraumsuche ist die systematische Erkundung der Menge von Zuständen, die von einem Anfangszustand aus über verfügbare Aktionen erreichbar sind, um einen Zustand zu finden, der einen Zieltest erfüllt, oder einen Pfad, der zu einem solchen führt.

Definition

Die Zustandsraumsuche behandelt ein Problem als einen Graphen, dessen Knoten Zustände und dessen Kanten Aktionen sind, und geht durch die Expansion von Zuständen von einer Grenze (Frontier) gemäß einer festen Strategie vor, bis ein Zielzustand gefunden oder der Raum erschöpft ist.

Scope

Dieses Thema behandelt die Formulierung eines Problems als Zustandsraum (Zustände, Aktionen, Übergangsmodell, Zieltest, Pfadkosten) und die uninformierten Suchstrategien, die diesen ohne domänenspezifische Anleitung erkunden: Breitensuche, Uniform-Cost-Suche, Tiefensuche, tiefenbeschränkte Suche und iterative Tiefensuche. Es umfasst die Analyse dieser Strategien hinsichtlich Vollständigkeit, Optimalität, Zeitkomplexität und Raumkomplexität sowie die Unterscheidung zwischen Baumsuche und Graphensuche mit Erkennung wiederholter Zustände. Heuristische Führung wird im separaten Thema zur heuristischen Suche und A* behandelt.

Core questions

• Wie wird ein Problem als Zustände, Aktionen, ein Übergangsmodell und ein Zieltest dargestellt?
• Wie unterscheiden sich Breitensuche, Tiefensuche, Uniform-Cost-Suche und iterative Tiefensuche in ihrer Grenzordnung (Frontier Ordering)?
• Welche Vollständigkeits-, Optimalitäts-, Zeit- und Raumgarantien bieten die einzelnen uninformierten Strategien?
• Wie vermeidet die Graphensuche die verschwenderische erneute Erkundung von Zuständen, die die Baumsuche zulässt?

Key concepts

• Anfangszustand und Zieltest
• Übergangsmodell und Nachfolger
• Frontier (offene Liste) und explorierte Menge
• Breitensuche
• Tiefensuche
• Uniform-Cost-Suche
• iterative Vertiefung
• Baumsuche vs. Graphensuche

Key theories

Die Frontier-Ordnung bestimmt die Strategie

Uninformierte Suchalgorithmen unterscheiden sich nur durch die Reihenfolge, in der sie Zustände aus der Frontier entfernen: Eine FIFO-Warteschlange ergibt die Breitensuche, ein LIFO-Stack die Tiefensuche und eine Prioritätswarteschlange basierend auf den Pfadkosten die Uniform-Cost-Suche.

Iterative Vertiefung als speichereffizientes Optimum

Die tiefenbasierte iterative Vertiefung führt wiederholt tiefenbeschränkte Tiefensuchen mit zunehmenden Grenzen durch, wodurch der lineare Speicherplatz der Tiefensuche mit der Vollständigkeit und Optimalität (bei Einheitskosten) der Breitensuche kombiniert wird.

Clinical relevance

Die uninformierte Zustandsraumsuche ist die konzeptionelle und implementatorische Grundlage für Pfadfindung, Rätsellösung, Erreichbarkeitsanalyse im Model Checking und als Substrat, auf dem heuristische und adversarische Suche aufbauen; das Verständnis ihrer Komplexität leitet an, wann eine blinde Suche praktikabel ist und wann Heuristiken erforderlich sind.

History

Die systematische Zustandsraumsuche leitet sich von Graphen-Traversierungsalgorithmen der 1950er Jahre ab, einschließlich Moores und Dijkstras Arbeiten zum kürzesten Pfad, und wurde in der frühen KI als Modell der Problemlösung formuliert. Korfs Analyse der iterativen Vertiefung von 1985 etablierte deren Optimalität unter zulässigen Baum-Suchen mit linearem Speicherplatz.

Key figures

• Nils J. Nilsson
• Richard E. Korf
• Edward F. Moore
• Edsger W. Dijkstra

Seminal works

• nilsson1971
• russell2020

Frequently asked questions

Wann ist die Breitensuche optimal?

Die Breitensuche ist optimal, wenn jeder Schritt die gleichen Kosten hat, da sie zuerst das flachste Ziel findet. Wenn die Schrittkosten variieren, ist die Uniform-Cost-Suche (die die Frontier nach den akkumulierten Pfadkosten ordnet) die uninformierte Strategie, die eine kostengünstigste Lösung garantiert.

Warum sollte man iterative Vertiefung anstelle einer einfachen Breitensuche verwenden?

Die Breitensuche speichert die gesamte Frontier und kann einen exponentiellen Speicherbedarf in Bezug auf die Tiefe haben. Die iterative Vertiefung führt wiederholt Tiefensuchen mit wachsenden Tiefenbegrenzungen durch, wobei sie nur linearen Speicherplatz benötigt und dennoch vollständig und optimal bei Problemen mit Einheitskosten ist, allerdings auf Kosten der erneuten Expansion flacher Knoten.