Suche und Problemlösung
Suche und Problemlösung ist der Zweig der künstlichen Intelligenz, der sich mit der Formulierung von Aufgaben als Exploration eines Zustands- oder Konfigurationsraums und dem Finden von Aktionssequenzen, Zuweisungen oder Zügen befasst, die ein Ziel erreichen.
Definition
Suchbasiertes Problemlösen stellt eine Aufgabe als einen Anfangszustand, eine Menge von Aktionen, die Zustände transformieren, einen Zieltest und Pfadkosten dar und löst sie durch systematisches Explorieren der erreichbaren Zustände, bis ein Zielzustand (oder ein Pfad mit den geringsten Kosten zu diesem) gefunden wird.
Scope
Dieser Bereich umfasst die Formulierung von Problemen als Zustandsräume und die Algorithmen, die diese explorieren: uninformierte (blinde) Suche wie Breitensuche und Tiefensuche, informierte (heuristische) Suche wie A* und Greedy Best-First, adversarische Suche für Zwei-Spieler-Spiele und Constraint Satisfaction. Es behandelt, wie Probleme als Zustände, Aktionen und Zieltests modelliert werden und wie Vollständigkeit, Optimalität, Zeit und Raum analysiert werden. Ausgeschlossen ist das Lernen von Suchheuristiken oder Bewertungsfunktionen aus Daten, das zum separaten Unterfeld des maschinellen Lernens gehört.
Sub-topics
Core questions
- Wie wird eine reale Aufgabe als Zustandsraum mit Zuständen, Aktionen und einem Zieltest formuliert?
- Wann ist ein Suchalgorithmus vollständig (garantiert eine Lösung zu finden, wenn eine existiert) und optimal (garantiert eine Lösung mit den geringsten Kosten zu finden)?
- Wie leitet eine heuristische Funktion die Suche zum Ziel, während die Optimalität erhalten bleibt?
- Wie kann die kombinatorische Explosion des Zustandsraums durch Beschneiden oder informierte Anordnung kontrolliert werden?
- Wie ändert sich die Suche, wenn ein Gegner einige der Züge wählt?
Key concepts
- Zustandsraum
- Suchbaum und Suchgraph
- uninformierte (blinde) Suche
- heuristische Funktion
- Zulässigkeit und Konsistenz
- A*-Suche
- Verzweigungsfaktor und Suchtiefe
- Vollständigkeit und Optimalität
- Constraint Satisfaction
Key theories
- Zulässige Heuristiken und A*-Optimalität
- Wenn eine Heuristik die wahren Kosten zum Ziel niemals überschätzt (zulässig ist), erweitert die A*-Suche Knoten in der Best-First-Reihenfolge von f = g + h und liefert garantiert eine optimale Lösung; Konsistenz garantiert zusätzlich, dass kein Knoten erneut erweitert wird.
- Kompromiss zwischen uninformierter und informierter Suche
- Blinde Strategien (Breitensuche, Uniform-Cost-Suche, Tiefensuche, iterative Vertiefung) unterscheiden sich nur in der Knotenreihenfolge und bieten Garantien ohne Domänenwissen, während heuristische Schätzungen der verbleibenden Kosten den explorierte Raum drastisch reduzieren können, mit dem Risiko, die Optimalität zu verlieren, wenn die Heuristik unzulässig ist.
- Problemformulierung als Zustandsraumsuche
- Eine Vielzahl von Aufgaben wird lösbar, sobald sie als Suche über Zustände, die durch Aktionen verbunden sind, formuliert werden, wodurch die Wahl der Zustandsrepräsentation und der Operatoren zu einer zentralen Designentscheidung wird, die den Verzweigungsfaktor und die Lösungstiefe bestimmt.
Clinical relevance
Die Suche ist die Grundlage einer Vielzahl praktischer Systeme: Routenplanung und Navigation (A* in Straßennetzen), Puzzle- und Spiel-Engines, automatisierte Konfiguration und Zeitplanung, Roboterbewegungsplanung und als Rückgrat automatischer Planungs- und Constraint-Solver, die in Logistik und Operations Research eingesetzt werden.
History
Die Suche war von Anfang an zentral für die KI, wobei Newell und Simons General Problem Solver (späte 1950er Jahre) Intelligenz als Suche durch Problemräume definierte. Der A*-Algorithmus (Hart, Nilsson, Raphael, 1968) verlieh der heuristischen Suche eine rigorose Optimalitätsgrundlage, und Pearls Monographie von 1984 systematisierte die Theorie der heuristischen Suche. Der Rahmen bleibt eine Standard-Organisationslinse in KI-Lehrbüchern.
Key figures
- Nils J. Nilsson
- Judea Pearl
- Peter E. Hart
- Bertram Raphael
- Allen Newell
- Herbert A. Simon
Related topics
Seminal works
- hart1968
- pearl1984
- russell2020
Frequently asked questions
- Was ist der Unterschied zwischen uninformierter und informierter Suche?
- Uninformierte (blinde) Suche, wie z. B. Breitensuche oder Tiefensuche, verwendet keine Informationen darüber, wie nah ein Zustand am Ziel ist, und exploriert rein nach der Struktur des Zustandsraums. Informierte (heuristische) Suche verwendet eine Schätzung der verbleibenden Kosten zum Ziel, um zu priorisieren, welche Zustände erweitert werden sollen, was weitaus effizienter sein kann.
- Warum wird A* so häufig verwendet?
- A* kombiniert die tatsächlichen Kosten vom Start (g) mit einer heuristischen Schätzung zum Ziel (h), und wenn die Heuristik zulässig ist, findet sie garantiert eine optimale Lösung, während sie typischerweise weitaus weniger Zustände exploriert als die uninformierte Suche. Dieses Gleichgewicht aus Optimalität und Effizienz macht sie zu einer Standardwahl für die Pfadfindung.