Die Frage war: Warum probieren wir die nicht einfach alle durch? Wozu haben wir denn Computer? Die Zahl der Möglichkeiten für das o.a. Beispiel ist sehr leicht zu berechnen: Sie ist 2Anzahl der Stücke = 213 = 8192.
Probieren wir also einmal alle Möglichkeiten durch! Die zugehörigen Suchverfahren bezeichnet man als "brute force" - Verfahren, weil sie die Lösung sozusagen mit brutaler Gewalt suchen. Ein solches Verfahren ist die Tiefensuche.
Bleiben wir beim Rucksackproblem mit der Frage "hinein" oder "nicht hinein", dann kann man als einen möglichen Expansionsgraphen einen binären Baum verwenden, bei dem jede Stufe zu einem der beteiligten Gewichtsstücke gehört und die Äste die beiden o.a. möglichen Fälle beschreiben. Die Entwicklung einer vollständigen Lösung ist mit seiner Hilfe leicht zu verstehen.
Man beginnt mit dem ersten Gewicht aus der Liste der gegebenen Gewichte -das verwendet werden kann oder auch nicht- und kann nun diese beiden Möglichkeiten weiter zu verfolgen. Wir untersuchen das an der Liste '(5 5 5 3 3 2 1) und dem zu erzielenden Gesamtgewicht von 17.
Zunächst haben wir zwei Möglichkeiten, die wir im Diagramm mit - und 5 kennzeichnen. Für die zweite 5 entstehen nun schon 4 Möglichkeiten usw.
Darstellung der Verzweigung | |||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
- | 5 | ||||||||||||||
-- | 5- | -5 | 55 | ||||||||||||
--- | --5 | 5-- | 5-5 | -5- | -55 | 55- | 555 | ||||||||
---- | ---3 | --5- | --53 | 5--- | 5--3 | 5-5- | 5-53 | -5-- | -5-3 | -55- | -553 | 55-- | 55-3 | 555- | 5553 |
Der rot markierte letzte Wert gehört zu einer Kombination, mit der wir die einschränkende Bedingung nicht mehr erfüllen können. Bei einer sturen vollständigen Suche würde man hier trotzdem weiter machen. Hier gibt es natürliche erste Ansätze zur Optimierung des Verfahrens selbst.
Aufgabe zur Verbesserung der Tiefensuche
Beschreiben Sie, was sich bei der Lösung verbessern lässt!