Constraint-Zufriedenheitsproblem - Constraint satisfaction problem

Nicht zu verwechseln mit Kommunikation sequentieller Prozesse .

Constraint-Erfüllungsprobleme ( CSPs ) sind mathematische Fragen, die als eine Menge von Objekten definiert sind, deren Zustand eine Reihe von Beschränkungen oder Beschränkungen erfüllen muss . CSPs stellen die Entitäten in einem Problem als homogene Sammlung endlicher Beschränkungen über Variablen dar , die durch Beschränkungserfüllungsverfahren gelöst werden. CSPs sind Gegenstand der Forschung sowohl in der künstlichen Intelligenz als auch im Operations Research , da die Regelmäßigkeit in ihrer Formulierung eine gemeinsame Grundlage bietet, um Probleme vieler scheinbar nicht verwandter Familien zu analysieren und zu lösen. CSPs weisen häufig eine hohe Komplexität auf , die eine Kombination von Heuristiken und kombinatorischen Suchmethoden in angemessener Zeit erfordert . Constraint Programming (CP) ist das Forschungsgebiet, das sich speziell mit solchen Problemen befasst. Darüber hinaus sind das Boolesche Erfüllbarkeitsproblem (SAT), die Erfüllbarkeits-Modulo-Theorien (SMT), die Mixed-Integer-Programmierung (MIP) und die Antwortmengen-Programmierung (ASP) Forschungsgebiete, die sich auf die Lösung bestimmter Formen des Constraint-Zufriedenheitsproblems konzentrieren.

Beispiele für Probleme, die als Constraint-Erfüllungsproblem modelliert werden können, sind:

Diese werden oft mit Tutorials von CP- , ASP-, Boolean SAT- und SMT-Solvern bereitgestellt . Im allgemeinen Fall können Beschränkungsprobleme viel schwieriger sein und sind in einigen dieser einfacheren Systeme möglicherweise nicht ausdrückbar. Beispiele aus dem "realen Leben" umfassen automatisierte Planung , lexikalische Begriffsklärung , Musikwissenschaft , Produktkonfiguration und Ressourcenzuweisung .

Die Existenz einer Lösung für einen CSP kann als Entscheidungsproblem angesehen werden . Dies kann dadurch entschieden werden, dass eine Lösung gefunden wird oder eine Lösung nach einer erschöpfenden Suche nicht gefunden wird (stochastische Algorithmen kommen normalerweise nie zu einem erschöpfenden Ergebnis, während gerichtete Suchen bei ausreichend kleinen Problemen häufig dies tun). In einigen Fällen kann bekannt sein, dass der CSP zuvor durch einen anderen mathematischen Inferenzprozess Lösungen hat.

Formale Definition

Formal wird ein Constraint-Erfüllungsproblem als Tripel definiert , wobei

  • ist eine Menge von Variablen,
  • eine Menge ihrer jeweiligen Wertebereiche ist, und
  • ist eine Reihe von Einschränkungen.

Jede Variable kann die Werte in der nichtleeren Domäne annehmen . Jede Einschränkung ist wiederum ein Paar , wobei eine Teilmenge von Variablen und eine -äre Relation auf der entsprechenden Teilmenge von Domänen ist . Eine Bewertung der Variablen ist eine Funktion von einer Untermenge von Variablen zu einer bestimmten Menge von Werten in der entsprechenden Untermenge von Domänen. Eine Auswertung erfüllt eine Einschränkung, wenn die den Variablen zugewiesenen Werte die Beziehung erfüllen .

Eine Auswertung ist konsistent, wenn sie keine der Beschränkungen verletzt. Eine Auswertung ist abgeschlossen, wenn sie alle Variablen enthält. Eine Evaluation ist eine Lösung, wenn sie konsistent und vollständig ist; Eine solche Auswertung gesagt wird, lösen die Randbedingungserfüllungsproblem.

Lösung

Constraint-Erfüllungsprobleme auf endlichen Domänen werden typischerweise durch eine Form der Suche gelöst . Die am häufigsten verwendeten Techniken sind Varianten von Backtracking , Constraint Propagation und Local Search . Diese Techniken werden auch oft kombiniert, wie bei der VLNS- Methode, und die aktuelle Forschung beschäftigt sich mit anderen Technologien wie der linearen Programmierung .

Backtracking ist ein rekursiver Algorithmus. Es behält eine Teilbelegung der Variablen bei. Zunächst sind alle Variablen nicht zugewiesen. Bei jedem Schritt wird eine Variable ausgewählt und ihr werden der Reihe nach alle möglichen Werte zugewiesen. Für jeden Wert wird die Konsistenz der Teilzuweisung mit den Constraints überprüft; bei Konsistenz wird ein rekursiver Aufruf durchgeführt. Wenn alle Werte ausprobiert wurden, geht der Algorithmus zurück. In diesem grundlegenden Backtracking-Algorithmus wird Konsistenz als die Erfüllung aller Beschränkungen definiert, deren Variablen alle zugewiesen sind. Es gibt mehrere Varianten des Backtrackings. Backmarking verbessert die Effizienz der Konsistenzprüfung. Backjumping ermöglicht es, in einigen Fällen einen Teil der Suche zu speichern, indem "mehr als eine Variable" zurückverfolgt wird. Das Constraint-Learning leitet neue Constraints ab und speichert sie, die später verwendet werden können, um einen Teil der Suche zu vermeiden. Look-Ahead wird auch häufig beim Backtracking verwendet, um zu versuchen, die Auswirkungen der Auswahl einer Variablen oder eines Wertes vorherzusehen, wodurch manchmal im Voraus bestimmt wird, wann ein Teilproblem erfüllbar oder nicht erfüllbar ist.

Constraint-Propagation- Techniken sind Verfahren, die verwendet werden, um ein Constraint-Erfüllungsproblem zu modifizieren. Genauer gesagt handelt es sich um Methoden, die eine Form lokaler Konsistenz erzwingen, dh Bedingungen, die sich auf die Konsistenz einer Gruppe von Variablen und/oder Einschränkungen beziehen. Die Beschränkungsausbreitung hat verschiedene Verwendungen. Erstens verwandelt es ein Problem in ein äquivalentes, aber normalerweise einfacher zu lösendes Problem. Zweitens kann es die Erfüllbarkeit oder Unerfüllbarkeit von Problemen beweisen. Dies ist im Allgemeinen nicht garantiert; es tritt jedoch immer bei einigen Formen der Einschränkungsausbreitung und/oder bei bestimmten Arten von Problemen auf. Die bekanntesten und am häufigsten verwendeten Formen der lokalen Konsistenz sind Bogenkonsistenz , Hyperbogenkonsistenz und Pfadkonsistenz . Die beliebteste Constraint-Propagation-Methode ist der AC-3-Algorithmus , der die Bogenkonsistenz erzwingt.

Lokale Suchverfahren sind unvollständige Erfüllbarkeitsalgorithmen. Sie können eine Lösung für ein Problem finden, aber sie können auch dann scheitern, wenn das Problem erfüllbar ist. Sie funktionieren, indem sie iterativ eine vollständige Zuweisung über die Variablen verbessern. Bei jedem Schritt wird der Wert einer kleinen Anzahl von Variablen geändert, mit dem allgemeinen Ziel, die Anzahl der durch diese Zuweisung erfüllten Einschränkungen zu erhöhen. Der Min-Conflicts-Algorithmus ist ein lokaler Suchalgorithmus speziell für CSPs und basiert auf diesem Prinzip. In der Praxis scheint die lokale Suche gut zu funktionieren, wenn diese Änderungen auch von zufälligen Entscheidungen beeinflusst werden. Es wurde eine Integration der Suche mit der lokalen Suche entwickelt, die zu hybriden Algorithmen führt .

Theoretische Aspekte

Entscheidungsprobleme

CSPs werden auch in der Computational Complexity Theory und der Finite-Model-Theorie untersucht . Eine wichtige Frage ist, ob für jede Menge von Relationen die Menge aller CSPs, die nur unter Verwendung von Relationen dargestellt werden können, die aus dieser Menge ausgewählt werden, entweder P oder NP-vollständig ist . Wenn ein solches Dichotomie- Theorem wahr ist, dann liefern CSPs eine der größten bekannten Teilmengen von NP , die NP-Zwischenprobleme vermeidet, deren Existenz durch den Satz von Ladner unter der Annahme P ≠ NP demonstriert wurde . Der Dichotomiesatz von Schaefer behandelt den Fall, dass alle verfügbaren Relationen Boolesche Operatoren sind, dh für Domänengröße 2. Der Dichotomiesatz von Schaefer wurde kürzlich auf eine größere Klasse von Relationen verallgemeinert.

Die meisten Klassen von CSPs, von denen bekannt ist, dass sie bearbeitbar sind, sind diejenigen, bei denen der Hypergraph von Beschränkungen eine begrenzte Baumbreite hat (und es keine Beschränkungen für den Satz von Beschränkungsrelationen gibt) oder bei denen die Beschränkungen eine beliebige Form haben, aber im Wesentlichen nicht-unäre Polymorphismen von . existieren die Menge der Beschränkungsbeziehungen.

Jeder CSP kann auch als Conjunctive Query Containment Problem betrachtet werden.

Funktionsprobleme

Eine ähnliche Situation besteht zwischen den Funktionsklassen FP und #P . Durch eine Verallgemeinerung des Satzes von Ladner gibt es auch Probleme in weder FP noch #P-vollständig solange FP ≠ #P. Wie im Entscheidungsfall wird ein Problem im #CSP durch eine Menge von Beziehungen definiert. Jedes Problem nimmt eine boolesche Formel als Eingabe und die Aufgabe besteht darin, die Anzahl der erfüllenden Zuweisungen zu berechnen. Dies kann weiter verallgemeinert werden, indem größere Domänengrößen verwendet werden und jeder erfüllenden Zuweisung eine Gewichtung zugeordnet wird und die Summe dieser Gewichtungen berechnet wird. Es ist bekannt, dass jedes komplexe gewichtete #CSP-Problem entweder in FP oder #P-schwer liegt.

Varianten

Das klassische Modell des Constraint Satisfaction Problems definiert ein Modell statischer, unflexibler Constraints. Dieses starre Modell ist ein Mangel, der es schwierig macht, Probleme einfach darzustellen. Mehrere Modifikationen der grundlegenden CSP-Definition wurden vorgeschlagen, um das Modell an eine Vielzahl von Problemen anzupassen.

Dynamische CSPs

Dynamische CSPs ( DCSPs ) sind nützlich, wenn die ursprüngliche Formulierung eines Problems in irgendeiner Weise geändert wird, typischerweise weil sich die zu berücksichtigenden Einschränkungen aufgrund der Umgebung ändern. DCSPs werden als eine Folge von statischen CSPs betrachtet, von denen jede eine Transformation der vorherigen ist, in der Variablen und Einschränkungen hinzugefügt (Restriktion) oder entfernt (Relaxation) werden können. Informationen, die in den anfänglichen Formulierungen des Problems gefunden wurden, können verwendet werden, um die nächsten zu verfeinern. Die Lösungsmethode kann nach der Art der Informationsübertragung klassifiziert werden:

  • Oracles: Die Lösung, die für frühere CSPs in der Sequenz gefunden wurde, wird als Heuristik verwendet, um die Auflösung des aktuellen CSP von Grund auf zu steuern.
  • Lokale Reparatur: Jeder CSP wird ausgehend von der Teillösung des vorherigen berechnet und die inkonsistenten Bedingungen mit lokaler Suche repariert .
  • Constraint-Aufzeichnung: In jeder Phase der Suche werden neue Constraints definiert, um das Erlernen inkonsistenter Entscheidungsgruppen darzustellen. Diese Einschränkungen werden auf die neuen CSP-Probleme übertragen.

Flexible CSPs

Klassische CSPs behandeln Beschränkungen als hart, d. h. sie sind zwingend (jede Lösung muss alle erfüllen) und unflexibel (in dem Sinne, dass sie vollständig erfüllt werden müssen, sonst werden sie vollständig verletzt). Flexible CSPs lockern diese Annahmen, lockern teilweise die Beschränkungen und erlauben der Lösung, nicht alle davon zu erfüllen. Dies ist vergleichbar mit Präferenzen bei der präferenzbasierten Planung . Einige Arten von flexiblen CSPs umfassen:

  • MAX-CSP, bei dem eine Anzahl von Beschränkungen verletzt werden darf und die Qualität einer Lösung durch die Anzahl der erfüllten Beschränkungen gemessen wird.
  • Weighted CSP , ein MAX-CSP, bei dem jede Verletzung einer Einschränkung gemäß einer vordefinierten Präferenz gewichtet wird. Somit wird das Erfüllen von Beschränkungen mit mehr Gewicht bevorzugt.
  • Fuzzy-CSP-Modellbeschränkungen als Fuzzy- Relationen, in denen die Erfüllung einer Beschränkung eine kontinuierliche Funktion der Werte ihrer Variablen ist, die von vollständig erfüllt bis vollständig verletzt wird.

Dezentrale CSPs

In DCSPs wird davon ausgegangen, dass jede Einschränkungsvariable einen separaten geografischen Standort hat. Dem Informationsaustausch zwischen Variablen werden starke Beschränkungen auferlegt, was die Verwendung vollständig verteilter Algorithmen erfordert, um das Problem der Beschränkungserfüllung zu lösen.

Siehe auch

Verweise

Weiterlesen