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: 50%" border="1" >
	<tr>
		<td>'''Aktie'''</td>
		<td>Wert</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>
</table>

==Varianten==

Text

=Tiefensuche=

=Breitensuche=

=Beschränkung des Suchbaumes=

=Nichtdeterminismus=