Constraint Satisfaction Problem
aus Wikipedia, der freien Enzyklopädie
 |
Dieser Artikel oder Abschnitt weist folgende Lücken auf:
Hilf Wikipedia, indem du die fehlenden Informationen recherchierst und einfügst! |
--Jörgens.Mi Diskussion 20:02, 18. Feb 2006 (CET)
Das Constraint-Satisfaction-Problem (Bedingungerfüllungsproblem) ist eine Aufgabenstellung aus der künstlichen Intelligenz und aus Operations Research. Aufgabe ist es, einen Zustand zu finden, der alle aufgestellten Bedingungen (Constraints) erfüllt.
Ein Constraint-Satisfaction-Problem besteht aus einer Menge von Variablen, ihrer Wertebereiche und Bedingungen (Constraints) zwischen diesen Variablen. Die Bedingungen legen fest, welche Kombinationen von Werten der Variablen zulässig sind. Auf diese Weise lassen sich eine Vielfalt von Problemen aus Informatik, Mathematik und weiteren Anwendungsgebieten (um)formulieren. Das Problem wird gelöst, indem eine Belegung der Variablen gefunden wird, die alle Constraints erfüllt. Sind die aufgstellten Constraints widersprüchlich, so gibt es keine Lösung des Problems.
Zur Lösung von Constraint-Satisfaction-Problemen werden verschiedenen Ansätze kombiniert:
- Aus bestehenden Constraints werden neue Constraints berechnet, die den Wertebereich von Variablen zusätzlich einschränken oder zu einem Widerspruch führen.
- Im Lösungsraum der Variablen wird systematisch nach einer Lösung gesucht.
Grundsätzlich können für die Lösung von CSPs allgemeine Suchalgorithmen verwendet werden. Allerdings lässt die Besonderheit der Problemklasse Algorithmen zu, die um einiges effizienter arbeiten als allgemeine Suchalgorithmen.
- Zustände sind durch Werte von Variablen definiert.
- Operatoren belegen eine Variable mit einem Wert
- Der Zieltest wird durch Constraints(Bedingungen) spezifiziert, welche die Variablenbelegungen erfüllen müssen
- Ein Zielzustand ist eine Belegung der Variablen mit Werten, die alle Constraints erfüllen
