Ein Prozess in der Constraint‑Lösung, bei dem lokale Inferenzregeln auf Constraints angewendet werden, um iterativ die Domänen von Variablen zu reduzieren, indem Werte eliminiert werden, die unter den aktuellen Constraints in keiner Lösung teilnehmen können, häufig als Vorverarbeitung oder während der Suche zur Reduktion des Suchraums.

Prinzip

Durchsetzung einer gewählten lokalen Konsistenz (Node‑, Arc‑, Path‑, k‑Konsistenz oder spezielle globale Propagatoren) in wiederholter Anwendung: Erkennen und Entfernen von Domänenwerten, die durch Constraints widersprochen werden, mittels Propagationsalgorithmen (z. B. AC‑3, AC‑4, GAC für globale Constraints), bis ein Fixpunkt oder ein Widerspruch erreicht ist.

Demonstration

In einem Sudoku‑CSP entfernt Arc‑Konsistenz‑Propagation unmögliche Ziffern aus den Domänen der Zellen durch Betrachtung von Zeilen‑, Spalten‑ und Block‑Constraints; wenn Domänen schrumpfen, können Singletons erzwungen werden, die weitere Reduktionen auslösen und die Backtracking‑Suche stark beschneiden.

Fehlanwendung

Sich darauf zu verlassen, dass lokale Propagation NP‑harte CSPs vollständig löst, oder zu aggressive Filterung anzuwenden, die unsound ist (Werte entfernt, die zu einer globalen Lösung gehören) aufgrund fehlerhafter Propagator‑Implementierung; oder Propagation ohne Kombination mit Suche einzusetzen, wenn Propagation allein die Erfüllbarkeit nicht entscheidet.

Konsequenz

Propagation verringert den Suchaufwand durch Ausscheidung unzulässiger Wertkombinationen, ermöglicht frühe Widerspruchserkennung, unterstützt inkrementelle und dynamische Problemlösung und lässt sich gut mit Verzweigungsheuristiken koppeln; ersetzt jedoch im Allgemeinen die exhaustive Suche nur für spezielle, tractable Klassen.

Umkehrung

Constraint‑Generierung oder Relaxation kehrt die einschränkende Funktion der Propagation um: statt Domänen einzuengen, kann man Domänen vergrößern oder Constraints abschwächen, um die Suche zu steuern oder duale Informationen zu erfassen, und tauscht damit Pruning gegen Flexibilität oder Überapproximation.

Abgrenzung

Gilt für CSPs mit endlichen oder endlich darstellbaren Domänen und hängt vom gewählten Konsistenzniveau ab; Propagation ist nur dann sound (entfernt keine Lösungen), wenn Propagatoren korrekt sind, und Vollständigkeit (ohne Suche eine Lösung finden) gilt nur für bestimmte tractable Problemklassen oder globale Konsistenzniveaus.

Semantische Spannung

Spannung besteht zwischen Propagation und Kodierungsansätzen (z. B. in SAT/SMT) sowie zwischen lokaler Konsistenz und globalem Schließen: lokale Propagation ist günstiger, aber schwächer als vollständige Constraintschlussfolgerung, während stärkere Propagatoren (globale Constraints) teurer sind, aber mehr Pruning erlauben.

Synthese

Constraint Propagation ist ein iteratives, korrektes lokales Inferenzverfahren, das Variablendomänen gemäß Constraints beschneidet, um die Suche praktikabel zu machen; in Kombination mit Verzweigung, globalen Propagatoren und Heuristiken bildet es das Rückgrat praktischer Constraint‑Programmierung und balanciert Inferenzkosten gegen Pruningwirkung.