5.2.4 Suchverfahren

Die Anwendung von Konsistenztechniken führt i.A. nicht zu einer Lösung eines CSP. Es ist daher notwendig, zusätzliche Algorithmen zum Auffinden von Lösungen anzuwenden. Diese Suchverfahren können nach dem Herstellen einer lokalen Konsistenz, oder kombiniert mit Konsistenztechniken zum Einsatz kommen (vgl. Güsgen, 2000, S. 275).

Suchverfahren zur Bestimmung von Lösungen in einem CSP werden unterschieden in systematische und stochastische Verfahren. In diesem Abschnitt werden ausschließlich systematische Suchverfahren vorgestellt. Systematische Verfahren werden auch globale Suchverfahren genannt, da sie auf das CSP in seiner gesamten Struktur angewendet werden. Im Gegensatz zu stochastischen Verfahren sind sie vollständig, d.h. es ist garantiert, dass alle existierenden Lösungen gefunden werden, wenn es welche gibt. Stochastische Suchverfahren sind unvollständig und betrachten das CSP anhand lokaler Kriterien. Sie garantieren nicht, dass eine gefundene Lösung globale Gültigkeit besitzt und werden deshalb auch lokale Suchverfahren genannt (vgl. Abschnitt 5.2.2).

Bei der Anwendung von Suchverfahren nehmen die Constraints i.A. eine passive Rolle ein, da die Strategie zur Lösung des Problems durch den Lösungsalgorithmus vorgegeben ist. Die Constraints werden durch das Suchverfahren dazu genutzt, durch Testen von generierten (Teil-)Lösungen Inkonsistenzen, d.h. ungültige Variablenbelegungen, zu entdecken und ungültige Werte auszuschließen. Bei dieser a posteriori Reduktion des Suchraums können die Eigenschaften eines CSP genutzt werden, um effizient zu einer Lösung zu gelangen.

Die Performanz der Suche kann gesteigert werden, indem der Suchraum reduziert wird. Dies kann durch die Kontrollstrategie des Suchalgorithmus beeinflusst werden, durch Herstellen eines lokalen Konsistenzgrades, durch die Reihenfolge, in der die Variablen ausgewählt werden und, wenn nur eine einzige Lösung benötigt wird, durch die Reihenfolge der Werte in den Domänen, mit denen die Variablen während des Suchvorgangs belegt werden (vgl. Dechter und Frost, 2002, S. 155 f.). Infolgedessen wurden zwei Arten von Vorgehensweisen entwickelt: Zum einen kann ein Preprozessing des CSP vor der eigentlichen Suche stattfinden. Hier kommen häufig Algorithmen zur Herstellung von Kanten- und Pfadkonsistenz sowie Heuristiken zur Generierung einer statischen Variablenordnung zum Einsatz. Zum anderen gibt es Verfahren, die während der Suche mittels look-ahead- und look-back-Strategien die Effizienz der Suche beeinflussen. Dies sind z.T. kombinierte Verfahren, die zur Problemreduktion dynamisch während des Suchvorgangs Konsistenztechniken und Heuristiken einsetzen. Die Strategien der hier beschriebenen Suchverfahren können, wie in Tabelle 5.2 dargestellt, in drei Kategorien klassifiziert werden vgl. Dechter und Frost, 1998, S. 3 f.; Dechter und Frost, 2002, S. 155 f.; Tsang, 1993, S. 119 f.:

Tabelle 5.2: Klassifizierung von Suchstrategien

allgemeine Suchstrategien	Generate & Test (GT)
	chronologisches Backtracking (BT)
look-back-Strategien	Backjumping (BJ)
	Backchecking (BC)
	Backmarking (BM)
look-ahead-Strategien	Forward Checking (FC)
	Partial Look-Ahead (PLA)
	Full Look-Ahead (FLA) bzw.
	Maintaining Arc Consistency (MAC)

1. Allgemeine Suchstrategien sind für generelle Problemstellungen geeignet. Sie ziehen keinen Nutzen aus den Constraints bzw. der Struktur eines CSP, um die Effizienz der Suche zu erhöhen.

2. Look-Back-Strategien können angewendet werden, wenn Backtracking aufgrund einer inkonsistenten Variablenbelegung notwendig wird. Das Ziel ist es, Zweige im Lösungsbaum, die zu keiner Lösung führen, nicht mehrmals zu durchlaufen. Dies kann auf zwei Arten erreicht werden: Zum einen kann die Inkonsistenz analysiert werden, um zu ermitteln, wie weit die Suche durch das Backtracking zurückgesetzt werden muss, d.h. wie weit im Suchbaum zurückgesprungen werden muss, um irrelevante Backtracking-Punkte zu vermeiden (sog. backjumping). Die Suche kann dadurch ggf. direkt an einem Punkt fortgesetzt werden, der vormals eine Inkonsistenz ausgelöst hat. Zum anderen können durch look-back-Strategien Inkonsistenzen bei der Belegung von Constraint-Variablen erfasst werden. Sollte Backtracking notwendig werden ist auf diese Weise sichergestellt, dass inkonsistente Variablenbelegungen nicht wiederholt getestet werden.

3. Look-Ahead-Strategien besitzen eine vorausschauende Komponente. Sie werden von kombinierten Verfahren angewendet, die jeweils nach der Festlegung eines Wertes durch den Suchalgorithmus Konsistenztechniken und Constraint-Propagation nutzen, um eine Reduzierung des Suchraums zu erzielen und die Effizienz der Suche zu steigern. Anschließend, nach dem Durchführen der Propagation und den damit einhergehenden Einschränkungen der Wertebereiche der Constraint-Variablen, kann mittels Heuristiken bestimmt werden, welche Variable als nächstes mit welchem Wert aus ihrer Domäne belegt werden sollte, um möglichst schnell zu einer Lösung zu gelangen (vgl. Abschnitt 5.2.5).

Im Folgenden werden eine Reihe von systematischen Suchverfahren vorgestellt, die zur Bestimmung von Lösungen in FCSPs geeignet sind. Die Auflistung erhebt keinen Anspruch auf Vollständigkeit, sondern gibt einen Überblick über die grundlegenden bzw. gängigen Techniken.