Eine Möglichkeit, CSPs mit höherwertigen Constraints zu verarbeiten, besteht in der Anwendung der in Abschnitt 5.2.3.5 vorgestellten Synthese-Algorithmen zur Herstellung von k-Konsistenz, was allerdings aus Komplexitätsgründen nur für die wenigsten Problemstellungen in Frage kommt.
Backtracking-basierte Suchverfahren lassen sich i.A. unkompliziert auch auf n-äre Constraints anwenden, allerdings steigt der Aufwand eine oder gar alle Lösungen zu finden sehr stark an, da selbst für scheinbar einfache Constraints eine sehr große Anzahl Wertekombinationen auf das Bilden einer möglichen Lösung getestet werden müssen (vgl. Marriott und Stuckey, 1999, S. 97). Filtertechniken zur Problemreduktion sind daher umso notwendiger, damit der nachfolgend bzw. parallel durchgeführte Suchvorgang vereinfacht wird. Einige Konsistenztechniken für binäre Constraints sind in der Vergangenheit für die direkte Behandlung von n-ären Constraints erweitert worden. Das am häufigsten eingesetzte Konsistenzverfahren ist die Kantenkonsistenz, die bereits sehr früh zur Hyperkantenkonsistenz generalisiert wurde. Beim populären Forward Checking dagegen gibt es mehrere Definitionen für die Behandlung von höherwertigen Constraints, die jeweils unterschiedliche Konsistenzgrade und Verarbeitungsverfahren nach sich ziehen (vgl. Bessière et al., 1999c,2002,1999b).5.71 Ursprünglich wurde FC von Van Hentenryck (1989, S. 60 ff.) für die Bearbeitung von n-ären CSPs verallgemeinert. Analog zur binären Form, wird demnach Forward Checking nur dann vorgenommen, wenn in einem Constraint bereits alle bis auf eine Variable mit einem Wert belegt sind. Die verbleibende Variable ist in diesem Fall forward checkable.
Für die Anwendung von Kantenkonsistenz gibt es wie für Backtracking nur eine einzige, eindeutige Definition für die Behandlung von n-ären Constraints (vgl. Mohr und Masini, 1988):
Dies bedeutet lediglich, dass für jede Belegung von jedem Knoten
gültige Belegungen in den Domänen der Variablen
existieren, so dass jedes n-äre Constraint auf diesen
Variablen erfüllt wird. Ein Constraint-Netz ist
hyperkantenkonsistent, wenn alle Hyperkanten (Constraints)
hyperkantenkonsistent sind. Die Hyperkantenkonsistenz dehnt somit die
Konsistenzbedingung der Kantenkonsistenz aus, damit diese auf jedes
Constraint unabhängig von der Anzahl der Variablen angewendet werden
kann. Allerdings können hierbei Konsistenzprüfungen selbst für
einfache Constraints mit mehr als zwei Variablen wiederum sehr
aufwendig werden, da der Aufwand zur Herstellung von
Hyperkantenkonsistenz bereits für ein einzelnes Constraint NP-hart ist
(vgl. Marriott und Stuckey, 1999, S. 97).5.72
Aufgrund dieser Bedingungen existieren nur wenige bekannte Algorithmen
zur Herstellung von Hyperkantenkonsistenz. Alan K. Mackworth hat in seiner Arbeit zur
Interpretation von handgezeichneten Skizzenkarten (engl. sketch maps) mittels Constraints den Algorithmus
AC-3 zu einem Algorithmus namens
CN zum Lösen n-ärer Constraints
verallgemeinert (vgl. Mackworth, 1977b). Wie
AC-3 besitzt CN aufgrund
wiederholt vorkommender Konsistenztests für bereits getestete
Wertekombinationen eine weniger gute worst-case
Zeitkomplexität:
, wobei
die maximale Stelligkeit
der Constraints ist (siehe
Tabelle 5.1). Infolgedessen sollte
CN nur auf Constraints mit relativ geringer
Stelligkeit und kleinen Wertebereichen angewendet werden
(vgl. Bessière und Régin, 1997, S. 399).
Roger Mohr und Gérald Masini erweitern den Algorithmus
AC-4 und stellen GAC-4
(Generalized AC-4) vor, mit dem sich
Kantenkonsistenz auch für n-äre Constraint-Netze
herstellen lässt (vgl. Mohr und Masini, 1988). Ebenso wie
AC-4 ist GAC-4 ein
optimaler Algorithmus, und besitzt daher gegenüber
CN eine verbesserte worst-case
Zeitkomplexität: . GAC-4 hat
allerdings wie AC-4 den Nachteil der im
Durchschnitt weniger guten Zeitkomplexität und einer sehr hohen
Platzkomplexität. Letzteres entsteht, da
GAC-4 ebenso wie AC-4
auf eine speicherintensive, extensionale
Repräsentation der Constraints durch Wertetupel in Listen mit
support-Einträgen angewiesen ist (vgl. Abschnitt 5.2.3.3).
GAC-4 sollte daher ausschließlich auf CSPs
angewendet werden, die nur eine geringe Anzahl erlaubter Wertetupel
aufweisen und die entsprechend stark
beschränkenden Constraints bzw. kleine Wertebereiche beinhalten.
Zuletzt haben Christian Bessière und Jean-Charles Régin den Ansatz für einen Algorithmus GAC-Schema vorgestellt, der den Algorithmus AC-7 für n-äre Constraints nutzbar macht und deshalb z.T. auch GAC-7 genannt wird (vgl. Bessière und Régin, 1997). GAC-Schema kann sowohl auf extensionale als auch auf intensionale, algebraische Constraint-Repräsentationen angewendet werden, und ist bei deutlich reduzierter Speicherintensität ebenso wie GAC-4 ein optimaler Algorithmus.5.73 Eine experimentelle Evaluierung von GAC-Schema im Vergleich zu CN findet sich in der Arbeit von Sillito (2000).5.74 Mit GAC-Schema ist es aufgrund der Fähigkeit n-äre Constraint-Relationen zu verarbeiten möglich, mit relativ geringem Einsatz höhere Konsistenz als Kantenkonsistenz zu erzielen, indem Konjunktionen von (binären) Constraints betrachtet werden. Diese Art lokale Konsistenz wird conjunctive consistency genannt (vgl. Bessière und Régin, 1998). In Abhängigkeit von der Problemstellung kann der Mehraufwand zur Konsistenzherstellung einen Effizienzgewinn bedeuten oder nicht. Eine einfache Heuristik, mit der die Obergrenzen für die Anzahl der jeweils miteinander verknüpften Constraints festgelegt werden können, wird von Katsirelos und Bacchus (2001) vorgestellt.