Beispiel Kanalisierungsbeschränkungen ECLiPSe

Wie in Dual-Viewpoint-Heuristik für Probleme mit binärer Abhängigkeitsbefriedigung (P. A. Geelen) :

  

Durch die Kanalabhängigkeit zweier verschiedener Modelle kann eine Beziehung zwischen zwei Gruppen von Variablen ausgedrückt werden, einer für jedes Modell.

Dies bedeutet, dass Zuordnungen in einem der Standpunkte in Zuweisungen in den anderen übersetzt werden können und umgekehrt, und wenn die Suche beginnt, Ausgeschlossene Werte aus einem Modell können auch aus dem anderen ausgeschlossen werden.

Lassen Sie mich ein Beispiel ansprechen, das ich vor einiger Zeit implementiert habe, als ich einen Sudoku-Solver geschrieben habe.

Klassischer Ansichtspunkt

Hier interpretieren wir das Problem auf die gleiche Weise, wie es ein Mensch tun würde: Ganzzahlen zwischen 1 und 9 und eine Definition, dass alle Zeilen, Spalten und Blöcke jede Ganzzahl genau einmal enthalten müssen.

Wir können dies in ECLiPSe leicht mit etwas wie:

Und das reicht noch, um das Sudoku-Rätsel zu lösen.

Binärer boolescher Standpunkt

Man könnte aber auch ganze Zahlen durch ihre binären booleschen Arrays darstellen (gezeigt in der Antwort von @jschimpf). Falls es nicht klar ist, was das ist, betrachten Sie das kleine Beispiel unten (das ist eingebaute Funktionalität!):

Wenn wir dieses Modell zur Darstellung eines Sudokus verwenden, wird jede Zahl durch ihr binäres boolesches Array ersetzt und entsprechende Einschränkungen können geschrieben werden. Da ich für diese Antwort trivial bin, werde ich nicht den gesamten Code für die Einschränkungen angeben, aber eine einzelne Summenbedingung reicht noch aus, um ein Sudoku-Puzzle in seiner binären booleschen Darstellung zu lösen.

Channeling

Wenn Sie diese beiden Standpunkte mit entsprechenden eingeschränkten Modellen haben, können Sie nun zwischen ihnen channeln und sehen, ob Verbesserungen vorgenommen wurden.

Da beide Modelle immer noch nur ein NxN-Board sind, gibt es keinen Unterschied in der Dimension der Darstellung und das Channeling wird wirklich einfach.

Lassen Sie mich zuerst ein letztes Beispiel dafür geben, wie ein mit Ganzzahlen gefüllter Block 1..9 in beiden unserer Modelle aussehen würde:

Wir sehen jetzt klar die Verbindung zwischen den Modellen und schreiben einfach den Code, um unsere Entscheidungsvariablen zu kanalisieren. Wenn Sie Sudoku und BinBools als unsere Boards verwenden, sieht der Code ungefähr so ​​aus:

An diesem Punkt haben wir ein kanalisiertes Modell, bei dem während der Suche, wenn Werte in einem der Modelle gelöscht werden, die Auswirkungen auch in dem anderen Modell auftreten. Dies kann dann natürlich zu einer weiteren generellen Constraint-Propagation führen.

Begründung

Um die Nützlichkeit des binären booleschen Modells für das Sudoku-Rätsel zu erklären, müssen wir zuerst zwischen einigen bereitgestellten alldifferent/1 -Implementierungen durch ECLiPSe unterscheiden:

Was dies in der Praxis bedeutet, kann wie folgt gezeigt werden:

Da noch keine Zuweisung mit der Forward Checking (ic-Bibliothek) erfolgt ist, wird die Ungültigkeit der Abfrage noch nicht erkannt, während die Bounds Consistent-Version dies sofort bemerkt. Dieses Verhalten kann zu erheblichen Unterschieden bei der Constraint-Propagierung beim Suchen und Zurückverfolgen durch stark eingeschränkte Modelle führen.

Oberhalb dieser beiden Bibliotheken befindet sich die Bibliothek ic_global_gac, die für globale Abhängigkeiten vorgesehen ist, für die eine verallgemeinerte Arc-Konsistenz (auch Hyperlichtbogenkonsistenz oder Domänenkonsistenz genannt) beibehalten wird. Diese alldifferent / 1-Einschränkung bietet noch mehr Beschneidungsmöglichkeiten als die Grenzen konsistent, aber die Erhaltung der vollen Domänenkonsistenz hat ihre Kosten und die Verwendung dieser Bibliothek in stark eingeschränkten Modellen führt im Allgemeinen zu einem Verlust der Laufleistung.

Versuchsergebnisse

Nachstehend finden Sie die Backtrack-Ergebnisse für das Sudoku-Rätsel "Platinumblonde" (das als das schwierigste und chaotischste Sudoku-Rätsel in Das Chaos innerhalb von Sudoku , M. ErcseyRavasz und Z. Toroczkai) unter Verwendung von Vorwärtsprüfung, Grenzkonsistenz, Domänenkonsistenz, eigenständigem binärem Booleschen Modell und schließlich dem kanalisierten Modell:

Wie wir sehen können, benötigt unser kanalisiertes Modell (mit bounds consistency (ic_global)) immer noch einen Backtrack mehr als die domänenkonsistente Implementierung, aber es ist definitiv besser als die standalone bounds konsistente Version.

Wenn wir uns jetzt die Laufzeiten ansehen (Ergebnisse sind das Ergebnis der Berechnung eines Durchschnitts über mehrere Ausführungen, um Extreme zu vermeiden), ohne die Implementierung der Vorwärtsüberprüfung auszuschließen, da sie für das Lösen von Sudoku-Puzzles nicht mehr interessant ist / p> %Vor%

Wenn wir diese Ergebnisse betrachten, können wir das Experiment erfolgreich abschließen (diese Ergebnisse wurden von über 20 anderen Sudoku-Puzzle-Instanzen bestätigt):

  

Das Channeln des binären booleschen Blickpunkts auf die Grenzen der konsistenten Standalone-Implementierung führt zu einem geringfügig weniger starken Constraint-Propagierungsverhalten als bei der domänenkonsistenten Standalone-Implementierung, jedoch mit Laufzeiten von genauso lang bis deutlich schneller.

BEARBEITEN: versuchen Sie zu klären

Stellen Sie sich vor, eine Domain-Variable, die eine Zelle auf einer Sudoku-Karte repräsentiert, hat eine verbleibende Domain von 4..9. Durch die Verwendung von Bounds Consistency ist sichergestellt, dass für Wert 4 und 9 andere Domain-Werte gefunden werden können, die alle Constraints erfüllen und somit Konsistenz gewährleisten. Für andere Werte in der Domäne ist jedoch keine Konsistenz explizit garantiert (dies ist die Domänenkonsistenz).

Unter Verwendung eines binären booleschen Modells definieren wir die folgenden zwei Summenbedingungen:

• Die Summe jedes binären booleschen Arrays ist immer gleich 1
• Die Summe jedes N-ten Elements jedes Arrays in jeder Zeile / Spalte / Block ist immer gleich 1

Die zusätzliche Constraint-Stärke wird durch die zweite Constraint erzwungen, die neben der Einschränkung von Zeilen, Spalten und Blöcken auch implizit sagt: "Jede Zelle kann nur jede Ziffer einmal enthalten". Dieses Verhalten wird nicht aktiv ausgedrückt, wenn nur die Grenzen konsistent alldifferent / 1 constraint verwendet werden!

Fazit

Es ist klar, dass Channeling sehr nützlich sein kann, um ein eigenständiges eingeschränktes Modell zu verbessern, jedoch wenn die Constraint-Stärke des neuen Modells schwächer ist als die des aktuellen Modells, werden offensichtlich keine Verbesserungen vorgenommen. Beachten Sie auch, dass ein eingeschränkteres Modell nicht notwendigerweise auch eine insgesamt bessere Leistung bedeutet! Das Hinzufügen von mehr Constraints verringert zwar die Anzahl der Backtracks, die zur Lösung eines Problems erforderlich sind, erhöht aber möglicherweise auch die Ausführungszeiten Ihres Programms, wenn mehr Constraint-Prüfungen durchgeführt werden müssen.

Kanalbeschränkungen werden verwendet, wenn in einem Modell Aspekte eines Problems auf mehr als eine Weise dargestellt werden. Sie sind dann notwendig, um diese multiplen Repräsentationen zu synchronisieren, obwohl sie selbst keinen Aspekt des Problems modellieren.

Wenn Sie ein Problem mit Einschränkungen modellieren, haben Sie normalerweise mehrere Möglichkeiten, Ihre Variablen auszuwählen. In einem Planungsproblem könnten Sie beispielsweise

• eine Integer-Variable für jeden Job (zeigt an, welcher Rechner den Job ausführt)
• eine Integer-Variable für jede Maschine (die angibt, welchen Job sie ausführt)
• eine Matrix von booleschen Werten (zeigt an, welcher Job auf welchem ​​Rechner läuft)
• oder etwas exotischeres

In einem einfach genug Problem, wählen Sie die Darstellung, die es am einfachsten macht, die Einschränkungen des Problems zu formulieren. In realen Problemen mit vielen heterogenen Randbedingungen ist es jedoch oft unmöglich, eine solche beste Darstellung zu finden: Einige Constraints werden am besten mit einem Typ von Variablen dargestellt, andere mit einem anderen.

In solchen Fällen können Sie mehrere Sätze von Variablen verwenden und jede einzelne Problemeinschränkung über den am besten geeigneten Variablensatz formulieren. Natürlich haben Sie dann mehrere unabhängige Teilprobleme, und wenn Sie diese isoliert lösen, erhalten Sie keine Lösung für das gesamte Problem. Durch Hinzufügen von Channeling-Constraints können die Variablensätze jedoch synchronisiert und die Subprobleme somit wieder verbunden werden. Das Ergebnis ist dann ein gültiges Modell für das ganze Problem.

Wie in dem Zitat aus dem Handbuch angedeutet, genügt in einer solchen Formulierung die Suche nach nur einem der Variablensätze ("viewpoints"), weil die Werte der anderen durch die Channeling-Constraints impliziert werden. p>

Einige gängige Beispiele für das Channeling zwischen zwei Repräsentationen sind:

Ganzzahlige Variable und Boolesches Array : Betrachten Sie eine Ganzzahlvariable T , die das Zeitfenster 1..N anzeigt, wenn ein Ereignis stattfindet, und ein Array von Booleschen Bs[N] , so dass Bs[T] = 1 wenn ein Ereignis im Zeitfenster T stattfindet. In ECLiPSe:

Das Channeling zwischen den beiden Repräsentationen kann dann mit

, die Informationen in beide Richtungen zwischen T und Bs propagiert. Eine andere Möglichkeit, dieses Channeling zu implementieren, ist die spezielle bool_channeling / 3 Einschränkung.

Start / Ende-Integer-Variablen und Array of Booleans (Stundenplan): Wir haben Integer-Variablen S,E , die die Start- und Endzeit einer Aktivität angeben. Auf der anderen Seite ein Array von Booleans Bs[N] , so dass Bs[T] = 1 wenn die Aktivität zum Zeitpunkt T stattfindet. In ECLiPSe:

Channeling kann über

Dual-Repräsentation Job / Maschine Integer-Variablen : Hier bedeutet Js[J] = M , dass der Job J auf der Maschine M ausgeführt wird, während die duale Formel Ms[M] = J bedeutet, dass die Maschine M den Job J

Und Channeling wird über

Variable festlegen und Boolesches Array : Wenn Sie einen Solver verwenden (z. B. library (ic_sets) ), der Set-Variablen direkt verarbeiten kann Diese können in ein Array von Booleans reflektiert werden, die die Zugehörigkeit von Elementen in der Menge anzeigen. Die Bibliothek stellt zu diesem Zweck eine dedizierte Einschränkung membership_booleans / 2 bereit.

Hier ist ein einfaches Beispiel, das in SWI-Prolog funktioniert, aber sollte arbeite auch in ECLiPSe Prolog (später musst du (::) / 2 anstelle von (in) / 2) verwenden:

Einschränkung C1:

Einschränkung C2:

Kanalbeschränkung:

Alles zusammen:

Also funktioniert die Kanalbeschränkung in beide Richtungen reduziert die Domäne von C1 sowie die Domäne von C2.

Einige Systeme verwenden iterative Methoden, mit dem Ergebnis, dass diese kanalisiert werden kann einige Zeit dauern, hier ist ein Beispiel, das herum benötigt 1 Minute zum Berechnen in SWI-Prolog:

Auf der anderen Seite macht ECLiPSe Prolog es im Handumdrehen:

Tschüss