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: 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: Man kann einen beliebigen Teil $t$, mit $0% \le t \le 100%$, eines Gegenstandes einpacken.</li>
<li>Unbeschränktes Rucksackproblem: </li>
</ol>

=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: <math>$w_i := g_i$<\math>

=Breitensuche=

=Beschränkung des Suchbaumes=

=Nichtdeterminismus=