6.4 Ein hybrides Constraint-System

Ein hybrides Constraint-System zeichnet sich dadurch aus, dass es in der Lage ist, ein hybrides Constraint Satisfaction Problem zu verarbeiten:

Definition 6.4.1   (Hybrides Constraint Satisfaction Problem)
Ein System zur Verarbeitung eines hybriden Constraint Satisfaction Problems H wird durch die Angabe von sieben Komponenten

$$H = (C, S, \delta, V_{fd}, D_{fd}, V_{int}, D_{int})$$

beschrieben. Dabei ist $C = \{C_1,\ldots,C_m\}$ eine endliche Menge von Constraints und $S = \{S_1,\ldots,S_n\}$ eine endliche Menge von Constraint-Lösungsstrategien. Die Funktion $\delta$ ordnet jedem Constraint $C_i$, $i \in \{1,\ldots,m\}$, eine eindeutige Strategie $S_j$, $j \in \{1,\ldots,n\}$, zu:

$$\delta: C_i \rightarrow S_j.$$

Der Bezeichner $V_{fd}$ steht für eine endliche Menge von FD-Variablen $\{v_1,\ldots,v_k\}$, mit denen die Wertebereiche $D_{fd} = \{D_1,\ldots,D_k\}$ mit $\{v_1 : D_1,\ldots,v_k : D_k\}$ assoziiert sind. Ebenso sind die Intervallvariablen $V_{int} = \{v_1,\ldots,v_l\}$ mit den Wertebereichen $D_{int} = \{D_1,\ldots,D_l\}$ mit $\{v_1 : D_1,\ldots,v_l : D_l\}$ assoziiert. Jedes Constraint $C_i$ setzt eine Teilmenge der Variablen aus $V_{fd}$ und $V_{int}$ zueinander in Relation und beschränkt deren gültige Wertekombinationen auf eine Teilmenge des kartesischen Produkts ihrer Wertebereiche.

Ein hybrides CSP vereinigt somit Constraints über Variablen mit finiten und infiniten Domänen. Jedem Constraint ist eine Lösungsstrategie zu dessen Verarbeitung zugeordnet. Dies führt zu einer Aufteilung des ursprünglichen Constraint-Problems in unterschiedliche Teilprobleme, welche durch die jeweils zuständige Constraint-Lösungsstrategie definiert werden (vgl. Abbildung 6.3).^6.4 Zur ,,Überlappung`` unterschiedlicher Teilprobleme kann es kommen, wenn eine Variable in strukturell unterschiedlichen Teilproblemen auftaucht, d.h. in Constraints, die unterschiedlichen Strategien zugeordnet sind.

Abbildung 6.3: Zuständigkeiten unterschiedlicher Strategien für Teilbereiche des Constraint-Problems

Wie der Ablauf zur Verarbeitung von einem derartigen, hybriden Constraint-Problem aussieht und wie mögliche Überlappungen der Teilprobleme unterschiedlicher Constraint-Lösungsstrategien behandelt werden können, wird in den folgenden Abschnitten erläutert.

Fußnoten

...^6.4

Teilprobleme entstehen, indem mehrere Constraints derselben Strategie zugeordnet werden.