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:

Die Anzahl der Kanten kann man wie folgt berechnet werden:

Fü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> &gt; (trace rucksack1) &gt; (rucksack1 '(30 50 10) '()) </eval>

Breitensuche

Diese Form der Suche erstreckt sich über gesamte Breite, daher werden erst alle Knoten mit Wurzelabstand k, mit k=1 und dann alle mit k+1, dann mit k+2, usw... entdeckt. Alle Knoten müssen vom Startknoten aus erreichbar sein. Man nennt diese Suche auch Breite-zuerst Suche ( englisch: „breadth-first search“ ).

Die Darstellung in Bäumen dient zur Veranschaulichung des Suchprozesses. Außerdem sind die Berechnungen der Aufwände sowie allgemeinen Berechnungen bei Bäumen bekannt.

Alle hier beschrieben Graphen sind ungewichtete Graphen, bedeutet sie sind nicht gewichtet bzw. haben das Gewicht Eins.

Ein Graph heißt Baum, falls er zusammenhängend ist und keinen Kreis enthält. Aus diesem Grund können diese Begriffe in diesem Zusammenhang synonym verwendet werden.