Der nachfolgende Überblick über Suchstrategien ist auf der Grundlage des
Tutorial on Search in ECLiPSe enstanden, welches Bestandteil der ECLiPSe Dokumentation ist.
Wir haben es also in der Constraint Logic Programmierung mit folgendem Muster zu tun:
solve(Data) :- model(Data, Variables), search(Variables), print_solution(Variables).In dem Modell werden die Werte und zugehörigen Constraints definiert. Die Suche muß erfolgen, da im Normalfall nicht davon ausgegangen werden kann, daß die Constraints alleine nur zu einer einzigen Lösung führen.
Constructive Suchmethoden arbeiten mit inkrementellen Assignments, das heißt, daß
den Problemvariablen schrittweise Werte zugewiesen werden. Daraus ergibt sich, daß
diese Methoden den Suchraum anhand einer Baumstruktur organisieren.
Move-Based Suchmethoden arbeiten mit Sprüngen zwischen Total Assignments. Unter einem
Total Assignment versteht man die vollständige Belegung aller Problemvariablen mit
Werten aus deren Wertebereich.
Durch methodische Modifikation einzelner Problemvariablen, ausgehend von einem
vorherigen Total Assignment, wird der Suchraum erforscht.
Dieses Verfahren ist seiner Natur nach sehr speicherintensiv,
da sich das System die bereits getesteten Kombinationen merken muß. An dieser
Stelle sei gesagt, daß in dieser Ausarbeitung nicht näher auf diese Art von
Suchstrategien eingegangen wird.
Es gibt noch zwei Kriteria, anhand derer sich die verschiedenen Suchmethoden charakterisieren
lassen. Zum einen ist es die Unterscheidung, ob es sich um eine vollständige
oder um eine unvollständige Suche handelt und zum anderen, ob es Zufallselemente
in dem Suchalgorithmus gibt.
Eine vollständige Suche ist immer dann notwendig, wenn eine Optimallösung gesucht
wird, denn eine optimale Lösung kann nur gefunden werden, wenn alle möglichen
Lösungen miteinander in Beziehung gesetzt werden.
Eine unvollständige Suche hingegegen kann immer dann eingesetzt werden, wenn nur nach einer
oder einer relativ guten Lösung gesucht wird.
Die traditionelle Methode in der CLP Welt ist die Anwendung von Heuristik und Pruning
im Rahmen der systematischen Baumsuche (also Constructive Suchmethoden). Pruning bedeutet das Beschneiden des Suchraumes
durch Constraints. Teile des Suchbaumes werden exkludiert, indem bewiesen wird, daß sie
keine Lösungen enthalten.
Unter Heuristik wird in diesem Bereich die methodische Anordnung des Suchbaumes
verstanden, so daß vielversprechende Subräume zuerst traversiert werden.
Ein Beispiel verdeutlicht dieses:
Wir betrachten die zwei Domain Variablen:
X1 :: 0..1 X2 :: 0..3Die graphische Veranschaulichung des Suchraumes anhand eines Baumes:
Hierbei wird der gesamte Baum traversiert. Durch eine geeignete Heuristik kann die
Zeit und die Anzahl der Backtracks bis zur ersten gültigen Lösung
dramatisch reduziert werden. Es sei an dieser Stelle auf das Fallbeispiel im
nächsten Kapitel hingewiesen.
Unter der Bounded Backtrack Methode versteht man die Festlegung einer maximalen Anzahl von Backtracks. Es erfolgt ein Buchführen über die erfolgten Backtracks. Bei der Überschreitung des Limits wird die Suche abgebrochen, auch wenn noch keine Lösung gefunden wurde. Es handelt sich also um eine unvollständige Suche, die einer gut gewählten Heuristik bedarf.
Dieses Verfahren beruht auf Festlegung eines "Kreditrahmens" für einen Baum.
Ausgehend vom Wurzelknoten wird der Kreditrahmen des Elternknotens zu gleichen Teilen
auf die Kindsknoten aufgeteilt.
Dabei ist die einzelne Krediteinheit atomar. Für Subbäume deren Wurzel
nur eine Krediteinheit besitzt, gilt damit die Regel, daß nur ein Blatt besucht
werden darf. Dabei wird der jeweils linke Pfad gewählt.
Subbäme für die kein Kredit mehr vorhanden ist, werden nicht besucht.
Bei der Kreditrahmenvergabe ist folgendes zu berücksichtigen:
Hier wird die Suche nach Ablauf einer vorab definierten Laufzeit abgebrochen und
die bis dahin beste gefundene Lösung präsentiert.