AuK/Systematische Suche SS11
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Scheme</language>
;Autoren
:[mailto://s3roluet@stud.hs-zigr.de Ronny Lüttke]<br/>
:[mailto://s3pawein@stud.hs-zigr.de Paul Weinhold]
<code id="4dbb20be19248" hidden>(import debugging)</code>
= 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 '''''w'''''
* ein Gewicht '''''g'''''
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.
== Beispiel ==
Ein LKW einer Spedition ist bis 50t belastbar. Es müssen einige Container transportiert werden:
* Container 1: Gewicht 10, Wert 60
* Container 2: Gewicht 20, Wert 100
* Container 3: Gewicht 30, Wert 120
Die Objektmenge besteht nun aus den folgenden Wertpaaren:
<math>M = \left \{ \left ( 10, 60 \right ), \left ( 20,100 \right ), \left ( 30,120 \right )\right \}</math>
Die Kapazitätsbeschränkung '''''K''''' ist hier 50
<math>K = 50</math>
<span id="img1">[[Bild:Syssuche_1.png|framed|center|'''Abbildung 1:''' Mögliche Kombinationen]]</span>
== Unterarten ==
;0/1-Rucksackproblem (0-1 knapsack problem)
:Ein Objekt darf nur komplett oder gar nicht in die Ergebnismenge übernommen
;Bruchteil-Rucksack-Problem
:Ein beliebiger Teil '''''t''''' (0% ≤ t ≤ 100%) jedes Gegenstands darf übernommen werden
Auf dieser Seite beschränken wir uns auf das 0/1-Rucksackproblem. Bruchteil-Rucksack-Probleme werden bei den [[AuK/Greedy-Algorithmen SS11|Greedy-Algorithmen]] besprochen.
== Ziel ==
In mathematischer Schreibweise sieht die oben genannte Zielstellung folgendermaßen aus:
<math>\sum_{i=1}^{n} x_{i}w_{i} \rightarrow max</math>
Wobei folgendes gelten muss:
<math>\sum_{i=1}^{n} x_{i}g_{i} \leq K</math>, mit <math>x_{i} \in {0, 1}</math>
== Teilmengen-Summen-Problem (subset-sum-problem) ==
Hierbei handelt sich um einen Spezialfall des 0/1-Rucksackproblems.
Das spezielle ist hier, dass nur eine Menge natürlicher Zahlen gegeben ist:
<math>M = \left \{ a_{i} \: | \: 1 \leq i \leq n \: \wedge a_{i},n \in \mathbb{N} \right \}</math>
Gewicht und Wert sind dabei gleich:
<math>g_{i} = w_{i}</math>, mit <math>g_{i}, w_{i} \in \mathbb{N}</math>
Gesucht ist eine Teilmenge dieser Menge deren Summe diesem Grenzwert möglichst nahe kommt, ihn dabei
erreichen, aber nicht erreichen darf.
Praktisch kann dieser Fall benutzt werden um die maximale Beladung eines LKW zu bekommen,
wenn die Güter in Kisten gleicher Abmessung verpackt sind. Das Fahrzeug darf nicht überlastet werden,
aber die Kapazität sollte auch möglichst gut ausgenutzt werden.
== Intuitives Verfahren ==
Versucht man den Rucksack intuitiv zu befüllen, würde man wohl zuerst zufällig Gegenstände einpacken.
Anschließend tauscht man je zwei Gegenstände aus.
Man nimmt einen Gegenstand aus dem Rucksack wieder heraus und legt statt dessen einen höherwertigen zurück.
Dabei beachtet man aber, dass die maximale Kapazität nicht überschritten wird.
Die Frage ob man auch den maximalen Wert erreicht hat, kann aber nicht wirklich beantwortet werden,
da diese Herangehensweise keinerlei System besitzt.
== ein anderer Versuch ==
Man könnte auch annehmen, dass mit einer „gierigen“ Herangehensweise ein optimales Ergebnis erreicht werden kann. Dabei geht immer der noch verbleibende Container mit dem höchsten Wert pro Gewicht in die Ergebnismenge ein, solange die obere Grenze '''''K''''' nicht erreicht wird.
<math>q_{c1} = \frac{60}{10} = 6</math>
<math>q_{c2} = \frac{100}{20} = 5</math>
<math>q_{c3} = \frac{120}{30} = 4</math>
Unter dieser Annahme müsste Container 1 ein Teil der Ergebnismenge sein, da er den größten Quotienten aus Wert und Gewicht besitzt.
Die optimale Ergebnismenge enthält Container 2 und 3. Alle Ergebnisse mit Container 1 führen zu einen nicht optimalen Ergebnis,
obwohl Container 1 das bessere Verhältnis aus Wert und Gewicht aufweist. [[#img1|Abbildung 1]] zeigt deutlich, dass diese Strategie bei
0/1-Rucksackproblemen zu keinem optimalen Ergebnis führt.
Die beiden nachfolgenden Suchstrategien führen stets zu einem optimalen Ergebnis. Es werden jeweils sämtliche Packmöglichkeiten erzeugt und anschließend bewertet. Die maximale Kapazität bleibt dabei vorerst außen vor.
Allerdings können diese Verfahren für große '''''n''''' zu unbeherrschbarem Aufwand führen. Aus diesem Grund werden auch Wege aufgezeigt,
den Suchraum noch einzuschränken.
= Tiefensuche =
<span id="img2">[[Bild:Tiefsuch.png|framed|center|'''Abbildung 2:''' ???]]</span>
<code id="4dbb1c3e4ff53">
(define rucksack1
(lambda (g-ls s-ls)
(if (null? g-ls)
s-ls
(begin
(rucksack1 (cdr g-ls) (cons (car g-ls) s-ls))
(rucksack1 (cdr g-ls) s-ls)))))</code>
<code id="4dbb20be192df">;(trace 'rucksack1)</code>
<run id="4dbb1c3e4ffb9">(rucksack1 '(10 20 30) '())</run>
= Breitensuche =
<span id="img3">[[Bild:Breitsuch_all.png|framed|center|'''Abbildung 3:''' ???]]</span>
<popup caption="weitere Bilder">
[[Bild:Breitsuch_red.png|framed|center|???]]<br />
[[Bild:Breitsuch_uni.png|framed|center|???]]
</popup>
= Beschränkung des Suchbaumes =
= Nichtdeterminismus =
= Quellen =
== Literatur ==
;Christian Wagenknecht
:Algorithmen und Komplexität.- Fachbuchverlag Leipzig, 2003. - ISBN 3-446-22314-2
;Thomas H. Cormen, Charles E. Leiserson, Ronald Rivest, Clifford Stein
:Algorithmen - Eine Einführung, Oldenbourg Verlag München Wien, 2. Auflage, 2007. - ISBN 978-3-486-58262-8
;Jochen Ziegenbalg
:Algorithmen - Von Hammurapi bis Gödel, Spektrum Akademischer Verlag Heidelberg Berlin Oxford, 1996. - ISBN 3-8274-0114-3
;Markus von Rimscha
:Algorithmen kompakt und verständlich, Vieweg + Teubner Verlag Wiesbaden, 2008. - ISBN 978-3-8348-0569-0
== Websites ==