next up previous contents index
Nächste Seite: 5.2.3.3 Kantenkonsistenz Aufwärts: 5.2.3 Konsistenzverfahren Vorherige Seite: 5.2.3.1 Constraint-Propagation   Inhalt   Index

5.2.3.2 Knotenkonsistenz

Der einfachste Konsistenzgrad ist die Knotenkonsistenz. Dieser Konsistenzgrad bezieht sich ausschließlich auf unäre Constraints, d.h. im Regelfall auf einfache Wertezuweisungen. Knotenkonsistenz ist folgendermaßen definiert (vgl. Güsgen, 2000, S. 270):

Definition 5.2.7   (Knotenkonsistenz/node consistency, NC)
Gegeben sei ein beliebiges CSP auf den Variablen $v_1,\ldots,v_n$ mit den Wertebereichen $D_1,\ldots,D_n$. Sei $C_1^u,\ldots,C_n^u$ die Menge der unären Constraints im Constraint-Netz, wobei $C_i^u$, $i
\in \{1,\ldots,n\}$, die Relation $R_i^u$ besitzt und die Variable $v_i$ einschränkt. Das Constraint-Netz ist knotenkonsistent, falls für alle $i
\in \{1,\ldots,n\}$ gilt: $D_i \subseteq R_i^u$.

Ein Constraint-Netz ist dementsprechend knotenkonsistent, wenn alle unären Constraints erfüllt sind, d.h. wenn sich alle vorhandenen unären Constraints trivialerweise in den Wertebereichen der Variablen bereits widerspiegeln. In Abbildung 5.2 ist der Algorithmus NC-1 zur Herstellung von Knotenkonsistenz von Mackworth (1977a) dargestellt. Der Algorithmus erhält als Eingabe die Menge der unären Constraints $C_1^u,\ldots,C_n^u$. In der Prozedur NC werden der Reihe nach alle Domänen $D_i$ auf den Wert $d_i$ beschränkt, der mit dem jeweiligen Constraint $C_i^u$ konsistent ist. Das Laufzeitverhalten des Algorithmus ist linear mit der Anzahl der Variablen und der Anzahl der möglichen Werte in den Wertebereichen, da der Algorithmus jeden Knoten im Constraint-Netz mit den möglichen Werten lediglich einmal inspiziert.

Abbildung 5.2: Algorithmus NC-1 zur Herstellung von Knotenkonsistenz (vgl. Mackworth, 1977a, S. 103)
\begin{figure}\fbox{\parbox{14.4cm}{
\begin{small}
\textbf{procedure} NC($v_i$):...
... \textbf{do} NC($v_i$)
\par
\textbf{end}
\end{small}}}%\end{rahmen}
\end{figure}

Knotenkonsistenz beschränkt in einem Constraint-Netz die Wertebereiche der Variablen auf die durch unäre Constraints erlaubten Werte und schließt dadurch u.U. bereits einen großen Teil Werte aus, die nicht zur Lösung des CSP beitragen können, da sie einzelne Constraints verletzen.


next up previous contents index
Nächste Seite: 5.2.3.3 Kantenkonsistenz Aufwärts: 5.2.3 Konsistenzverfahren Vorherige Seite: 5.2.3.1 Constraint-Propagation   Inhalt   Index