AuK/Systematische Suche WS13-14

Wiki-Quelltext dieser Seite.

;Autoren
:[mailto://s3hakret@stud.hszg.de Hannes Kretschmer]<br/>
:[mailto://s3juhils@stud.hszg.de 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. 

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

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.<br>

Zur Verfügung stehende Aktien:<br>

<table style="width: 40%" border="1" >
<tr>
<td>'''Aktie'''</td>
<td>'''Wert (in €)'''</td>
<td>'''Bewertung (0-10, höher ist besser)'''</td>
</tr>
<tr>
<td>Mapple</td>
<td>2500</td>
<td>8</td>
</tr>
<tr>
<td>Minisoft</td>
<td>3000</td>
<td>4</td>
</tr>
<tr>
<td>Le-Nogo</td>
<td>5000</td>
<td>5</td>
</tr>
<tr>
<td>Wogitech</td>
<td>6000</td>
<td>3</td>
</tr>
<tr>
<td>Joogle</td>
<td>4000</td>
<td>7</td>
</tr>
</table>
<br>

==Varianten==

Es gibt viele unterschiedliche Formen des Rucksackproblems:

<ol>
<li>'''0/1 Rucksackproblem:'''<br> Hier wird ein Gegenstand entweder vollständig (1) oder gar nicht (0) eingepackt. Außerdem darf der selbe Gegenstand nur einmal eingepackt werden.</li>
<li>'''Bruchteil-Rucksackproblem:''' <br> Man kann einen beliebigen Teil $t$, mit $0\% \le t \le 100\%$, eines Gegenstandes einpacken.</li>
<li>'''Unbeschränktes Rucksackproblem:''' <br> Bei dieser Variante des Problems gibt es keine Kapazitätsobergrenze, d.h. $K = \infty$.</li>
<li>'''Teilmengen-Summen-Problem (subset-sum problem):''' <br> 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$.</li>
</ol>

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

=Lösungsverfahren=

==Intuitives Verfahren==

==Tiefensuche==

Das Tiefe-zuerst-Suchverfahren (engl. depth first search) oder kurz: die Tiefensuche stellt ein Lösungsverfahren für das oben benannte Rucksackproblem dar.<br>
Voraussetzung:<br>
<p style="text-indent:30px;">$w_i := g_i$,</p>
<p style="text-indent:30px;">Liste mit Gegenständen im Rucksack (zunächst leer),</p>
<p style="text-indent:30px;">Liste der Gegenstände, die in den Rucksack übergehen können</p><br>
Vorgehensweise:<br>
<p style="text-indent:30px;">mit jedem Schritt wird entschieden, ob ein Gegenstand in den Rucksack gelegt werden soll, oder nicht</p>

==Breitensuche==

=Beschränkung des Suchbaumes=

=Nichtdeterminismus=