Suchalgorithmus

Der Suchbaum

Über den Zustandsraum legt der Algorithmus einen Suchbaum: Die Wurzel ist der Anfangszustand, jeder Zweig ein möglicher Pfad. Zustandsraum und Suchbaum sind nicht dasselbe — derselbe Zustand kann im Baum mehrfach auftauchen, wenn mehrere Wege zu ihm führen.

Der Arbeitsschritt

Das Verfahren führt eine Menge von Knoten, die erzeugt, aber noch nicht weiterverfolgt wurden; Russell und Norvig nennen sie die Grenze (englisch frontier). In jedem Schritt wird ein Knoten von der Grenze genommen und expandiert: Seine Nachfolger werden erzeugt und der Grenze hinzugefügt. Welchen Knoten die Wahl trifft, ist der einzige Unterschied zwischen den Verfahren — und macht ihre gesamte Charakteristik aus. Bereits erreichte Zustände werden vermerkt, damit das Verfahren nicht im Kreis läuft.

Die vier Beurteilungsmaße

Ein Suchverfahren wird an vier Eigenschaften gemessen. Vollständigkeit: Findet es eine Lösung, wenn eine existiert? Kostenoptimalität: Findet es die günstigste? Zeitkomplexität und Speicherkomplexität: Wie viele Knoten muss es erzeugen und gleichzeitig vorhalten? Angegeben werden die letzten beiden über den Verzweigungsfaktor (die mittlere Zahl der Nachfolger je Knoten) und die Lösungstiefe.

Zwei Familien

Verfahren, die nur die Problemdefinition nutzen, heißen uninformiert (siehe Uninformierte Suche). Verfahren, die zusätzlich eine Schätzung der Restentfernung heranziehen, heißen informiert oder heuristisch; ihr bekanntester Vertreter ist die A*-Suche.

Einordnung

Suchen ist der algorithmische Kern der klassischen, regelbasierten KI, wie sie die Symbolische KI verfolgt. Anders als Maschinelles Lernen lernt ein Suchverfahren nichts aus Daten: Das Verfahren rechnet die Lösung aus, sobald das Problem sauber beschrieben ist. Beide Ansätze stehen heute nebeneinander, und moderne Systeme verbinden sie: AlphaGo etwa kombiniert Baumsuche mit gelernten Bewertungsfunktionen.