5.3.4.2.1 Azyklische Constraint-Netze

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.:

Definition 5.3.12   (globale Konsistenz in azyklischen Constraint-Netzen)
Ein azyklisches Constraint-Netz ist global konsistent, gdw. es lokal konsistent ist.

Wenn für eine Variable $v_i$, $i \in \{1,\ldots,n\}$ eine zulässige Belegung ${v_i=x}$, ${x \in I_i}$ gewählt wird, so lassen sich wegen der lokalen Konsistenz den jeweils restlichen Variablen, die mit $v_i$ 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 $v_i$ 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

Fußnoten

...^5.98

,,[A `cutset' is] a minimal set of nodes, that `cuts' every cycle in a net`` (Hyvönen, 1992, S. 99).

...^5.99

Diese Strategie kann auch sinnvoll zum Auffinden von Lösungen in CSPs mit finiten Domänen eingesetzt werden, und ist dort unter den Namen Cutset Conditioning und Cycle-Cutset-Methode bekannt (vgl. Dechter, 1990a; Russel und Norvig, 2002): Wenn ein cutset identifiziert und mit konsistenten Werten belegt wurde, lassen sich, falls eine Lösung existiert, die Variablen im verbleibenden (baumartigen) Constraint-Graphen relativ einfach mit konsistenten Werten belegen (vgl. Dechter und Pearl, 1989,1987). Wegen der großen Abhängigkeit der Effektivität von der Struktur des jeweiligen Constraint-Graphen, und der starken heuristischen Komponente dieses Verfahrens bei der Auswahl der cutset-Variablen, wurde es in dieser Arbeit nicht nicht näher betrachtet (vgl. Abschnitt 5.2.2).