AuK/Systematische Suche SS10
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
'''Autoren:'''
Daniel Horbach
Richard Hettmann
== Rucksackproblem ==
Das Rucksackproblem ist ein Optimierungsproblem der Kombinatorik. Aus einer Menge von Objekten, die jeweils ein Gewicht und einen Wert haben, soll eine Teilmenge ausgewählt werden, deren Gesamtgewicht eine vorgegebene Gewichtsschranke nicht überschreitet. Unter dieser Bedingung soll der Wert der ausgewählten Objekte maximiert werden.
Zur Veranschaulichung dieses klassischen Problems wird auch gerne der Dieb herangezogen, der nur einen kleinen Teil der Beute im Rucksack abtransportieren kann und nun versucht, den größtmöglichen Wert herauszuschlagen.
===Grundsätzliches===
Gegeben sei eine nichtleere Menge von <math> n </math> Gegenständen, von denen jeder einen Wert <math>w_i</math>
und ein Gewicht <math>g_i</math>. Da unser Rucksack nicht unbegrenzt belastbar ist, brauchen wir noch die Aufnahmekapazität <math>K</math>, welche keinesfalls durch das aktuelle Gesamtgewicht überschritten werden darf.
Unser Ziel ist es nun, den Rucksack so zu füllen, dass die Wertsumme der eingepackten Gegenstände
maximal ist und die Aufnamekapazität nicht überschrittn wird.
Man unterscheidet diese zwei grundsätzlich veschiedenen Arten von Rucksackproblemen:
=== Bruchteilrucksackproblem ===
Ein beliebiger Teil <math> t </math> eines jeden Gegenstandes darf eingepackt werden.
<math> t </math> , <math> 0 \% <= t <= 100 \% </math>
=== 0/1 Rucksackproblem ===
Jeder einzelne Gegenstand wird entweder vollständig (1) oder garnicht (0) in den Rucksack aufgenommen
Wir befassen uns nur mit dem 0/1 Rucksackproblem
=== Ziel ===
Unser Ziel ist das Erreichen der maximalen Wertsumme ohne die Aufnahmekapazität zu überschreiten.
<math> \sum \limits _{i =1}^n {x_i w_i} \to max </math>, wobei <math> \sum \limits _{i =1}^n {x_i g_i} \leq K </math> , mit <math> x_i \in \{0,1\} </math>
=== Teilmengen-Summen-Problem ===
Das Teilmengen-Summen-Problem ist ein Spezialfall des Rucksackproblems. Aus einer Menge natürlicher Zahlen
<math> M </math> wird eine Teilmenge gesucht, deren Elementensumme möglichst nahe an die Kapazitätsgrenze
<math> K </math> herankommt und diese auch erreichen darf. Dieser Spezialfall ergibt sich immer dann, wenn Gewicht und Wert eines jeden Gegenstandes zahlenmäßig überein stimmen.
<math> M = \{ a_i </math> <math>|</math> <math> 1 \leq i \leq n </math> und <math> a_i, n \in N \} </math>
<math> g_i = w_i , </math> mit <math> g_i,w_i \in N </math>
Dieses Problem entsteht beispielsweise in Transporunternehmen, wenn in einem LKW, dessen Ladekapazität natürlich beschränkt ist, unterschiedliche Frachtgüter befördert werden sollen. Um die Transportkapazität optimal nutzen zu können, also das Fahrzeug nicht zu überlasten oder Transportkapazität zu vergeuden, ist eine sorgfältige Auswahl der Transportgüter nötig.
=== Intuitives Verfahren ===
Welche Möglichkeiten haben wir um das Rucksackproblem zu lösen? Natürlich könnte man den Rucksack mit zufällig ausgewählten Gegenständen füllen und danach den einen oder anderen Gegenstand austauschen bis man der Meinung ist das man das globale Wertmaximum erreicht hat. Da diese Verfahren aber weder systenmatisch noch zielführend ist, kann man sich dessen niemals sicher sein.
Der bessere Weg ist die Benutzung von Suchstrategien, die dafür sorgen das sämtliche Packmöglichkeitn des Rucksacks erzeugt und anschließend bewertet werden. Mit zwei dieser Strategien werden wir uns näher beschäftigen, der Tiefensuche und der Breitensuche.
=== Grundlegende Graphentheorie ===
Bevor wir uns der Tiefensuche und Breitensuche zuwenden, möchten wir die Grundbegriffe und die von uns verwendete allgemeine Darstellung erläutern. Ein Graph besteht aus mehreren Knoten, welch durch Kanten miteinander verbunden sind. Je nach Art und Weise der Verbindung dieser Knoten entstehen unterschiedlich Varianten von Graphen.
Um alle Knoten eines Graphen effizient betrachten zu können, werden gerne Bäume aus dem Graphen konstruiert.
Die Wurzel dieses Baumes ist der Startknoten, von dem eine oder mehrere Kanten zu weiteren Knoten abgehen, von denen wiederum Kanten zu weiteren Knoten abgehen können.
Ein spezieller und oft verwendeter Baum ist der Binärbaum. Hierbei kann jeder Knoten maximal zwei Kanten haben, welche mit 0 und 1 dargestellt werden können.
Wir stellen die Knoten wie folgt dar:
Knoten = Rucksackliste und Gegenstandsliste
Die elemente dieser Listen bezeichnen die Gegenstände. Eine leere Rucksackliste und eine Gegenstandsliste mit 3 Gegenständen Würde so aussehen:
<math>()|({g}_{1}, {g}_{2}, {g}_{3})</math>
Die Kanten repräsentieren einen alternativen Weg, wo win Gegenstand der Gegenstandsliste entnommen und der Rucksackliste hinzugefügt wird.
=== Graphendurchlauf ===
Ausgehend vom Startknoten wird beim Graphendurchlauf jeder Knoten in einer bestimmten Reihenfolge berührt.
Die erste Berührung eines Knoten nennt man Prewalk. Wenn dieser Knoten ein zweites Mal besucht wird heißt es Centralwalk und beim dritten Mal Postwalk.
== Tiefensuche ==
[[Bild:Rucksack1graph2.jpg]]
[[Bild:Exponentielleraufwand2.jpg]]
<code>
(define rucksack1
(lambda (g-ls s-ls)
(display 'rucksack1)
(display g-ls)(display s-ls)(newline)
(if (null? g-ls)
(begin
(display s-ls) (newline))
(begin
(rucksack1 (cdr g-ls) (cons (car g-ls) s-ls))
(display '-); Tiefe
(rucksack1 (cdr g-ls) s-ls))))); Breite
</code>
Es können auch andere Werte als 30, 50 und 10 oder mehr gewählt werden.
<eval>
(rucksack1 '(30 50 10) '())
</eval>
<code>
;;; Tiefensuche mit Beschraenkung
(define rucksack2
(lambda (g-ls s-ls k)
(display 'rucksack1)
(display g-ls)(display s-ls)(newline)
(if (null? g-ls)
(begin
(display s-ls) (newline))
(begin
(if (hoechstens-maxgewicht? s-ls k)
(rucksack2 (cdr g-ls) (cons (car g-ls) s-ls) k))
(if (hoechstens-maxgewicht? s-ls k)
(rucksack2 (cdr g-ls) s-ls k))))))
(define hoechstens-maxgewicht?
(lambda (ls k)
(<= (apply + ls) k)))
</code>
<eval>
(rucksack2 '(30 50 10) '() 42)
</eval>
<code>
;;; Beschraenkte Tiefensuche mit Ergebnisliste
(define rucksack3
(lambda (g-ls k)
(let ((max 0) (max-s-ls '()))
(letrec
((helfer
(lambda (g-ls s-ls) (display s-ls)(newline)
(if (null? g-ls)
(let ((gesamtgewicht (apply + s-ls))) ; apply wendet + auf die Liste an.
(if (and
(> gesamtgewicht max)
(hoechstens-maxgewicht? s-ls k))
(begin
(set! max gesamtgewicht)
(set! max-s-ls s-ls)))
(cons max-s-ls max))
(begin
(if (hoechstens-maxgewicht? s-ls k)
(helfer (cdr g-ls) (cons (car g-ls) s-ls)))
(if (hoechstens-maxgewicht? s-ls k)
(helfer (cdr g-ls) s-ls)))))))
(helfer g-ls '())))))
</code>
<eval>
(rucksack3 '(30 50 10) 42)
</eval>
<!--
<code>
(define mrl
(lambda (n)
(cond
((= n 1)(list (random n[100])))
(else (append (list (random n[100])) (mrl (- n 1)))))
))
(define rucksack3b
(lambda (n)
(let ((k -1)
(g-ls -1))
(set! k (random n[100]))
; (define g-ls -1)
(set! g-ls (mrl n))
(and
(display 'rs3b)
(display g-ls)
(display k)
)
(let ((max 0) (max-s-ls '()))
(letrec
((helfer
(lambda (g-ls s-ls) (display s-ls)(newline)
(if (null? g-ls)
(let ((gesamtgewicht (apply + s-ls))) ; apply wendet + auf die Liste an.
(if (and
(> gesamtgewicht max)
(hoechstens-maxgewicht? s-ls k))
(begin
(set! max gesamtgewicht)
(set! max-s-ls s-ls)))
(cons max-s-ls max))
(begin ;rek. Aufufe
(if (hoechstens-maxgewicht? s-ls k)
(helfer (cdr g-ls) (cons (car g-ls) s-ls)))
(if (hoechstens-maxgewicht? s-ls k)
(helfer (cdr g-ls) s-ls)))))))
(helfer g-ls '()))))))
</code>
<eval>
(rucksack3b 3)
</eval>
-->
[[Bild:BS_Baum4.jpg]]
[[Bild:BS_graph_veranschaulichung.gif]]
[[Bild:BS_4_red_part.jpg]]