Systematische Suche SS09
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.
Betrachten wir das Ganze mal mathematisch :
Es gibt verschiedene Gegenstände x_i , mit einem bestimmten Gewicht g_i und einem Wert w_i . Dazu kommt dann die Kapazität des Rucksacks K .
Die Optimierungsaufgabe ist die maximale Wertsumme bei Nichtüberschreitung der Kapazitätsbeschränkung: \sum \limits _{i =1}^n {x_i w_i} \to max , wobei \sum \limits _{i =1}^n {x_i g_i} \leq K , mit x_i \in \{0,1\}
Tiefensuche
Die Tiefe-zuerst-Suche, englisch depth-first search oder kurz Tiefensuche, ist ein Verfahren zum Suchen eines Knotens in einem Graphen. Sie zählt zu den uniformierten Suchalgorithmen.
Wie ist der Graph oder Entscheidungsbaum nun aufgebaut?
Da es sich in diesem Kapitel nur um das 0/1 Rucksackproblem handelt, kommt es in jedem Knoten zu eine Ja/Nein-Entscheidung. Wird der Baum wärend einer Suche generiert, als eine Art Protokol spricht man von einem dynamischen Baum.
Wie sieht so ein Baum nun aus und welche Eigenschaften hat er?
Gehen wir mal davon aus, dass man n Gegenstände hat. Allgemein ergeben sich dann für n Gegenstände 2^n Blätter. Anhand des Baumes kann man das auch mit folgender Formel nachrechnen:
\sum \limits _{k=0}^n {n \choose k}z^k = {n \choose 0}z^0+...+{n \choose n}z^n = (1+z)^n , für z = 1
Die Anzahl der Knoten kann man mit folgender Formel berechnen:
\sum_{k=0}^n 2^k = 2^n^+^1 -1Die Anzahl der Kanten kann man wie folgt berechnet werden:
\vert E \vert = \vert V \vert -1Für die Erzeugung eines gesamten Baumes hat man einen exponentiellen Aufwand von \mathcal{O} (2^n) .
Kommen wir zur Laufzeit der Tiefensuche:
Da im schlimmsten Fall alle möglichen Pfade zu allen möglichen Knoten betrachtet werden müssen, beträgt die Laufzeit von Tiefensuche \mathcal{O}(\vert V \vert + \vert E \vert) ,
Anzahl der Knoten \vert V \vert
Anzahl der Kanten \vert E \vert
rekursive Tiefensuche mit Scheme:
<eval> (rucksack1 '(30 50 10) '()) </eval>
Tiefensuche mit Beschränkung:
Es kann anstatt der 42 auch eine beliebige andere Kapazität gewählt werden.
<eval> (rucksack2 '(30 50 10) '() 42) </eval>