Problemrepräsentation

Problemrepräsentation bezeichnet in der Informatik und Kognitionswissenschaft die Art und Weise, wie ein Problem formal beschrieben wird, um es durch Algorithmen lösen zu können. Sie bestimmt, welche Zustände, Operationen und Kosten zur Verfügung stehen und wie der Lösungsraum aufgebaut ist.

Zentrale Bausteine sind der Anfangszustand, das Zielkriterium, die Operatoren bzw. Aktionen, sowie der Zustandsraum bzw. der Übergangsmechanismus. Oft werden zusätzlich Kostenfunktionen, Randbedingungen und Nebenbedingungen modelliert. Die Wahl der Repräsentation beeinflusst, wie groß der Suchraum erscheint und welche Heuristiken sinnvoll sind.

Gängige Repräsentationen umfassen graphenbasierte Modelle (Zustandsgraphen oder Suchbäume), relationale oder logische Beschreibungen (z. B. Prädikatenlogik), funktionale oder numerische Modelle und produktionelle Systeme (STRIPS-ähnliche Boards). In vielen Aufgaben wird der Zustand durch eine strukturierte Datenmenge beschrieben, etwa Matrizen oder Objekte, während Aktionen als Übergänge zwischen Zuständen modelliert werden.

Ein praxisnahes Beispiel ist das 8-Puzzle: Der Zustand ist die Anordnung der Kacheln, die Aktionen Bewegungen einer leeren Kachel, das Ziel die korrekte Endanordnung. Die Darstellung beeinflusst, welche Suchalgorithmen (Breitensuche, A*-Suche) und Heuristiken verwendet werden können.

Wichtige Herausforderungen umfassen Abstraktion und Generalisierung, Reduktion überflüssiger Details, Beibehaltung Korrektheit (Korrektheit, Vollständigkeit, Optimalität), sowie die Berücksichtigung von Domänenwissen, um den Suchaufwand zu verringern. Eine gute Problemrepräsentation erleichtert das Auffinden von Lösungen und die Anwendung von heuristischen Verfahren.