Systematische Suche SS11

Aus ProgrammingWiki
< AuK
Archivierte Version vom 2011-05-01T15:23:44+00:00. Aktuelle Version

Inhaltsverzeichnis

Autoren
Ronny Lüttke
Paul Weinhold

Rucksackprobleme

Bei den Rucksackproblemen handelt es sich um Optimierungsprobleme. Betrachtet werden dabei nicht-leere Mengen von n Objekten.
Jedes Objekt besitzt dabei zwei Kernattribute:

  • einen Wert w
  • ein Gewicht g

Als Begrenzung dient ein fest definierter Wert, die Kapazitätsbeschränkung K.

Gesucht ist die Menge derjenigen Objekte, die in der Summe einen maximalen Wert bei bestmöglicher Ausnutzung der Kapazität haben.

Beispiel

[[Bild:Syssuche_1.png|thumb|right|400px|Mögliche Kombinationen (Original)]]

Ein LKW einer Spedition ist bis 50t belastbar. Es müssen einige Container transportiert werden:

  • Container 1: Gewicht 10, Wert 60
  • Container 2: Gewicht 20, Wert 100
  • Container 3: Gewicht 30, Wert 120

Die Objektmenge besteht nun aus den folgenden Wertpaaren:

M = \left \{ \left ( 10, 60 \right ), \left ( 20,100 \right ), \left ( 30,120 \right )\right \}

Die Kapazitätsbeschränkung K ist hier 50

K = 50


Unterarten

0/1-Rucksackproblem (0-1 knapsack problem)
Ein Objekt darf nur komplett oder gar nicht in die Ergebnismenge übernommen
Bruchteil-Rucksack-Problem
Ein beliebiger Teil t (0% ≤ t ≤ 100%) jedes Gegenstands darf übernommen werden

Auf dieser Seite beschränken wir uns auf das 0/1-Rucksackproblem. Bruchteil-Rucksack-Probleme werden bei den Greedy-Algorithmen besprochen.

Ziel

In mathematischer Schreibweise sieht die oben genannte Zielstellung folgendermaßen aus:

\sum_{i=1}^{n} x_{i}w_{i} \rightarrow max

Wobei folgendes gelten muss:

\sum_{i=1}^{n} x_{i}g_{i} \leq K, mit x_{i} \in {0, 1}


Teilmengen-Summen-Problem (subset-sum-problem)

Hierbei handelt sich um einen Spezialfall des 0/1-Rucksackproblems. Das spezielle ist hier, dass nur eine Menge natürlicher Zahlen gegeben ist:

M = \left \{ a_{i} \: | \: 1 \leq i \leq n \: \wedge a_{i},n \in \mathbb{N} \right \}

Gewicht und Wert sind dabei gleich:

g_{i} = w_{i}, mit g_{i}, w_{i} \in \mathbb{N}

Gesucht ist eine Teilmenge dieser Menge deren Summe diesem Grenzwert möglichst nahe kommt, ihn dabei erreichen, aber nicht erreichen darf.

Praktisch kann dieser Fall benutzt werden um die maximale Beladung eines LKW zu bekommen, wenn die Güter in Kisten gleicher Abmessung verpackt sind. Das Fahrzeug darf nicht überlastet werden, aber die Kapazität sollte auch möglichst gut ausgenutzt werden.

Intuitives Verfahren

Versucht man den Rucksack intuitiv zu befüllen, würde man wohl zuerst zufällig Gegenstände einpacken. Anschließend tauscht man je zwei Gegenstände aus. Man nimmt einen Gegenstand aus dem Rucksack wieder heraus und legt statt dessen einen höherwertigen zurück. Dabei beachtet man aber, dass die maximale Kapazität nicht überschritten wird. Die Frage ob man auch den maximalen Wert erreicht hat, kann aber nicht wirklich beantwortet werden, da diese Herangehensweise keinerlei System besitzt.

ein anderer Versuch

Man könnte auch annehmen, dass mit einer „gierigen“ Herangehensweise ein optimales Ergebnis erreicht werden kann. Dabei geht immer der noch verbleibende Container mit dem höchsten Wert pro Gewicht in die Ergebnismenge ein, solange die obere Grenze K nicht erreicht wird.

q_{c1} = \frac{60}{10} = 6 q_{c2} = \frac{100}{20} = 5 q_{c3} = \frac{120}{30} = 4

Unter dieser Annahme müsste Container 1 ein Teil der Ergebnismenge sein, da er den größten Quotienten aus Wert und Gewicht besitzt. Die optimale Ergebnismenge enthält Container 2 und 3. Alle Ergebnisse mit Container 1 führen zu einen nicht optimalen Ergebnis, obwohl Container 1 das bessere Verhältnis aus Wert und Gewicht aufweist. Abbildung 1 zeigt deutlich, dass diese Strategie bei 0/1-Rucksackproblemen zu keinem optimalen Ergebnis führt.

Die beiden nachfolgenden Suchstrategien führen stets zu einem optimalen Ergebnis. Es werden jeweils sämtliche Packmöglichkeiten erzeugt und anschließend bewertet. Die maximale Kapazität bleibt dabei vorerst außen vor.

Allerdings können diese Verfahren für große n zu unbeherrschbarem Aufwand führen. Aus diesem Grund werden auch Wege aufgezeigt, den Suchraum noch einzuschränken.


Tiefensuche

Bei der Tiefensuche wird ein Suchbaum aufgebaut. Bäume sind in diesem Fall Gebilde aus der Graphentheorie, welche aus Knoten, Kanten und Blättern bestehen. Ein solcher Baum wird durchlaufen, wobei zunächst zum nächtmöglichen Folgeknoten weitergegangen wird.

Aufbau des Algorithmus

  1. Bestimmung des Startknotens
  2. Ersten Knoten expandieren und alle Folgeknoten speichern
  3. Tiefensuche rekursiv auf jeden gespeicherten Folgeknoten anwenden
  4. Abbruch:
    • bei Fund eines passenden Elements
    • wenn kein Knoten mehr im Speicher ist

Erläuterung

[[Bild:Tiefsuch.png|thumb|right|400px|Suchbaum für eine Tiefensuche mit 3 Objekten (Original)]]

Beim Rucksackproblem entsteht ein Binärbaum, dessen Schichten den einzelnen Objekten zugeordnet werden können. Die Knoten stehen hier für Kombinationen aus Objekten, die Kanten repräsentieren die Entscheidung, ob ein Objekt aufgenommen werden soll (grün) oder nicht (rot). Aufgebaut wird dieser von links her, weshalb man auch von einem dynamischen Baum spricht

Die Suche geht soweit in die Tiefe, bis ein passender Knoten gefunden wird, oder keine Folgeknoten mehr zur Verfügung stehen. In letzterem Fall wird eine Ebene zurück gesprungen und mit dem nächsten Folgeknoten fortgesetzt. Dieses zurückspringen bezeichnet man als Backtracking In der untersten Schicht findet man nun alle möglichen Kombinationen der Objekte wieder, insgesamt also 2^{n} mögliche Kombinationen.

Herleitung
\sum_{k=0}^{n}\binom{n}{k}z^k = \binom{n}{0} z^0 + \binom{n}{1} z^1 + \cdots + \binom{n}{n} z^n = (1 + z)^n \xrightarrow{z=1} 2^n


Vorgehensweisen

Angewandt auf statische binärbäume erhält man, je nachdem, wann der Inhalt notiert wird 3 verschiedene Vorgehensweisen:

  • prewalk: Notation beim ersten Durchgang
  • centralwalk: Notation beim zweiten Durchgang
  • postwalk: Notation beim dritten Durchgang

Handelt es sich um einen Rechenbaum mit 2-stelligen Operationen, so entsprechen die jeweiligen Ergebnisse der Präfix-, Infix- bzw. Postfix-Notation.

Eigenschaften

Laufzeit

Im schlimmsten Fall müssen alle möglichen Pfade zu allen möglichen Knoten in Betracht gezogen werden. Geht man also davon aus, dass das Überprüfen eines Knotens konstant erfolgt so gilt allgemein \mathcal{O}(\vert V \vert + \vert E \vert), wobei \vert V \vert für die Summe aller Knoten und \vert E \vert für die Summe aller Kanten steht.

Betrachtet man den Binärbaum, der beim Rucksackproblem entsteht ergibt sich die folgende Laufzeitberechnung:

\vert V \vert + \vert E \vert
\Rightarrow ( 2^{0} + 2^{1} + 2^{2} + \cdots + 2^{n} ) + ( 2^{1} + 2^{2} + 2^{3} + \cdots + 2^{n} ) \Rightarrow \sum_{i=0}^{n} 2^{i} + \sum_{i=1}^{n} 2^{i} \Rightarrow 2^{0} + 2 \sum_{i=1}^{n} 2^{i} \Rightarrow 1 + \sum_{i=1}^{n} 2^{i+1} \Rightarrow 2 \left ( 2^{n+1} -2 \right ) \Rightarrow 2^{n+2}-3 \Rightarrow 4 \cdot 2^{n} - 3 \Rightarrow \mathcal{O}(2^{n})

Man erhält also im worst-case eine exponentielle Laufzeit. Für viele Objekte kann eine solche Suche einige Zeit in Anspruch nehmen oder sogar unvertretbar werden.

Vollständigkeit

[[Bild:Tiefcycle.png|thumb|right|Beispiel für eine fehlschlagende Tiefensuche (Original)]]

Allgemein hat die Tiefensuche keinen Anspruch auf Vollständigkeit, da es sich bei dem gegebenen Graphen nicht zwangsläufig um einen Baumhandeln muss. Da immer zunächst einmal in die nächste Unterebene gegangen wird, kann es passieren, dass sich der Algorithmus einen Endloszyklus erzeugt, wenn keine Zyklenerkennung eingebaut ist.

Da beim Rucksackproblem aber ein Binärbaum mit fester Tiefe und ohne Zyklen entsteht, kann dieser Fall nicht eintreten.

Optimalität

Dadurch, das die Tiefensuche zunächst die Folgeknoten betrachtet, kann es im allgemeinen Fall passieren, dass ein längerer Pfad gefunden wird, als optimal gewesen wäre. Dieser wird aber im Allgemeinen dafür schneller gefunden.

Bezogen auf das Rucksackproblem ist dies Nebensächlich, da ohnehin alle Möglichkeiten in betracht gezogen werden sollten.


Beispiel der Tiefensuche in Scheme

rucksack1 Quelltext


Breitensuche
Die Breitensuche durchläuft einen Baum im Gegensatz zur Tiefensuche, nach dem dem Prinzip "Breite zuerst". Dabei wird der Baum schichtweise aufgebaut.

Angewandt auf das Rucksackproblem stellt jede Schicht alle möglichen Kombinationen von n Elementen im Rucksack dar. Jeder Knoten besitzt für n Nicht-Rucksackgegenstände n Teilbäume.
Ablauf des Algorithmus
  1. Bestimmung des Startknotens
  2. Alle vom Startkonten ereichbaren Knoten durchlaufen und in eine Schlange stellen (Breite zuerst)
  3. Ersten Knoten aus der Schlange entnehmen und damit Schritt 1 wiederholen
Aufbau eines Breitensuchbaums
Die Abbildung 3 zeigt den Aufbau eines Breitensuchbaums angewandt auf das Rucksackproblem. Grün dargestellt ist die Menge aller Gegenstände im Rucksack und rot die Nicht-Rucksackgegenstände während eines Knotens
Breitsuch_all.png
'''Abbildung 3:''' Aufbau eines Breitensuchbaums
Anzahl der Knoten
Die Anzahl der Knoten ist wie folgt definiert:
1+n+n(n-1)+n(n-1)(n-2)+...+n(n-1)(n-2)(n-3)...(n-(n-1))
= \frac{n!}{0!}+\frac{n!}{1!}+\frac{n!}{2!}+...+\frac{n!}{n!}


= \sum_{k=0}^n \frac{n!}{k!}


weitere Bilder
Breitsuch_red.png
Redundanzen

Breitsuch_uni.png
Breitenbaum ohne Redundanzen


Beschränkung des Suchbaumes
Nichtdeterminismus

Quellen
Literatur
Christian Wagenknecht
Algorithmen und Komplexität.- Fachbuchverlag Leipzig, 2003. - ISBN 3-446-22314-2
Thomas H. Cormen, Charles E. Leiserson, Ronald Rivest, Clifford Stein
Algorithmen - Eine Einführung, Oldenbourg Verlag München Wien, 2. Auflage, 2007. - ISBN 978-3-486-58262-8
Jochen Ziegenbalg
Algorithmen - Von Hammurapi bis Gödel, Spektrum Akademischer Verlag Heidelberg Berlin Oxford, 1996. - ISBN 3-8274-0114-3
Markus von Rimscha
Algorithmen kompakt und verständlich, Vieweg + Teubner Verlag Wiesbaden, 2008. - ISBN 978-3-8348-0569-0
Websites