Der Zustandsraum ist die Menge aller Zustände, die ein Problem annehmen kann, zusammen mit den Übergängen zwischen ihnen. Ein Problem in dieser Form zu beschreiben, ist die Voraussetzung dafür, es durch Suchen zu lösen.
Ein Zustand ist eine Momentaufnahme der Situation — vollständig, soweit sie für das Problem zählt. Bei einer Routenplanung ist das der Ort, an dem man sich befindet; beim Schiebepuzzle die Anordnung der Steine; bei einem Schachspiel die Stellung auf dem Brett. Alles, was für die Lösung keine Rolle spielt, gehört nicht dazu.
Ein Suchproblem ist vollständig beschrieben durch fünf Angaben: den Anfangszustand, die in einem Zustand möglichen Aktionen, das Übergangsmodell (welcher Zustand aus einer Aktion folgt), den Zieltest und die Aktionskosten. Anfangszustand, Aktionen und Übergangsmodell spannen zusammen den Zustandsraum auf.
Der Zustandsraum lässt sich als Graph darstellen: Die Knoten sind Zustände, die gerichteten Kanten sind Aktionen. Eine Lösung ist dann ein Pfad vom Anfangs- zu einem Zielzustand; eine kostenoptimale Lösung ist der Pfad mit den geringsten Gesamtkosten.
Schon kleine Probleme spannen sehr große Räume auf. Das 8-Puzzle hat rund 180.000 erreichbare Zustände, das 15-Puzzle bereits etwa 10 Billionen. Beim Schach übersteigt die Zahl möglicher Stellungen die Zahl der Atome im beobachtbaren Universum bei Weitem. Deshalb wird der Zustandsraum nie vollständig aufgeschrieben, sondern während der Suche stückweise erzeugt.
Jede Problemformulierung lässt Einzelheiten weg. Bei einer Routenplanung wird eine Fahrt zu einer Kante mit einer Zahl daran — Wetter, Mitreisende, Straßenzustand entfallen. Diese Abstraktion ist keine Nachlässigkeit, sondern notwendig: Ohne sie wäre der Raum nicht handhabbar. Die Kunst besteht darin, genau so viel wegzulassen, dass die Lösung im abstrakten Raum noch einer Lösung in der Wirklichkeit entspricht.
Der Zustandsraum ist nicht auf Landkarten und Schiebepuzzles beschränkt. Auch die Zugfolgen eines Spiels, die Belegungen eines Stundenplans oder die Wirkstoffkandidaten einer Molekülsuche bilden Zustandsräume. Auch Bestärkendes Lernen stützt sich auf denselben Begriff: Der Zustandsraum beschreibt dort die Umgebung, in der ein Agent handelt.
Hallo! Ich bin dein KI-Tutor.
Melde dich an, um mit mir zu chatten — ich erinnere mich dann auch an eure letzten Gespräche.
