AuK/Systematische Suche SS11

Wiki-Quelltext dieser Seite.

= Rucksackprobleme =

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

* einen Wert
* ein Gewicht

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.



== Ziel ==

= Versuch einer Lösung =

= Tiefensuche =

= Breitensuche =

= Beschränkung des Suchbaumes =

= Nichtdeterminismus =