Systematische Suche WS13-14

Aus ProgrammingWiki
< AuK
Archivierte Version vom 2013-10-08T12:46:53+00:00. Aktuelle Version

Inhaltsverzeichnis

Autoren
Hannes Kretschmer
Julian Hilsberg

Rucksackprobleme

Aus einer Menge von Gegenständen die einen Wert w und ein Gewicht g besitzen, gilt es einen Rucksack zu füllen bei dem der Gesamtwert der eingepackten Gegenstände maximal ist, ohne die Kapizitätsgrenze K des Rucksacks zu überschreiten.

$\[ \sum_{i=1}^{n} x_i w_i \rightarrow max $ , wobei $\[ \sum_{i=1}^{n} x_i g_i \le K $, mit $ x_i \in \{0,1\} $

Allgemein beschreiben Rucksackprobleme: Beladungsprobleme, Verschnittprobleme oder Probleme der Budgetkontrolle.

Beispiel

Thomas will sein Geld anlegen und versucht ein Investment-Portfolio zu erstellen, aus dem er sich maximalen Gewinn erhofft. Er hat 10000€ (K) zur Verfügung und will diese in unterschiedliche Aktien verteilen, welche eine Bewertung (w) und einen festen zu investierenden Wert (g) besitzen. Nun geht es darum ein Portfolio zusammenzustellen (Rucksack), in welchem die Gesamtbewertung aller gekauften Aktien maximal ist, dabei darf sein Budget nicht überzogen werden.

Zur Verfügung stehende Aktien:

Aktie Wert (in €) Bewertung (0-10, höher ist besser)
Mapple 2500 8
Minisoft 3000 4
Le-Nogo 5000 5
Wogitech 6000 3
Joogle 4000 7


Varianten

Es gibt viele unterschiedliche Formen des Rucksackproblems:

  1. 0/1 Rucksackproblem: Hier wird ein Gegenstand entweder vollständig (1) oder gar nicht (0) eingepackt. Außerdem darf der selbe Gegenstand nur einmal eingepackt werden.
  2. Bruchteil-Rucksackproblem: Man kann einen beliebigen Teil t, mit 0\% \le t \le 100\%, eines Gegenstandes einpacken.
  3. Unbeschränktes Rucksackproblem: Bei dieser Variante des Problems gibt es keine Kapazitätsobergrenze, d.h. K = \infty.
  4. Teilmengen-Summen-Problem (subset-sum problem): In diesem speziellen Fall geht es darum die Gewichtskapazität des Rucksacks optimal auszunutzen, da der Wert mit dem Gewicht übereinstimmt, d.h. g_i = w_i für alle i.

In diesem Artikel wird ausschließlich das 0/1 Rucksackproblem betrachtet. Bruchteil-Rucksackprobleme werden im Artikel der Greedy-Algorithmen behandelt.

Tiefensuche

Das Tiefe-zuerst-Suchverfahren (engl. depth first search) oder kurz: die Tiefensuche stellt ein Lösungsverfahren für das oben benannte Rucksackproblem dar.
Voraussetzung:

w_i := g_i,

Liste mit Gegenständen im Rucksack (zunächst leer),

Liste der Gegenstände, die in den Rucksack übergehen können

Breitensuche

Beschränkung des Suchbaumes

Nichtdeterminismus