Systematische Suche WS13-14

Aus ProgrammingWiki
< AuK
Archivierte Version vom 2013-10-08T10:58:50+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\} $

Beispiel

Text

Varianten

Text

Tiefensuche

Breitensuche

Beschränkung des Suchbaumes

Nichtdeterminismus