vorige nächste

Finden wir so alle Lösungen ?


Leider ist das nicht der Fall. Betrachten wir dazu den Fall, bei dem wir als Stückeliste die Liste
'(30 30 30 20 20 20 15 15 5 3 2 1 1) haben und unser Rucksack 103 fasst. Das geht natürlich zu lösen, indem man '(30 30 20 20 2 1) verwendet. Nur, dass diese Lösung nicht gefunden wird, da bei unserem bisherigen Verfahren zunächst die dritte 30 in den Rucksack gepackt wird und danach passen die anderen Stücke nicht mehr.

Unser Verfahren lässt es aber nicht zu, dass ein Stück wieder aus dem Rucksack entnommen wird, also eine Entscheidung rückgängig gemacht wird. Es wäre aber notwendig, die Entscheidung für das dritte 30-er-Gewicht rückgängig zu machen, um statt dessen mit den beiden 20-er-Gewichten zur zulässigen Lösung zu kommen.

Sinnvollerweise versucht man an dieser Stelle das Problem zu verallgemeinern. Ob man dazu auf einen neuen Anwendungsfall wechselt - wie zum Beispiel Labyrinthe, das Problem der acht Damen oder andere - ist nicht entscheidend. Wichtig ist allerdings, dass die Schülerinnen und Schüler im Verlauf des Kurses erkennen, dass ein Graph mit Knoten und Kanten ein angemessenes Modell für die Beschreibung des Problems ist.

Bleiben wir beim Rucksackproblem, 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 möglichen Fälle "das Gewichtsstück kommt in den Rucksack" und "das Gewichtsstück kommt nicht in den Rucksack" beschreiben.

Warum probieren wir die Möglichkeiten nicht einfach alle durch? Wozu haben wir denn Computer?


Aufgabe "alles durchprobieren"

  1. Zeichnen Sie zu einem nicht zu umfangreichen Beispiel den Baum der Möglichkeiten!
  2. Berechnen Sie die Zahl der Möglichkeiten für den Fall ihres Diagramms - Sie können natürlich auch einfach abzählen - und berechnen Sie die Zahl der Möglichkeiten für das o.a. Beispiel!
  3. Geben Sie eine allgemeine Formel für die Zahl der Möglichkeiten an!
  4. Überlegen Sie sich eine Strategie zur vollständigen Suche nach Lösungen und beschreiben Sie das Verfahren (schriftlich) !