Der iterative Prozess, Einschränkungen in einem Constraint-Netzwerk anzuwenden, um Variablendomänen zu verkleinern, indem Werte eliminiert werden, die in keiner Lösung vorkommen können; häufig realisiert durch Bogenkonsistenz, Forward Checking oder verallgemeinerte Konsistenzalgorithmen.

Prinzip

Verwende lokale Nebenbedingungsrelationen, um unmögliche Werte zu schließen und zu entfernen, damit Domänen schrumpfen und erzwungene Zuordnungen sichtbar werden; wiederholte Anwendung schärft das Problem und reduziert kombinatorische Verzweigung.

Demonstration

In einem binären CSP mit der Nebenbedingung X ≠ Y und Domänen X = {1,2}, Y = {2,3} entfernt die Propagation die 2 aus Xs Domäne, wenn Y auf 2 festgelegt wird; Bogenkonsistenz kann iterativ Werte entfernen, bis Stabilität erreicht ist.

Fehlanwendung

Zu aggressive globale Propagation ohne Kostenabwägung kann Zeit verschwenden bei geringem Eigenschnitt (hoher Overhead), und naive Propagation, die Abhängigkeiten zwischen Nebenbedingungen ignoriert, kann bei fehlerhafter Implementierung zu falschen Domänenreduktionen führen.

Konsequenz

Richtige Constraint-Propagation reduziert die Suche erheblich, indem unzulässige Zweige früh eliminiert werden; kombiniert mit Suchheuristiken kann sie eine unhandliche Suche handhabbar machen.

Umkehrung

Das Gegenteil ist die Suche ohne jegliche Propagation (reine Brute-Force-Aufzählung), die zwar korrekt bleibt, aber typischerweise viel weniger effizient ist, weil frühes Pruning fehlt.

Abgrenzung

Gilt für diskrete CSPs und kombinatorische Suche; kontinuierliche Domänen erfordern andere Propagationsmethoden (Intervallarithmetik, Relaxation) und bestimmte globale Nebenbedingungen benötigen spezialisierte Propagatoren.

Semantische Spannung

Es besteht Spannung zwischen lokaler Propagation (Bogenkonsistenz) und globaleren Konsistenzgraden: stärkere Konsistenz führt zu besserer Beschneidung, aber zu höheren Rechenkosten; der Trade-off ist problemabhängig.

Synthese

Constraint-Propagation ist die disziplinierte Anwendung lokaler Schlussfolgerungen zur schrittweisen Verkleinerung von Variablendomänen, die Abwägung von Pruning-Effektivität gegen Rechenaufwand, um kombinatorische Suche praktisch durchführbar zu machen.