Constraint-Satisfaction-Problem
Aus Wikipedia, der freien Enzyklopädie
Aus Wikipedia, der freien Enzyklopädie
Ein Constraint-Satisfaction-Problem (CSP; deutsch: Bedingungserfüllungsproblem) ist eine Aufgabenstellung aus der künstlichen Intelligenz und aus dem Operations Research. Aufgabe ist es, einen Zustand (d. h. Belegungen von Variablen) zu finden, der alle aufgestellten Bedingungen (Constraints) erfüllt.
Ein Constraint-Satisfaction-Problem besteht aus einer Menge von Variablen, ihren Wertebereichen und den Bedingungen, die Verknüpfungen zwischen den Variablen herstellen und dadurch festlegen, welche Kombinationen von Werten der Variablen zulässig sind. Auf diese Weise lassen sich eine Vielfalt von Problemen aus Informatik, Mathematik und weiteren Anwendungsgebieten formulieren. Einfache Beispiele für solche Probleme sind das Damenproblem, das Vier-Farben-Problem, Sudoku, Str8ts oder das Erfüllbarkeitsproblem der Aussagenlogik (SAT bzw. SAT-k), Erfüllbarkeitsproblem für quantifizierte boolesche Formeln, Graphenfärbung oder Erfüllbarkeitsproblem für Schaltkreise, aber auch physikalische Probleme wie das Isingmodell und andere Spinmodelle auf Gittern. Dem entspricht in der elementaren Mathematik das Lösen einer Gleichung oder eines Gleichungssystems – als Constraint-Satisfaction-Probleme bezeichnet man speziell die Fragestellungen, die sich analytisch so nicht oder nur aufwändig lösen lassen.
Ein CSP wird gelöst, indem eine Belegung der Variablen gefunden wird, die allen Bedingungen genügt. Im Unterschied zu anderen Optimierungsproblemen, in denen eine „möglichst gute“ Lösung gesucht wird, fordern Constraint-Satisfaction-Probleme eine vollständige Erfüllung jeder einzelnen Vorbedingung. Sind die aufgestellten Bedingungen widersprüchlich, so gibt es keine Lösung des Problems (respektive umgekehrt: gibt es nachweislich keine Lösung, sind die Vorbedingungen als unvereinbar bewiesen). Es kann aber durchaus mehrere oder viele Lösungen geben. Gibt es nur eine, spricht man wie bei anderen Optimierungsfragen von einer „eindeutigen Lösung“ und bei dem entsprechenden SAT-Problem zu entscheiden, ob es nur eine Lösung gibt von unique SAT.
Constraint-Satisfaction-Probleme werden in verschiedene Beschränkungs- bzw. Bedingungstypen unterteilt:
Zur Lösung von Constraint-Satisfaction-Problemen werden verschiedene Ansätze kombiniert:
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.
Beispiele für Algorithmen, die sich besonders für die Lösung von Constraint-Satisfaction-Problemen eignen, sind der AC-3-Algorithmus, Backtracking oder die Min-Conflict-Heuristik.
Die CSP sind ein häufiger Testboden für Methoden der Komplexitätstheorie. Für die Komplexität in einer breiten Klasse von CSP-Abzählproblemen wurde 2021 der Gödel-Preis an Andrei Bulatov, Martin Dyer, David Richerby, Jin-Yi Cai und Xi Chen verliehen. Die Dichotomie besteht darin, dass sie entweder in Polynomzeit lösbar sind oder Sharp-P-schwer sind.[1]
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.