Systematische Suche SS09

Systematische Suche

Rucksackprobleme

Stellen Sie sich vor, Sie wollen von einem Ort A zu einem Ort B kommen und haben für diesen Weg einen Rucksack dabei, damit Sie verschiedene Gegenstände, welche ein Gewicht und einen Wert haben transportieren wollen. Das Problem ist, dass der Rucksack nur eine Gesamtkapazität hat, die nicht überschritten werden darf. Die Aufgabe besteht nun darin, den Rucksack so zu füllen, dass die Wertsumme der eingepackten Gegenstände, unter Beachtung seiner Kapazitätsschranke, maximal ist.

Man unterscheidet dabei in zwei Formen:

- der Gegenstand wird vollständig eingepackt oder nicht

- der Gegenstand wird teilweise eingepackt

Wir betrachten nur die erste Form, dass der Gegenstand vollständig oder gar nicht eingepackt wird.

Tiefensuche

Breitensuche

Beschränkung des Suchbaumes

Nichtdeterminismus