Umgedreht allerdings impliziert lokale Konsistenz die globale Konsistenz nur selten, nämlich immer dann, wenn ein lokal konsistentes Constraint-Netz keine Zyklen enthält vgl. Hyvönen, 1991, S. 246; Hyvönen, 1992, S. 89 f.:
Wenn für eine Variable ,
eine zulässige
Belegung
,
gewählt wird, so lassen sich wegen
der lokalen Konsistenz den jeweils restlichen Variablen, die mit
in einem Constraint vorkommen, ebenfalls konsistente Werte zuweisen.
Wegen der Zyklenfreiheit führt nun jede Kante aus dem bisher
betrachteten Graphen in einen eigenständigen Teilgraphen, der auf
dieselbe Art mit Werten belegt werden kann. Dies lässt sich mit jeder
beliebigen Variable
und jedem Wert x aus deren
Wertebereich durchführen, so dass in diesem Fall die lokale Konsistenz
mit der globalen Konsistenz äquivalent ist.
Dies geht wiederum direkt auf die von Freuder (1982) gemachten Beobachtungen zurück (vgl. Abschnitt 5.2.3.5). Wenn auch globale Konsistenz durch lokale TP nur selten erreicht wird, so kann dennoch versucht werden, wenigstens engere Intervallgrenzen zu bestimmen. Dies kann durch dynamic splitting erreicht werden. Dabei wird eine lokal konsistente Toleranzsituation bzgl. der global inkonsistenten Variablen durch Zerteilen der Wertebereiche eben dieser Variablen in unterschiedliche Teilprobleme zerlegt (vgl. Abschnitt 5.3.2). Von diesen Teilproblemen werden wiederum die lokalen Lösungen bestimmt usw. Dies geschieht so lange, bis keine Änderungen mehr eintreten bzw. u.U. globale Konsistenz erreicht wird. Die Variablen, die für diese Zerlegung ausgewählt werden, sind i.d.R. die sog. cutset-Variablen. Ein cutset besteht dabei aus der kleinsten Menge der Variablen, durch die sämtliche Zyklen im Constraint-Netz verbunden werden.5.98 Das dynamic splitting funktioniert deswegen, weil durch die beschränkteren Wertebereiche der Variablen globale Lösungen einfacher anhand lokaler Kriterien hergestellt werden können (vgl. Hyvönen, 1991, S. 247). Führt dynamic splitting sogar dazu, dass die cutset-Variablen jeweils auf einen einzigen Wert, d.h. ein Punktintervall, reduziert werden können, so ist das Constraint-Netz durch die lokale Konsistenz gleichzeitig global konsistent: Die cutset-Variablen können in diesem Fall als Konstanten betrachtet werden. Das resultierende Constraint-Netz ist azyklisch (vgl. Hyvönen, 1992, S. 99 ff.).5.99