5.2.6.2 Binärisierung von Constraints

Statt der direkten Verarbeitung n-ärer Constraints ist es möglich, eine Transformation in binäre Constraints vorzunehmen. Dies kann vorteilhaft sein, da für binäre Constraints eine Vielzahl an Algorithmen und Heuristiken bekannt sind, die z.T. für n-äre Constraints bisher nicht anwendbar sind.^5.75 Durch die einfache Projektion eines n-ären Constraints auf Paare von binären Constraints auf denselben Variablen wird allerdings die ursprüngliche Lösungsmenge lediglich durch eine Obermenge approximiert (vgl. Barták, 2001, S. 8). Nur für bestimmte n-äre Constraint-Arten, wie z.B. dem all-different-Constraint ( $v_1 \neq v_2 \neq \ldots \neq v_k$), erhält man eine Menge von binären Constraints mit derselben Lösungsmenge wie das ursprüngliche CSP. Um ein äquivalentes Constraint-Netz mit derselben Lösungsmenge wie das originale CSP zu erhalten, ist i.A. die Einführung zusätzlicher Variablen notwendig. Diese neuen Variablen umfassen jeweils die Menge der durch ein n-äres Constraint beschränkten Variablen in Form des kartesischen Produkts der jeweiligen Wertebereiche.^5.76 Ein beliebiges n-äres Constraint lässt sich nun durch eine solche umfassende Variable (engl. encapsulated variable) darstellen, indem dessen Wertebereich um die nicht erlaubten Wertekombinationen reduziert wird.

Beispiel 5.2.8   Das n-äre Constraint

$$C_{1,2,3}: v_1 + v_2 = v_3$$

mit den Wertebereichen

$$v_1: \{1,2\}, \quad v_2: \{3,4\}, \quad v_3: \{5,6\}$$

lässt sich auf diese Weise durch die umfassende Variable

$$u: \{(1,4,5),(2,3,5),(2,4,6)\}$$

repräsentieren, wobei sich die erste Stelle dieser Tripel jeweils auf einen Wert von $v_1$, die zweite auf $v_2$ und die dritte entsprechend auf $v_3$ bezieht (vgl. Güsgen, 2000, S. 271).

Diese Variablen bzw. Lösungen für einzelne n-äre Constraints werden anschließend mittels binärer Constraints verknüpft, um die Gesamtlösungen für das CSP berechnen zu können. Es werden zwei unterschiedliche Arten der Konvertierung von n-ären nach binären Constraint-Netzen unterschieden: die Hidden-Variable-Repräsentation und die Dual-Graph-Repräsentation, die im Folgenden kurz skizziert werden.

Hidden-Variable-Repräsentation:

Für den Ursprung der Hidden-Variable-Repräsentation wird von Rossi et al. (1989, S. 3) auf die Arbeit von Peirce (1933) verwiesen. Hier wurde von Charles S. Peirce auf dem Gebiet der philosophischen Logik bereits formal nachgewiesen, dass binäre Relationen grundsätzlich dieselbe Ausdrucksstärke wie n-äre Relationen besitzen.^5.77 Auf der Methode von Peirce aufbauend, zeigt Dechter (1990b), wie jede n-äre Relation mittels binärer Relationen und Nutzung von umfassenden Variablen, in diesem Fall Hidden-Variablen genannt, mit begrenzten Wertebereichen dargestellt werden kann. Bei der Hidden-Variable-Repräsentation werden umfassende Variablen und originale Variablen kombiniert. Lediglich die n-ären Constraints werden in umfassende bzw. Hidden-Variablen transformiert, an die wiederum die originalen Variablen durch zusätzliche binäre Kompatibilitäts-Constraints, auch Hidden-Constraint genannt, gebunden werden. Hierfür wird eine Projektion $\pi$ eingeführt, welche die Relation $v = i$-tes Argument von $u$ beschreibt:

$$v = \pi_i(u)$$

Die Werte aus der Domäne der Variable $v$ werden auf die $i$-te Stelle der Tupel aus dem Wertebereich der umfassenden Variable $u$ projiziert (d.h. $i$ ist die Position von $v$ in $u$). Ein Beispiel für ein derartig transformiertes, binäres Constraint-Netz ist in Abbildung 5.19 zu sehen. Von Vorteil ist bei diesem Vorgehen der Erhalt der originalen Variablen. Lösungen können direkt abgelesen werden, ohne dass eine Umsetzung anhand der Hidden-Variablen vorgenommen werden muss. Zudem müssen weniger Constraints in der speicheraufwendigen, extensionalen Repräsentation in den umfassenden Variablen kodiert werden, als bei der Dual-Graph-Repräsentation (vgl. Barták, 2003).

Abbildung 5.19: Hidden-Variable-Repräsentation n-ärer Constraints (vgl. Barták, 2003)

Dual-Graph-Repräsentation:

Die Repräsentation als Dual-Graph stammt ursprünglich aus dem Bereich der relationalen Datenbanken und wurde von Rina Dechter und Judea Pearl in den CSP-Bereich eingeführt (vgl. Dechter und Pearl, 1989).^5.78 Bei der Dual-Graph-Repräsentation wird das umgewandelte, binäre CSP ausschließlich durch umfassende Variablen dargestellt, d.h. auch binäre Constraints werden konvertiert.^5.79 Ein Dual Graph ist dadurch gekennzeichnet, dass die Knoten und Kanten im Gegensatz zur normalen Darstellung, auch Primal Graph genannt, vertauscht sind vgl. Dechter und Pearl, 1989, S. 355; Stergiou und Walsh, 1999, S. 164. Im Fall der Binärisierung eines n-ären CSP sind die Constraints extensional in den Knoten, d.h. in den Wertebereichen der umfassenden Variablen, hier Dual-Variablen genannt, enthalten. Die Kanten hingegen repräsentieren die gemeinsamen Variablen der Constraints vgl. Rossi et al., 1989, S. 3; 1990, S. 554. Während ein Primal Graph für den allgemeinen Fall auch n-äre Constraints enthalten kann, ist sein entsprechender Dual Graph immer ein binärer Graph vgl. Rossi et al., 1989, S. 21; 1990, S. 555. Wird eine Variable ursprünglich von mehreren Constraints beschränkt, so werden die entsprechenden Dual-Variablen in der Dual-Graph-Repräsentation über ein binäres Kompatibilitäts- bzw. Dual-Constraint miteinander verbunden. Hierfür wird wiederum die Projektion $\pi$ genutzt, in diesem Fall zur Beschreibung der Relation $i$-tes Argument von $u_1$ = $j$-tes Argument von $u_2$:

$$\pi_i(u_1) = \pi_j(u_2)$$

Diese Relation verknüpft somit jeweils die $i$-te mit der $j$-ten Stelle der Wertetupel zweier umfassender Variablen. Das vormalig bereits vorgestellte n-äre Constraint-Netz ist in binärer Dual-Graph-Repräsentation in Abbildung 5.20 dargestellt. Dieses Constraint-Netz ist überschaubarer als das in Abbildung 5.19 dargestellte transformierte CSP, allerdings müssen für die Bestimmung einer Lösung des ursprünglichen CSPs die Variablenbelegungen aus den Dual-Variablen extrahiert und den originalen Variablen zugewiesen werden (vgl. Barták, 2003). Die hierfür benötigten Informationen werden separat zwischengespeichert. Das resultierende Constraint-Netz ist eine vollständig extensionale Repräsentation der Constraints, da alle für einzelne Constraints gültigen Kombinationen in den umfassenden Variablen enthalten sind.

Abbildung 5.20: Dual-Graph-Repräsentation n-ärer Constraints (vgl. Barták, 2003)

Von Kostas Stergiou und Toby Walsh wird außerdem eine Kombination der Hidden-Variable- und Dual-Graph-Repräsentation eingeführt, die Double-Repräsentation (vgl. Stergiou und Walsh, 1999). Sie vereint sowohl die Vor- als auch die Nachteile der beiden vorher genannten Repräsentationen, da beide vollständig enthalten sind. Es existieren sowohl die originalen Variablen als auch die Dual-Variablen, und neben den Dual-Constraints zwischen den Dual-Variablen sind ebenfalls die Hidden-Constraints zwischen den originalen und den Dual- bzw. Hidden-Variablen enthalten.

Ebenfalls von Stergiou und Walsh (1999), aber auch von Bacchus et al. (2002), wird festgestellt, dass Kantenkonsistenz angewandt auf ein Constraint-Netz in Dual-Graph-Repräsentation einen höheren Grad lokaler Konsistenz erreicht als Hyperkantenkonsistenz auf der ursprünglichen n-ären Form, da bedingt durch die extensionale Repräsentation mehr inkonsistente Wertekombinationen aus den Domänen der Variablen herausgefiltert werden können.^5.80 Kantenkonsistenz angewandt auf ein Constraint-Netz in Hidden-Variable-Repräsentation hingegen ist äquivalent zur Hyperkantenkonsistenz in der n-ären Form.^5.81

Die Frage, ob die Transformation eines n-ären CSP in eines binäres CSP sinnvoll ist, muss in Abhängigkeit von der Problemstellung und von der Modellierung des Problems beantwortet werden. Idealerweise ist ein CSP in der natürlichsten Art und Weise modelliert, und der Rechner löst es möglichst auf die effizienteste Art und Weise (vgl. Bacchus und van Beek, 1998, S. 312). In diesem Fall muss der Wissensingenieur die Entscheidung treffen, und in der Wissensbasis zusammen mit der Problemstellung definieren, ob eine Konvertierung vorgenommen werden soll oder nicht. Wobei für die meisten Probleme die n-äre Repräsentation die effizientere bzgl. der Anwendung von Lösungsverfahren ist. Für eine Klasse von stark einschränkenden Constraints, kann die binäre Transformation jedoch wesentlich effizienter sein (vgl. Bacchus und van Beek, 1998; Bacchus et al., 2002).

Aufgrund der vollständig extensionalen Darstellung im Dual-Graph lohnt sich diese Repräsentation umso mehr, je weniger erfüllbare Wertetupel die Constraints aufweisen. Je größer die Menge der zu verwaltenden Wertetupel ist, umso schlechter verhält sich das Laufzeitverhalten der Lösungsverfahren, da umso mehr Konsistenztests durchgeführt werden müssen, die u.U. in der n-ären Repräsentation redundant sind (vgl. Bacchus und van Beek, 1998, S. 314). Ähnlich, jedoch nicht ganz so ausgeprägt, gilt dies ebenfalls für die Hidden-Variable-Repräsentation, da hier ausschließlich die n-ären Constraints in Hidden-Variablen transformiert werden, und der Zugriff auf die originalen Variablen erhalten bleibt. Bacchus und van Beek (1998) stellen zudem einen eigens für die Hidden-Variable-Repräsentation angepassten Algorithmus FC$^+$ vor, der eine höhere Reduktion erreicht, als der normale FC-Algorithmus. In der Double-Repräsentation können flexibel die Vorteile der einen wie der anderen Repräsentation genutzt werden. Weiterhin lassen sich bei Bedarf unterschiedliche hybride Repräsentationen erzeugen, die u.U. spezielle Constraints nur in der einen oder anderen Repräsentation enthalten, um z.B. die Nachteile der extensionalen Darstellung für bestimmte Constraints zu umgehen (vgl. Stergiou und Walsh, 1999; Smith et al., 2000). Dies erfordert jedoch zusätzlichen Anpassungsaufwand des Lösungsverfahrens an die Problemstellung.

Fußnoten

...^5.75

Beispielsweise MFC und LAC (vgl. Bacchus und van Beek, 1998, S. 311).

...^5.76

Bei einem FCSP sind die Domänen der Variablen endlich, insofern ist das kartesische Produkt dieser Wertebereiche ebenfalls endlich.

...^5.77

Indem gezeigt wurde, dass ein Ansatz, der Variablen hinzufügt, um binäre Relationen zu erhalten, mit der originalen Repräsentation logisch äquivalent ist.

...^5.78

Ein inkrementeller Algorithmus, der diese Methode zum Auffinden aller Lösungen innerhalb eines CSPs nutzt, wurde von Freuder (1978) bereits mit seinem Synthese-Algorithmus (vgl. Abschnitt 5.2.3.5) vorgestellt (vgl. Bacchus und van Beek, 1998, S. 311).

...^5.79

Tatsächlich lässt sich die Dual-Graph-Repräsentation aufbauend auf der Hidden-Variable-Repräsentation erzeugen, indem die zusätzlichen Dual-Variablen und Dual-Constraints erzeugt und die originalen Variablen entfernt werden vgl. Bacchus et al., 2002, S. 8; Stergiou und Walsh, 1999, S. 164 f..

...^5.80

Auch wenn Hyperkantenkonsistenz für ein n-stelliges Constraint hergestellt wurde, sind anschließend mit den Wertebereichen der beteiligten Constraint-Variablen i.d.R. Wertekombinationen möglich, die keine Lösung des Constraints darstellen. Dies ist bei einer extensionalen Constraint-Repräsentation nicht möglich, da hier ausschließlich gültige Kombinationen vorausgesetzt werden. So lässt sich in bestimmten Situationen in der Dual-Graph-Repräsentation z.B. feststellen, dass ein CSP nicht lösbar ist, während dies mit Hyperkantenkonsistenz in der n-ären Repräsentation nicht gelingt (vgl. Bacchus et al., 2002, S. 13).

...^5.81

Wenn die zusätzliche Reduktion der ausschließlich erlaubten Wertekombinationen in den Hidden-Variablen nicht beachtet wird (vgl. Stergiou und Walsh, 1999, S. 166).