next up previous contents index
Nächste Seite: 5.2.6.2 Binärisierung von Constraints Aufwärts: 5.2.6 Behandlung von höherwertigen Vorherige Seite: 5.2.6 Behandlung von höherwertigen   Inhalt   Index

5.2.6.1 Direkte Verarbeitung allgemeiner CSPs

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

Definition 5.2.12   (Hyperkantenkonsistenz/generalized arc consistency, GAC)
Gegeben sei ein CSP auf den Variablen $v_1,\ldots,v_n$ mit den Wertebereichen $D_1,\ldots,D_n$. Sei $C_{j,\ldots,k}$ ein Constraint mit der Relation $R_{j,\ldots,k}$, welche für die Variablen $v_j,\ldots,v_k$ mit $j,\ldots,k \in \{1,\ldots,n\}$ gültige Belegungen spezifiziert. Eine Belegung ist kantenkonsistent, gdw. $\forall v_i \in V$, $\forall d_i
\in D_i$, $\forall R_{j,\ldots,k}$, die $v_i$ beschränken, $\forall v_j,\ldots,v_k$, $\exists
d_j,\ldots,d_k$, so dass $R_{j,\ldots,k}(d_j,\ldots,d_k)$ erfüllt ist.

Dies bedeutet lediglich, dass für jede Belegung $d_i$ von jedem Knoten $v_i$ gültige Belegungen in den Domänen der Variablen $v_j,\ldots,v_k$ 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: $O(er^2d^{r+1})$, wobei $r$ 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: $O(ed^r)$. 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.



Fußnoten

...5.71
Ebenso wie FC, PLA und FLA bzw. MAC unterschiedliche Grade Kantenkonsistenz erreichen, werden von Bessière et al. (1999c,2002,1999b) eine Reihe von unterschiedlichen FC-Algorithmen diskutiert, die z.T. die im Folgenden vorgestellten Algorithmen zur Herstellung von Hyperkantenkonsistenz nutzen, und dabei unterschiedliche Grade lokaler Konsistenz erreichen.
...5.72
Die worst-case Zeitkomplexität von Algorithmen zur Herstellung von Hyperkantenkonsistenz besitzt ein exponentielles Wachstum bezogen auf die maximale Stelligkeit der Constraints.
...5.73
GAC-Schema kommt z.B. im ILOG Solver zum Einsatz (vgl. Abschnitt 4.5.2).
...5.74
Der Algorithmus CN wird von Sillito (2000) mit GAC-3 benannt.

next up previous contents index
Nächste Seite: 5.2.6.2 Binärisierung von Constraints Aufwärts: 5.2.6 Behandlung von höherwertigen Vorherige Seite: 5.2.6 Behandlung von höherwertigen   Inhalt   Index