next up previous contents index
Nächste Seite: 4.4 Ansätze zur Constraint-Verarbeitung Aufwärts: 4. Constraints - Konzepte Vorherige Seite: 4.2 Algebraische Constraints   Inhalt   Index

4.3 Eigenschaften von Constraints

Constraints bzw. Constraint-Netze können anhand unterschiedlicher Eigenschaften charakterisiert werden (vgl. Tsang, 1993, S. 46 ff.). Diese spezifischen Eigenschaften können zur Effizienzsteigerung durch Lösungsverfahren ausgenutzt werden. Bei der späteren Diskussion der Effektivität einzelner Lösungsverfahren bzw. -kombinationen bzgl. unterschiedlicher Problemstellungen wird auf diese Eigenschaften Bezug genommen.

Üblicherweise werden eine Reihe von allgemeinen Eigenschaften betrachtet. Neben der bereits angesprochenen Unterscheidung in Constraints mit finiten und infiniten Domänen und symbolischen und numerischen Wertebereichen, zählt dazu die Größe eines Problems. Sie betrifft sowohl die Anzahl der Variablen, den Umfang der Wertebereiche als auch die Anzahl der Constraints. Weiterhin ist häufig die Stelligkeit der Constraints von besonderem Interesse. Binäre Constraints setzen maximal zwei Constraint-Variablen zueinander in Relation. Bei allgemeinen Constraints ist diese Anzahl nicht begrenzt. Der Hintergrund ist, dass sich binäre Constraints im Gegensatz zu allgemeinen Constraints effektiver Propagieren lassen, da immer nur die Werte für eine Variable innerhalb eines Constraints bekannt sein müssen, um Werte für die jeweils andere ableiten zu können.

Die Stelligkeit einer Variable bezeichnet hingegen den Grad ihres Vorkommens in den Constraints, d.h. von wie vielen Constraints eine Variable beschränkt wird.

Für die Art der einzusetzenden Lösungsverfahren ist entscheidend, wie das gewünschte Ergebnis aussehen soll. So muss unterschieden werden, ob lediglich ein bestimmter Konsistenzgrad hergestellt werden soll, oder ob eine, eine bestimmte/optimale oder alle Lösungen benötigt werden. Je höher der hergestellte Konsistenzgrad (bei entsprechendem Aufwand), umso leichter fällt die anschließende Suche nach Lösungen, da vorher bereits eine größere Anzahl möglicher Variablenbelegungen als ungültig herausgefiltert wurde. Für global konsistente Constraint-Netze kann eine Lösung in linearer Zeit bestimmt werden (vgl. Abschnitt 5.2.3.5).

Von besonderem Interesse bzgl. der Effektivität von Lösungsverfahren ist ebenfalls die Struktur des Constraint-Netzes: Wenn ein Netz z.B. eine baumartige Struktur aufweist, oder in eine solche konvertiert werden kann, lässt sich das Problem in Polynomialzeit lösen (vgl. Abschnitt 5.2.3.5). Wenn dies nicht der Fall ist, bzw. nicht möglich ist, bieten sich einige strukturelle Anhaltspunkte, an der die Effektivität bestimmter Lösungsverfahren festgemacht werden kann:

Manche Lösungsmechanismen sind dementsprechend besser geeignet für Constraint-Probleme mit höherem Beschränkungsgrad, andere eignen sich besser für Probleme mit niedrigerer Beschränkung. Problemreduktion ist umso effektiver, je einschränkender die Constraints sind. Dies ist, neben der Anzahl der benötigten Lösungen, ein Grund dafür, weshalb stark beschränkte Constraint-Probleme nicht unbedingt härter zu lösen sein müssen als weniger stark beschränkte.

Bei schwach beschränkten Problemen sind im Verhältnis viele Blätter des Suchbaums Lösungen für das Constraint-Problem. Auch einfache Suchverfahren stoßen daher i.A. bereits frühzeitig auf eine Lösung. Verfahren zur Problemreduktion bzw. Konsistenzherstellung sind in diesem Fall unnötiger Overhead. Sollen sämtliche Lösungen ermittelt werden, wird ein schwach beschränktes Problem schnell sehr ,,hart``, denn aufgrund der vielen vorhandenen Lösungen muss durch den Mechanismus zur Lösungssuche ein in diesem Fall größerer Suchraum durchlaufen werden.

Je stärker beschränkt ein Problem ist, umso aufwendiger ist es für naive Suchalgorithmen, Lösungen zu finden. Ein stark beschränktes Problem ist daher härter, verglichen mit schwach beschränkten Problemen, wenn es darum geht, nur eine Lösung zu finden. Um alle Lösungen zu ermitteln, kann bei starker Beschränkung sinnvoll mit Mitteln zur Problemreduktion gearbeitet werden, so dass im Endeffekt ein geringerer Suchraum vom Lösungsalgorithmus durchlaufen werden muss (vgl. Tsang, 1993, S. 49).

Analog zum Grad der Beschränkung und entsprechend der Anzahl der vorhandenen Lösungen werden Constraint-Probleme in unter-, über- und wohlbestimmte Probleme unterschieden (vgl. Cheeseman et al., 1991, S. 331). Ein Constraint-Problem P heißt

Konfigurierungsprobleme sind in der Ausgangssituation häufig unterbestimmt (vgl. Fleischanderl et al., 1998, S. 66). In Konfiguratoren, die Benutzerinteraktionen zulassen, bzw. durch Konfigurierungskonflikte können allerdings überbestimmte Situationen entstehen. Für die Behandlung überbestimmter Constraint-Netze gibt es spezielle Konzepte, für die ein Überblick in Abschnitt 4.4.3 ff. gegeben wird.

Der Übergang zwischen unter- und überbestimmten Constraint-Problemen wird auch (engl.) phase transition region genannt. Dies ist der Bereich zwischen der Menge von Problemen, die fast alle viele Lösungen aufweisen und einfach zu lösen sind, und Problemen, die fast ausnahmslos keine Lösung aufweisen und deren Unlösbarkeit relativ einfach nachzuweisen ist. In der Phasenübergangsregion ist dementsprechend ein abrupter Wechsel der Lösungswahrscheinlichkeit für Probleme von nahezu 0 nach annähernd 1 zu beobachten (vgl. Cheeseman et al., 1991, S. 335). Probleme in diesem Übergangsbereich sind durchschnittlich relativ hart, d.h. mit höherem Schwierigkeitsgrad behaftet, und nur mit erhöhtem Aufwand zu lösen. Einzelne, besonders harte Probleme (engl. exceptionally hard problems) treten allerdings eher in Regionen auf, wo sich ansonsten eher leicht zu lösende Probleme befinden. Dies ist allerdings wiederum abhängig von den eingesetzten Lösungsverfahren, so dass formuliert werden kann, dass Probleme, die für bestimmte Lösungsalgorithmen besonders hart zu lösen sind, für andere Algorithmen sehr leicht zu lösen sein können vgl. Grant und Smith, 1995, S. 2 f.; Grant und Smith, 1996, S. 175.

Zur Beantwortung der Frage, welche Lösungsverfahren für welche Problemstellungen sinnvoll eingesetzt werden können, werden neben theoretischen Überlegungen und worst-case Analysen überwiegend empirische Untersuchungen herangezogen, da worst-case Analysen ihrer Natur nach pessimistisch sind und häufig nicht die Praxistauglichkeit eines Algorithmus reflektieren. Üblicherweise werden zur empirischen Evaluierung von Lösungsalgorithmen relativ harte Probleme aus der Phasenübergangsregion mit Hilfe von Problemgeneratoren erzeugt vgl. Dechter, 1999, S. 196 f.; Gülden, 1993, S. 33.4.8

Um eine Vielzahl unterschiedlicher Constraint-Probleme effizient Verarbeiten zu können, sind daher ebenso unterschiedliche Constraint-Solver notwendig. In Bezug auf die strukturbasierte Konfigurierung und das Konfigurierungswerkzeug ENGCON ist daher eine flexible Lösung anzustreben, die in Abhängigkeit von der Problemstellung den Einsatz von jeweils geeigneten Lösungsalgorithmen ermöglicht.



Fußnoten

...4.7
Es wird in diesem Fall davon ausgegangen, dass zwischen einer Menge von Variablen jeweils nur ein einziges (totales) Constraint besteht, welches sämtliche Abhängigkeiten zwischen genau diesen Variablen beschreibt (vgl. Definition 4.1.2).
...4.8
Problemgeneratoren setzen allerdings i.A. eine extensionale Repräsentation der Constraints und eine entsprechende Verarbeitung durch Lösungsalgorithmen voraus.

next up previous contents index
Nächste Seite: 4.4 Ansätze zur Constraint-Verarbeitung Aufwärts: 4. Constraints - Konzepte Vorherige Seite: 4.2 Algebraische Constraints   Inhalt   Index