Suchstrategien

Übersicht: Titel

• Klassifizierung
• Generate and Test
• Backtracking
• Forward Checking
• Heuristik
• Variablenordnung
• Werteordnung

Bei constructive Algorithmen erfolgt eine inkrementelle Wertezuweisung an die Variablen. Dies impliziert, dass der Suchraum anhand einer Baumstruktur organisiert wird. Moved-based Algorithmen arbeiten hingehen mit total assignments, also mit zeitgleichen Zuweisungen von Werten an alle Variablen. Der Suchraum wird hierbei durch methodische Modifikation einzelner Problemvariablen ausgehend von vorherigen Zuweisungen untersucht, soll heißen, dass daraus neue total assignments abgeleitet und getestet werden, bis eine oder alle Lösungen gefunden worden sind. Diese Art der Suche erweist sich jedoch als sehr speicherintensiv, da alle überprüften möglichen Lösungen gemerkt werden müssen. Gerade bei sehr komplexen Problemen kann dies zu Schwierigkeiten führen. Im weiteren Verlauf werden nur noch constructive Algorithmen betrachtet.

Die Suchstrategien können zudem noch nach vollständiger und unvollständiger Suche klassifiziert werden. Bei der vollständigen Suche wird der gesamte Suchbaum traversiert. Dies ist beispielsweise bei der Suche nach der optimalen Lösung notwendig. Hingegen wird bei der unvollständigen Suche nur ein Teil des Suchbaums betrachtet. So kann bei sehr komplexen Aufgabenstellungen die zulässige Anzahl an Rücksprüngen (auf Rücksprünge wird im Folgenden noch näher eingegangen) angegeben werden. Sollte bis dahin noch keine Lösung gefunden worden sein, wird die Suche abgebrochen.

In obiger Grafik repräsentiert jeder Knoten für eine Problemvariable, jede Kante für einen Wert, den die Problemvariable annehmen kann und jeder Punkt für eine mögliche Wertkombination. Das Prinzip der Tiefensuche wird auch in den anderen vorgestellten Suchstrategien verwendet, es erfolgt allerdings jeweils eine Weiterentwicklung, um effizienter zu einer möglichen Lösung zu gelangen.

Das Backtracking soll an folgendem einfachen Beispiel verdeutlicht werden.

:- lib(fd). solve(Triple) :-     Triple = [X, Y ,Z],     [X, Z] :: 1..2,     Y :: 1..3,     X #> 1,     Y #>= X,     Z #< Y,     labeling(Triple).

Der Suchbaum sieht in diesem Fall folgendermaßen aus:

Suchbaum Backtracking

Zur Erklärung: Die erste Variable, X, wird mit dem ersten Wert aus ihrer Domain belegt (1). Da dieser Wert jedoch auch gegen das erste Constraintatom verstößt, wird der nächste Wert aus der Domain gewählt. Somit wird zugleich der linke Teilbaum abgeschnitten, sodass bereits nach der ersten Variablenbelegung die Hälfte aller möglichen Lösungen ausgeschlossen werden kann. Die oben beschriebene Systematik wird nun weiter verfolgt, bis man zur ersten Lösungsmenge (2,2,1) gelangt. Um hiernach eine weitere Lösung zu erhalten, muss darauf ein Rückschritt von der bereits belegten Variable Z zu der Variablen Y erfolgen, welche nun mit 3 belegt wird. Aus dieser Position werden dann durch Belegen der Variablen Z die anderen beiden Lösungen gefunden.

Das Forward Checking soll an dieser Stelle an obigem Beispiel nochmals kurz verdeutlicht werden. Unter der Annahme, dass X mit 2 belegt ist, wird der Wert 1 aus der Domain der Variablen Y belegt. Hierdurch wird der Baum schon ohne die Belegung von Y weiter beschnitten.

Generell soll die Variablenordnung nach dem Fail-First-Prinzip festgelegt werden. Dieses besagt: "Um erfolgreich zu sein, probiere das zuerst, was am wahrscheinlichsten zum Fehler führt!". Hieraus leitet sich ab, dass immer die Variable gewählt werden soll, welche den kleinsten (im dynamischen Fall: verbleibenden) Wertebereich hat. Für den Fall, dass mehrere Variablen gleich große Domains haben, so soll die Variable gewählt werden, welche am häufigsten in den primitiven Constraints vorkommt.

In folgenden Beispiel soll verdeutlicht werden, wie die Variablenordnung zur Entwurfszeit das simple Backtracking beeinflussen kann.

Suchräume bei unterschiedlicher Variablenordnung

Würde man annehmen, dass in diesem Beispiel die Constraintatome

X1 #> 0 , X2 #> X1

gelten, so wird ersichtlich, dass sich aufgrund einer überlegten Variablenordnung, welche sich an die oben aufgestellte Regel hält, eine Reduzierung der notwendigen Backtrackingschritte bis zur erfolgreichen Lösung erreichen lässt.

Die dynamische Variablenordnung soll an dieser Stelle am Beispiel einer eigenen labelling-Regel "labelingff(Liste)" dargestellt werden, die die Variablenauswahl berücksichtigt. Dies geschieht durch die Regel "deleteff(Vs, V, Rest)", welche über den Parameter V die Variable mit der kleinsten Domain zurückgibt.

labelingff([]). labelingff(Vs) :-     deleteff(Vs, V, Rest),     indomain(V),     labelingff(Rest). deleteff([V0|Vs], V, Rest) :-     get_domain_size(V0, S0),     min_size(Vs, S0, V0, V, Rest). min_size([], _, V, V, []). min_size([V1|Vs], S0, V0, V, [V0|Rest]) :-     get_domain_size(V1, S1),     S1 #< S0     min_size(Vs, S1, V1, V, Rest). min_size([V1|Vs], S0, V0, V, [V1|Rest]) :-     get_domain_size(V1, S1),     S1 #>= S0     min_size(Vs, S0, V0, V, Rest).

Die Auswahl kann nach verschiedensten Algorithmen erfolgen, welche sehr problemspezifisch gewählt werden sollten. So kann es in einem Fall von Vorteil sein, die Domain aus der Mitte heraus nach außen hin abzuarbeiten. In anderen Fällen erscheint es aber auch vernünftig, die Kosten der Wertwahl durch den Prozentsatz der vergefallenen Werte in den zukünftigen Domains zu berechnen und den Wert mit den geringsten Kosten zu nehmen. Daher kann an dieser Stelle keine allgemein gültige Regel dem interessierten Leser vorgestellt werden.