|
2.1 Allgemeines über Backtracking r />
Backtracking ist ein Suchverfahren, bei dem versucht wird, aus einer Reihe von Möglichkeiten durch einfaches Ausprobieren eine optimale Kombination zu ermitteln.
Wenn ein bestimmter Zweig den Prüfbedingungen nicht mehr entspricht, wird in diesem Zweig nicht mehr weitergesucht, sondern um 1 Knoten zurückgegangen und von dort wird der nächste Zweig getestet.
2.2 Einfaches Beispiel
Ein Verbrecher bricht in ein Haus ein, und findet dort 4 Dinge, die ihm gefallen. Er kann jedoch nur ein Maximalgewicht von 37 kg tragen und nun muß er sich entscheiden welche Dinge er mitnimmt. Mit Hilfe des Backtrackings wird dieses Problem optimal gelöst.
Gegenstand A: Edle Lampe 5 kg Wert: 14
B: Hifi-Anlage 18 kg Wert: 7
C: Fernsehapparat 15 kg Wert: 15
D: Videorecorder 10 kg Wert: 16
Die Zahlen hinter den Buchstaben bedeuten das Gewicht, die Zahlen darunter den Wert. Die durchgestrichenen Kästchen werden bei der Suche ignoriert. Die orangen Pfeile kennzeichnen die Suchreihenfolge. Der Weg mit doppelten Strichen kennzeichnet den optimalen Weg. Der Räuber wird Gegenstand A,C und D mitnehmen.
Algorithmus:
1. Zuerst wird der linke Zweig durchsucht
2. Wenn beim Aufsummieren der Gewichte das Maximalgewicht überschritten wird, wird der Ast nicht weiter verfolgt, sondern 1 Knoten zurückgegangen.
3. Wenn ein Endknoten erreicht wird, wird die Summe der Werte als Höchstwert gespeichert. Auch der Weg von der Wurzel zum Endknoten wird gespeichert.
4. Es wird wieder zurückgegangen und der nächste Zweig wird getestet.
5. Wenn wieder ein Endknoten erreicht ist, wird die Summe der Werte mit dem derzeitigen Höchstwert verglichen. Wenn sie höher ist, wird die neue Summe
der Werte zum Höchstwert.
Nachteil dieses Algorithmusses ist, daß auch Äste oder Wege durchlaufen werden, die nicht zum Ziel führen. Das kann zu enorm hohen Rechenzeiten führen. Der Algorithmus kann verbessert werden, indem pro Knoten der höchste Wert, zu dem er führt mitgespeichert wird. Kommt der Algorithmus jetzt zu einem Knoten, der zu keinem größeren Wert als dem bestehenden Höchstwert führt, wird sofort zurückgegangen (\"backgetrackt\").
2.3 Weitere Beispiele
Wegesuche
Ein weiteres Problem, bei dem Backtracking eingesetzt wird, ist die sogenannte Wegesuche in einem zusammenhängenden Graphen.
Wird auch mittels Rekursionen gelöst.
suche(gefunden,A,B,Weg)
Hinzufügen von A zu Weg
Wenn A=B
gefunden = TRUE
Sonst
Wenn A besucht dann
gefunden = FALSE
Sonst
A besucht = TRUE
Für alle Nachbarn von A (solange nicht gefunden)
suche gefunden,Nachbar, B , Weg
EndFür
A besucht = FALSE
EndWenn
EndWenn
Wenn gefunden = FALSE
Lösche A aus Weg // Backtracking
EndWenn
|
