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):
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
. In der Prozedur
NC werden der Reihe nach alle Domänen
auf
den Wert
beschränkt, der mit dem jeweiligen Constraint
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.
![]() |
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.