AuK/Systematische Suche WS13-14
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
;Autoren
:[mailto://s3hakret@stud.hszg.de Hannes Kretschmer]<br/>
:[mailto://s3juhils@stud.hszg.de Julian Hilsberg]
<language>Scheme</language>
<language>Scheme</language>
=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:'''<br> 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:''' <br> Man kann einen beliebigen Teil $t$, mit $0\% \le t \le 100\%$, eines Gegenstandes einpacken.</li>
<li>'''Unbeschränktes Rucksackproblem:''' <br> Bei dieser Variante des Problems gibt es keine Kapazitätsobergrenze, d.h. $K = \infty$.</li>
<li>'''Teilmengen-Summen-Problem (subset-sum problem):''' <br> In diesem speziellen Fall geht es darum die Gewichtskapazität des Rucksacks optimal auszunutzen, da der Wert mit dem Gewicht übereinstimmt, d.h. $g_i = w_i$ für alle $i$.</li>
</ol>
In diesem Artikel wird ausschließlich das 0/1 Rucksackproblem betrachtet. Bruchteil-Rucksackprobleme werden im Artikel der Greedy-Algorithmen behandelt.
=Beschränkung des Suchbaumes=
<language>Scheme</language>
<language>Scheme</language>
==Tiefensuche mit Beschränkung==
Bei der beschränkten Tiefensuche wird nun auch die Kapazitätsbeschränkung ($K$) beim "Packen des Rucksacks" mit einbezogen. Im folgenden Beispiel ist eine Prozedur zur Erstellung eines Berechnungsprotokolles zur Lösung des Problems unter Berücksichtigung von $K$ in Scheme dargestellt:
<code id="526e23e042f72">
;;; Tiefensuche mit Beschraenkung
(define rucksack2
(lambda (g-ls s-ls)
(if (null? g-ls)
s-ls
(begin
(if (hoechstens-maxgewicht? s-ls 42)
(rucksack2 (cdr g-ls) (cons (car g-ls) s-ls)))
(if (hoechstens-maxgewicht? s-ls 42)
(rucksack2 (cdr g-ls) s-ls))))))
(define hoechstens-maxgewicht?
(lambda (ls k)
(<= (apply + ls) k)))
</code>
<run>(trace 'rucksack2)
(rucksack2 '(30 50 10) '())</run>
[[Bild:Tiefensuche_2.png|200px|thumb|right|Reduzierter Baum mit (30 50 10) für $K = 42$]]
Am reduzierten Suchbaum zu erkennen ist, das lediglich die Blätter (10,30), (30), (10) und () die gewählte Kapazitätsbeschränkung erfüllen. Gesucht ist allerdings der größtmögliche Wert: Es wird bei $w_i = g_i$
<center><math> $\sum g_{i} \is s-ls g_i</math></center> gefordert
=Nichtdeterminismus=
Beim Rucksackproblem wird der Suchprozess bei der Tiefensuche als Baum dargestellt. Dieser Baum existiert aber nicht wirklich, d.h. er wird nicht als Datenstruktur repräsentiert.
Der Programmierer denkt in Bäumen, wenn er versucht das Verfahren in seiner Programmiersprache implementiert. Bietet die gewählte Programmiersprache das Mittel Rekursion, kann das die Arbeit weiter vereinfachen. Denn so kann die rekursive Baumstruktur direkt in eine rekursive Programmstruktur abgebildet werden. Trotzdem muss der Programmierer noch viel geistige Energie in die Organisation des Suchprozesses stecken, um einen erfolgreichen Algorithmus zu schreiben. <br> Es wäre von Vorteil nur das potentielle Resultat zu beschreiben und sich nicht um den Prozess zur Findung dieses Ergebnisses kümmern zu müssen. So kommen wir zur deskriptiven Programmierung. <br>
Um das zu realisieren eignen sich nichtdeterministische Algorithmen besonders gut.
Ein nichtdeterministischer Algorithmus "erahnt" den richtigen Pfad von der Wurzel bis zum Resultat-Blatt, falls eins existiert.
Nichtdeterminismus beschreibt eine übernatürliche Fähigkeit, das Richtige vorherzusehen. <br>
Nun könnte man denken, durch den Einsatz des Nichtdeterminismus kann man auch die Effizienz des Algorithmus steigern, dass gelingt aber nur in den seltensten Fällen. Der Nichtdeterminismus wird durch deterministische Sprachmittel simuliert, im Hintergrund findet eine Tiefensuche statt, die bei vollständigem Durchlauf einen exponentiellen Aufwand erfordert.
Der große Vorteil vom Einsatz des Nichtdeterminismus ist die Verbesserung der kognitiven Effizienz, die hilft komplexere Probleme zu lösen.
==Nichtdeterminismus in Scheme==
Um den Nichtdeterminismus in Scheme zu nutzen benötigt man einige Befehle, die man zusätzlich implementieren muss.
'''choice:''' Nimmt eine Liste und gibt "das richtige Element" daraus zurück. Wenn der Befehl eingebettet ist, wird der Wert zurück gegeben, der zum "Erfolg des Gesamtausdrucks" führt.
<run>(= (choice '(3 6 9)) 7)</run>
'''bag-of:''' Nimmt eine Liste und gibt eine Liste der Elemente zurück, die zum Erfolg führen.
<run>(bag-of (< (choice '(3 6 9 12 15)) 10))</run>
'''multichoice:''' Nimmt eine Liste $ls$ und eine natürliche Zahl $n$ und gibt die $n$ "richtigen" Elemente aus $ls$ zurück.
<run>(multichoice '(1 2 3 4 5 6 7 8) 4)</run>
'''randomchoice:''' Nimmt eine natürliche Zahl $n$ und berechnet das richtige Element aus der Liste (1 2 3 ... $n$).
'''initialize-amb-fail:''' Diese nullstellige Prozedur (thunk), dient zur Initialisierung des Ambigious-Systems.
==Nichtdeterministische Summandensuche==
Das folgende Programm sucht nach Summanden für eine angegebene ganze Zahl.
<code id="526a659a98442">
(define summanden
(lambda ()
(list (choice '(1 2 3 4 5 6))(choice '(1 2 3 4 5 6)))))
(define sumsuche
(lambda (summe)
(let ((kandi (summanden)))
(if (= (apply + kandi) summe)
kandi (choice '())))))
</code>
<run id="526a659a984dd">
(initialize-amb-fail)
(bag-of (sumsuche 5))
</run>
==Anwendung auf das Rucksackproblem==
Nun nutzen wir die nichtdeterministischen Sprachmittel um unser Rucksackproblem zu lösen.
<code>
(define rucksack4
(lambda (gls k)
(let ((sls (multichoice gls (randomchoice (length gls)))))
(if (<= (apply + sls) k)
sls
(choice '())))))
</code>
<run>(initialize-amb-fail)
(rucksack4 '(30 50 10) 45)</run>
Jetzt wird in diese Prozedur noch die Forderung nach der maximalen Gewichtssumme der eingepackten Gegenstände eingebaut.
<code>
(define rucksack5
(lambda (gls k)
(let ((max 0) (resultat '()))
(let ((alle-sls (bag-of (rucksack4 gls k))))
(map
(lambda (sls)
(let ((slssumme (apply + sls)))
(if (> slssumme max)
(begin
(set! max slssumme)
(set! resultat sls)))))
alle-sls))
(cons resultat max))))
</code>
<run>(initialize-amb-fail)
(rucksack5 '(56 21 91 34 8 43) 172)</run>