Philosophie Lexikon der Argumente

Home Screenshot Tabelle Begriffe

 
Constraint-Satisfaction-Problem: In der Informatik ist ein Constraint-Satisfaction-Problem (CSP) ein Problem, bei dem wir eine Reihe von Variablen und eine Reihe von Beschränkungen haben, die angeben, welche Werte die Variablen annehmen können. Das Ziel ist es, eine Zuordnung von Werten zu den Variablen zu finden, die alle Beschränkungen erfüllt.

_____________
Anmerkung: Die obigen Begriffscharakterisierungen verstehen sich weder als Definitionen noch als erschöpfende Problemdarstellungen. Sie sollen lediglich den Zugang zu den unten angefügten Quellen erleichtern. - Lexikon der Argumente.

 
Autor Begriff Zusammenfassung/Zitate Quellen

Peter Norvig über Constraint-Satisfaction-Probleme – Lexikon der Argumente

Norvig I 202
Constraint-Satisfaction-Probleme/CSP/künstliche Intelligenz/Norvig/Russell: Problem: Wenn jeder Zustand atomar oder unsichtbar ist - eine Blackbox ohne interne Struktur, können Probleme [nur] durch Suchen in einem Raum von Zuständen gelöst werden. Diese Zustände können durch domänenspezifische Heuristiken evaluiert und daraufhin getestet werden, ob es sich um Zielzustände handelt.
Lösung: Wir verwenden eine gewichtete Darstellung für jeden Zustand: einen Satz von Variablen, von denen jede einen Wert hat. Ein Problem ist gelöst, wenn jede Variable einen Wert hat, der alle Constraints der Variable erfüllt. CSP-Suchalgorithmen nutzen die Struktur von Zuständen und verwenden eher allgemeine als problemspezifische Heuristiken, um die Lösung komplexer Probleme zu ermöglichen. Die Grundidee ist es, große Teile des Suchraums auf einmal zu eliminieren, indem man Variablen-Wert-Kombinationen identifiziert, die gegen die Constraints verstoßen.
Ein Constraint-Satisfaction-Problem besteht aus drei Komponenten, X, D und C:
X ist ein Satz von Variablen, {X1, .....]. ,Xn}.
D ist ein Satz von Domänen, {D1, . .... ,Dn}, eine für jede Variable.
C ist eine Reihe von Constraints, die zulässige Kombinationen von Werten festlegen.
Norvig I 203
Es kann hilfreich sein, einen CSP als Constraint-Graphen zu visualisieren, (...) Die Knoten des Graphen entsprechen den Variablen des Problems, und ein Link verbindet zwei beliebige Variablen, die an einem Constraint teilnehmen. Wenn wir z.B. im [Kartenfärbungs-]Problem [eine Farbe] gewählt haben, können wir feststellen, dass keine der fünf benachbarten Variablen den Wert[der gleichen Farbe] annehmen kann.
Norvig I 205
Problem: Eine diskrete Domäne kann unendlich sein, wie beispielsweise die Menge der ganzen Zahlen oder Zeichenketten.
Lösung: Es muss eine Constraintsprache verwendet werden, die Constraints (...) direkt versteht, ohne das Set von Paaren zulässiger Werte (...) aufzulisten. Spezielle Lösungsalgorithmen (...) existieren für lineare Constraints ganzzahliger Variablen, d.h. Constraints, (...), bei denen jede Variable nur in linearer Form erscheint.
Problem: Es kann gezeigt werden, dass kein Algorithmus zur Lösung allgemeiner nichtlinearer Constraints für ganzzahlige Variablen existiert.
Norvig I 206
Continuous domains: Constraint-Satisfaction-Probleme mit continuous domains sind in der realen Welt weit verbreitet und werden im Forschungsfeld der Operations Research (Operationsforschung) umfassend untersucht. So erfordert beispielsweise die Planung von Experimenten auf dem Hubble-Weltraumteleskop ein sehr genaues Timing der Beobachtungen (...). Die bekannteste Kategorie von continuous-domain CSPs ist die der Probleme der linearen Programmierung, bei denen die Einschränkungen lineare Gleichheiten oder Ungleichungen sein müssen. >Lineare Programmierung/Norvig.
Norvig I 208
Bei der regulären Zustandsraumsuche kann ein Algorithmus nur eines tun: suchen. In CSPs gibt es eine Wahl: Ein Algorithmus kann suchen (eine neue Variablenzuweisung aus mehreren Möglichkeiten auswählen) oder eine bestimmte Art von Schlussfolgerung namens Constraint Propagation (Bedingungsfortpflanzung) durchführen: die Constraints verwenden, um die Anzahl der zulässigen Werte für eine Variable zu reduzieren, was wiederum die zulässigen Werte für eine andere Variable reduzieren kann, und so weiter.
Constraint Propagation kann mit der Suche verknüpft sein oder als Vorverarbeitungsschritt erfolgen, bevor die Suche beginnt. Manchmal kann diese Vorverarbeitung das gesamte Problem lösen, sodass überhaupt keine Suche erforderlich ist.
Norvig I 227
Constraint-Satisfaction-Probleme (CSPs) stellen einen Zustand mit einem Satz von Variablen-Wert-Paaren dar und stellen die Bedingungen für eine Lösung durch einen Satz von Constraints für die Variablen dar. Viele wichtige Probleme aus der Praxis können als CSPs bezeichnet werden.
Eine Reihe von Inferenztechniken nutzt die Constraints, um daraus abzuleiten, welche Variablen-Wert-Paare konsistent sind und welche nicht. Dazu gehören Knoten, Kante, Pfad und k-Konsistenz.
Die Backtracking-Suche, eine Form der Tiefensuche, wird häufig zur Lösung von CSPs eingesetzt.
Inferenz kann mit der Suche verwoben werden.
Die minimum-remaining-values heuristic und die Gradheuristik sind domänenunabhängige Methoden, um zu entscheiden, welche Variable als nächstes in einer Backtracking-Suche ausgewählt werden soll. Die least-constraining-value heuristic hilft bei der Entscheidung, welchen Wert man zuerst für eine gegebene Variable ausprobieren soll. Backtracking tritt auf, wenn für eine Variable keine zulässige Zuordnung gefunden werden kann. Konfliktgesteuertes Backjumping führt direkt zur Ursache des Problems zurück.
Lokale Suche, welche die Heuristik der Min-Konflikte nutzt, wurde auch mit großem Erfolg auf Constraint-Satisfaction-Probleme angewendet.
Geschichte: Die frühesten Arbeiten im Zusammenhang mit Constraint Satisfaction befassten sich weitgehend mit numerischen Einschränkungen. Equational Constraints mit ganzzahligen Domänen wurden vom indischen Mathematiker Brahmagupta im siebten Jahrhundert untersucht; sie werden oft als diophantische Gleichungen bezeichnet (...).
Systematische Methoden zur Lösung linearer Gleichungen durch die Eliminierung von Variablen wurden von Gauß (1829(1)) untersucht; die Lösung linearer inequality constraints geht auf Fourier (1827)(2) zurück.
Constraint-Satisfaction-Probleme mit endlichen Domänen haben ebenfalls eine lange Geschichte. Beispielsweise ist die Färbung von Graphen (von denen map coloring ein Sonderfall ist) ein altes Problem in der Mathematik. Die Vier-Farben-Vermutung (dass jeder planare Graph mit vier oder weniger Farben gefärbt werden kann) wurde erstmals 1852 von Francis Guthrie, einem Schüler von De Morgan, aufgestellt. Sie widersetzte sich der Lösung - trotz mehrerer veröffentlichter gegenteiliger Behauptungen -, bis Appel und Haken (1977)(3) einen Beweis fanden (siehe das Buch Four Colors Suffice (Wilson, 2004)(4)). Puristen waren enttäuscht, dass sich ein Teil des Beweises auf einen Computer stützte, sodass Georges Gonthier (2008)(5) unter Verwendung des COQ-Theorems einen formalen Beweis dafür ableitete, dass Appels und Hakens Beweis korrekt waren.
Norvig I 228
Methoden der Constraint Propagation wurden durch Waltz' (1975)(6) Erfolg bei vielflächigen line-labeling problems für die Computervision populär. Waltz zeigte, dass bei vielen Problemen durch die Propagation die Notwendigkeit des Backtracking vollständig entfällt. Montanari (1974)(7) führte den Begriff der Constraint-Netzwerke und der Propagation durch Pfadkonsistenz (path consistency) ein. Alan Mackworth (1977)(8) schlug den AC-3-Algorithmus zur Durchsetzung der Kantenkonsistenz sowie die allgemeine Idee, Backtracking mit einem gewissen Grad an Konsistenzdurchsetzung zu kombinieren. AC-4, ein effizienterer Kantenkonsistenz-Algorithmus, wurde von Mohr und Henderson (1986)(9) entwickelt. Bald nachdem Mackworths Arbeit erschien, begannen die Forscher mit dem Kompromiss zwischen den Kosten für die Durchsetzung der Konsistenz und den Vorteilen in Bezug auf die Reduzierung der Suche zu experimentieren. Haralick und Elliot (1980)(10) favorisierten den von McGregor (1979)(11) beschriebenen minimalen Forward-Checking-Algorithmus, während Gaschnig (1979)(12) nach jeder Variablenzuweisung eine vollständige Prüfung der Kantenkonsistenz vorschlug - ein Algorithmus, der später von Sabin und Freuder (1994)(13) MAC genannt wurde.
Spezielle Methoden zur Handhabung von höherwertigen oder globalen Constraints wurden zunächst im Rahmen der Constraint-Logischen Programmierung entwickelt. Marriott and Stuckey (1998)(14) bieten einen ausgezeichneten Bericht der Forschung in diesem Bereich.


1. Gauss, C. F. (1829). Beiträge zur Theorie der algebraischen Gleichungen. Collected in Werke,
Vol. 3, pages 71–102. K. Gesellschaft Wissenschaft, Göttingen, Germany, 1876.
2. Fourier, J. (1827). Analyse des travaux de l’Academie Royale des Sciences, pendant l’annee 1824; partie mathematique. Histoire de l’Academie Royale des Sciences de France, 7, xlvii–lv.
3. Appel, K. and Haken, W. (1977). Every planar map is four colorable: Part I: Discharging. Illinois J. Math., 21, 429–490
4. Wilson, R. (2004). Four Colors Suffice. Princeton University Press.
5. Gonthier, G. (2008). Formal proof–The four-color theorem. Notices of the AMS, 55(11), 1382–1393.
6. Waltz, D. (1975). Understanding line drawings of scenes with shadows. In Winston, P. H. (Ed.), The
Psychology of Computer Vision. McGraw-Hill.
7. Montanari, U. (1974). Networks of constraints: Fundamental properties and applications to picture processing. Information Sciences, 7(2), 95–132.
8. Mackworth, A. K. (1977). Consistency in networks of relations. AIJ, 8(1), 99–118.
9. Mohr, R. and Henderson, T. C. (1986). Arc and path consistency revisited. AIJ, 28(2), 225–233.
10. Haralick, R. M. and Elliot, G. L. (1980). Increasing tree search efficiency for constraint satisfaction problems. AIJ, 14(3), 263–313.
11. McGregor, J. J. (1979). Relational consistency algorithms and their application in finding subgraph and graph isomorphisms. Information Sciences,
19(3), 229–250.
12. Gaschnig, J. (1977). A general backtrack algorithm that eliminates most redundant tests. In IJCAI-77, p. 457.
13. Sabin, D. and Freuder, E. C. (1994). Contradicting conventional wisdom in constraint satisfaction. In
ECAI-94, pp. 125–129.
14. Marriott, K. and Stuckey, P. J. (1998). Programming with Constraints: An Introduction. MIT Press.


_____________
Zeichenerklärung: Römische Ziffern geben die Quelle an, arabische Ziffern die Seitenzahl. Die entsprechenden Titel sind rechts unter Metadaten angegeben. ((s)…): Kommentar des Einsenders. Übersetzungen: Lexikon der Argumente
Der Hinweis [Begriff/Autor], [Autor1]Vs[Autor2] bzw. [Autor]Vs[Begriff] bzw. "Problem:"/"Lösung", "alt:"/"neu:" und "These:" ist eine Hinzufügung des Lexikons der Argumente.

Norvig I
Peter Norvig
Stuart J. Russell
Artificial Intelligence: A Modern Approach Upper Saddle River, NJ 2010

Send Link

Autoren A   B   C   D   E   F   G   H   I   J   K   L   M   N   O   P   Q   R   S   T   U   V   W   Y   Z  


Begriffe A   B   C   D   E   F   G   H   I   J   K   L   M   N   O   P   Q   R   S   T   U   V   W   Z