5.3.7 $2^k$-Baum-Methode

Djamila Sam-Haroud und Boi V. Faltings stellen ein Verfahren vor, mit dem globale Konsistenz in ICSPs hergestellt werden kann (vgl. Haroud und Faltings, 1994; Sam-Haroud, 1995). Der Lösungsraum wird dazu in einer hierarchischen Zerlegung in Form von $2^k$-Bäumen (engl. $2^k$-trees) repräsentiert. $2^k$-Bäume sind eine Repräsentationsform, die üblicherweise in der Bildverarbeitung Anwendung findet. Der Lösungsraum wird dazu in drei Kategorien eingeteilt und farblich markiert:

1. Bereiche, die ausschließlich Lösungen enthalten (weiß),

2. Bereiche, die Lösungen enthalten, aber auch Punkte, die nicht Teil der Lösung sind (grau), und

3. Bereiche, die keine Lösung enthalten (schwarz).

Die grauen Bereiche, die sowohl Lösungen als auch Elemente enthalten, die nicht Teil einer Lösungen sind, werden in neue Unterbereiche zerteilt und wiederum klassifiziert. Dies geschieht so lange, bis eine definierte Präzisionsgrenze erreicht wird, d.h. die zerteilten Bereiche eine bestimmte Größe erreicht haben. Der Lösungsraum wird bei diesem Vorgehen quasi durch eine Menge konsistenter Boxen ,,aufgefüllt``. Das Verfahren ist daher eher für die Berechnung von Lösungsräumen anstatt für punktgenaue Lösungen vorgesehen.^5.109

Fußnoten

...^5.109

Beispielsweise für Anwendungen aus dem Bereich Diagnose und Design, in denen unterbestimmte Probleme (engl. under-constrained problems) durch Ungleichheits-Constraints auftreten können.