AuKAuKAuK43
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
== Lösung des 0/1 Rucksackproblems ==
Beim Rucksackproblem handelt es sich um ein Optimierungsproblem der Kombinatorik. Aus einer bestimmten Menge von Objekten, die jeweils ein Gewicht und einen Wert haben, soll eine Teilmenge ausgewählt werden, deren Gesamtgewicht ein vorgegebenes Gewichtslimit nicht überschreitet.
Hierbei gilt die Optimalitätsbedingung, denn die optimale Gesamtlösung lässt sich aus optimalen Teilproblemen zusammensetzen.
Bezogen auf das Rucksackproblem bedeutet das, Gegenstand i wird in den optimal gefüllten, auch leeren, Rucksack gelegt. D.h. alle zur Auswahl stehenden Gegenstände können solange in den Rucksack gelegt werden, solange sie noch Platz haben.
Für den optimal gefüllten Rucksack gilt die rekursive Definition mit:
$i=\text{ Gegenstand }$
$g=\text{ Gewicht }$
$w=\text{ Wert des Gegenstands }$
$n = \text { Anzahl der Gegenstände }$
$K = \text{ Kapazität des Rucksacks }$
$wert(i,g) = \text{ Optimaler Wert für die Gegenstände }$
$wert(n,K)=\text{ Optimaler Gesamtwert }$
$wert(i,g) = \begin{cases}
0, & wenn \ i =0 \\
wert(i-1, g), & wenn \ i > 0 \ und \ g-g_{i} < 0\\
max(wert(i-1,g), wert(i-1, g-g_{i})+w_{i}), & sonst \\
\end{cases}$
Der Fall $wert(i,g) = wert(i-1,g)$ bezieht sich auf einen Gegenstand, der die Restkapazität des Rucksacks überschreiten würde. D.h. $wert(i-1,g)$ ist der Maximalwert aus $1,2,...,i-1$ Gegenständen mit Bezug auf die Kapazität des Rucksacks. Der letzte Fall $wert(i,g) = max(wert(i-1,g), wert(i-1, g-g_{i})+w_{i})$ beschreibt die Maximierung des Wertes in Berücksichtigung des Gewichtes.
===Iterativer Algorithmus===
Der iterative Lösungsansatz lässt sich, wie bereits erwähnt, nicht mit einer rekursiven Vorschrift umsetzen. Jedoch ist es möglich, die Überlegungen aus dieser Vorschrift zu verwenden und in einen iterativen Lösungsansatz umzuwandeln.
Das soll am folgenden Beispiel demonstriert werden:
<table border="1" bordercolor="#000000" style="background-color:#FFFFFF" width="20%" cellpadding="2" cellspacing="1">
<tr>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">$i$</td>
<td style="text-align: center;width: 5mm;">1</td>
<td style="text-align: center;width: 5mm;">2</td>
<td style="text-align: center;width: 5mm;">3</td>
<td style="text-align: center;width: 5mm;">4</td>
<td style="text-align: center;width: 5mm;">5</td>
</tr>
<tr>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">$g_i$</td>
<td style="text-align: center;width: 5mm;">2</td>
<td style="text-align: center;width: 5mm;">2</td>
<td style="text-align: center;width: 5mm;">6</td>
<td style="text-align: center;width: 5mm;">5</td>
<td style="text-align: center;width: 5mm;">4</td>
</tr>
<tr>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">$w_i$</td>
<td style="text-align: center;width: 5mm;">6</td>
<td style="text-align: center;width: 5mm;">3</td>
<td style="text-align: center;width: 5mm;">5</td>
<td style="text-align: center;width: 5mm;">4</td>
<td style="text-align: center;width: 5mm;">6</td>
</tr>
</table>
Zur Lösung wird die Gegenstandsliste mit der Prozedur $gegenstaende$ (Quelle: [1], S. 102) auf Vektoren als Gewicht/Wert-Paar abgebildet. Auf das jeweilige Gewicht bzw. den jeweiligen Wert kann dann mittels der Prozeduren $gewicht$ und $wert$ zugegriffen werden. Die Prozedur $gesamtwert-iterativ$ füllt dann eine Tabelle mit den jeweils maximalen Gesamtwerten für die aktuell betrachteten Gegenstände (Zeile) und das darauf bezogene Gesamtgewicht (Spalte). Das Problem hierbei ist die Speicherung aller Werte in der Tabelle, was eine sehr hohe Speicherbelastung nach sich zieht. Für den hier dargestellten Fall genügt es jedoch, wie in der rekursiven Vorschrift notiert, die jeweils letzten beiden Zeilen (zeileAlt und zeileNeu) zu speichern. D.h. die $i$-te Zeile wird aus der $i-1$-ten Zeile berechnet.
<code id="52822b4acd936">
(define gegenstaende
(list->vector
'("dummy"
(2 . 6)
(2 . 3)
(6 . 5)
(5 . 4)
(4 . 6))))
;Liste wird auf Vektor abgebildet, hier von 0 bis 5, um die Nummerierung mit 1 zu starten, wird 0 nicht benutzt(dummy).
(define gewicht
(lambda(i)
(car (vector-ref gegenstaende i))))
;um auf das Gewicht zuzugreifen, wird auf das erste Element aus dem Vektor an der Position i zugegriffen.
(define wert
(lambda(i)
(cdr (vector-ref gegenstaende i))))
;um auf den Wert zuzugreifen, wird auf das erste Element aus dem Vektor an der Position i zugegriffen.
(define vector-copy
(lambda (v)
(let* ((l (vector-length v))
(v-duplikat (make-vector l)))
(do ((i 0 (+ i 1)))((= i l) v-duplikat)
(vector-set! v-duplikat i (vector-ref v i))))))
(define gesamtwert-iterativ
(lambda(n k)
(let ((zeileAlt (make-vector (+ k 1) 0))
(zeileNeu (make-vector (+ k 1) 0)))
(do ((z 1 (+ z 1))) ;Zeile
((> z n)(vector-ref zeileNeu k));Resultat
(set! zeileAlt (vector-copy zeileNeu))
(let ((gewicht-z (gewicht z)))
(do ((s 1 (+ s 1))) ;Spalte
((> s k))
(if (< s gewicht-z)
(vector-set! zeileNeu s (vector-ref zeileAlt s))
(vector-set! zeileNeu s
(max
(vector-ref zeileAlt s)
(+ (vector-ref
zeileAlt
(- s gewicht-z))
(wert z)))))))))))
</code>
<run id="52822b4acd9fe">(gesamtwert-iterativ 5 10)</run>
Der Aufruf von (gesamtwert-iterativ 5 10) erzeugt folgende Tabelle:
<table border="1" bordercolor="#000000" style="background-color:#FFFFFF" width="40%" cellpadding="2" cellspacing="1">
<tr>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">$n/K$</td>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">$0$</td>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">$1$</td>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">$2$</td>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">$3$</td>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">$4$</td>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">$5$</td>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">$6$</td>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">$7$</td>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">$8$</td>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">$9$</td>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">$10$</td>
</tr>
<tr>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">$0$</td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">0</td>
</tr>
<tr>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">$1:(g_i=2; w_i=6)$</td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">0</td>
<th style="text-align: center;width: 5mm;">6</th>
<td style="text-align: center;width: 5mm;">6</td>
<td style="text-align: center;width: 5mm;">6</td>
<td style="text-align: center;width: 5mm;">6</td>
<td style="text-align: center;width: 5mm;">6</td>
<td style="text-align: center;width: 5mm;">6</td>
<td style="text-align: center;width: 5mm;">6</td>
<td style="text-align: center;width: 5mm;">6</td>
<td style="text-align: center;width: 5mm;">6</td>
</tr>
<tr>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">$2:(g_i=2; w_i=3)$</td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">6</td>
<td style="text-align: center;width: 5mm;">6</td>
<th style="text-align: center;width: 5mm;">9</th>
<td style="text-align: center;width: 5mm;">9</td>
<td style="text-align: center;width: 5mm;">9</td>
<td style="text-align: center;width: 5mm;">9</td>
<td style="text-align: center;width: 5mm;">9</td>
<td style="text-align: center;width: 5mm;">9</td>
<td style="text-align: center;width: 5mm;">9</td>
</tr>
<tr>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">$3:(g_i=6; w_i=5)$</td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">6</td>
<td style="text-align: center;width: 5mm;">6</td>
<td style="text-align: center;width: 5mm;">9</td>
<td style="text-align: center;width: 5mm;">9</td>
<td style="text-align: center;width: 5mm;">9</td>
<td style="text-align: center;width: 5mm;">9</td>
<td style="text-align: center;width: 5mm;">11</td>
<td style="text-align: center;width: 5mm;">11</td>
<td style="text-align: center;width: 5mm;">14</td>
</tr>
<tr>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">$4:(g_i=5; w_i=4)$</td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">6</td>
<td style="text-align: center;width: 5mm;">6</td>
<td style="text-align: center;width: 5mm;">9</td>
<td style="text-align: center;width: 5mm;">9</td>
<td style="text-align: center;width: 5mm;">9</td>
<td style="text-align: center;width: 5mm;">10</td>
<td style="text-align: center;width: 5mm;">11</td>
<td style="text-align: center;width: 5mm;">13</td>
<td style="text-align: center;width: 5mm;">14</td>
</tr>
<tr>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">$5:(g_i=4; w_i=6)$</td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">6</td>
<td style="text-align: center;width: 5mm;">6</td>
<td style="text-align: center;width: 5mm;">9</td>
<td style="text-align: center;width: 5mm;">9</td>
<td style="text-align: center;width: 5mm;">12</td>
<td style="text-align: center;width: 5mm;">12</td>
<th style="text-align: center;width: 5mm;">15</th>
<td style="text-align: center;width: 5mm;">15</td>
<td style="text-align: center;width: 5mm;">15</td>
</tr>
</table>
===Rekursiver Algorithmus===
Die Lösung des 0/1 Rucksackproblems mittels Rekursion wird im Folgenden mit einer Prozedur gezeigt, die im ersten Teil ohne memoizing und im zweiten Teil mit memoizing arbeitet.
====Ohne Memoizing====
Als erstes wird die Prozedur (Quelle: [1], S. 106) ohne memoizing implementiert. Die rekursive Definition kann leicht in die Prozedur überführt werden:
<popup><math>$wert(i,g) = \begin{cases}
0, & wenn \ i =0 \\
wert(i-1, g), & wenn \ i > 0 \ und \ g-g_{i} < 0\\
max(wert(i-1,g), wert(i-1, g-g_{i})+w_{i}), & sonst \\
\end{cases}$
</math></popup>
<code id="52822a9552f91" hidden>
(define gegenstaende
(list->vector
'("dummy"
(2 . 6)
(2 . 3)
(6 . 5)
(5 . 4)
(4 . 6))))
(define gewicht
(lambda (i)
(car (vector-ref gegenstaende i))))
(define wert
(lambda (i)
(cdr (vector-ref gegenstaende i))))
</code>
<code id="52822a955300f">
(define gesamtwert-rekursiv
(lambda (n k)
(let ((rek-aufrufe 0))
(letrec
((gesamtwert
(lambda (i g)
(set! rek-aufrufe (+ rek-aufrufe 1))
(cond
((= i 0) 0)
((> (gewicht i) g) (gesamtwert (- i 1) g))
(else
(max
(gesamtwert (- i 1) g)
(+ (gesamtwert (- i 1) (- g (gewicht i)))(wert i))))))))
(list (gesamtwert n k) rek-aufrufe)))))
</code>
<run id="52822ade4b41b">(gesamtwert-rekursiv 5 10)</run>
Durch die rekursiven Aurufe wird auch die Menge der zu lösenden Teilprobleme bestimmt. Deshalb kommt es in der Prozedur zu Mehrfachberechnungen. Um dies zu verhindern, wird das sogenannte memoizing eingesetzt. Bei dieser Technik wird vor der Berechnung eines neuen Wertes in der Tabelle nachgeschaut, ob dieser Wert bereits vorhanden ist. Wenn er vorhanden ist, wird er verwendet. Ist er nicht vorhanden, wird er berechnet und zur weiteren Verarbeitung in die Tabelle übernommen. Das wird am folgenden Beispiel gezeigt:
====Mit Memoizing====
Um die rekursive Prozedur (Quelle: [1], S. 107) mit memoizing zu implementieren, benötigt es nur wenige Änderungen im bereits vorhandenen Quellcode.
<code id="5282291a7f486" hidden>
(define gegenstaende
(list->vector
'("dummy"
(2 . 6)
(2 . 3)
(6 . 5)
(5 . 4)
(4 . 6))))
;Liste wird auf Vektor abgebildet, hier von 0 bis 5, um die Nummerierung mit 1 zu starten, wird 0 nicht benutzt(dummy).
(define gewicht
(lambda(i)
(car (vector-ref gegenstaende i))))
;um auf das Gewicht zuzugreifen, wird auf das erste Element aus dem Vektor an der Position i zugegriffen.
(define wert
(lambda(i)
(cdr (vector-ref gegenstaende i))))
;um auf den Wert zuzugreifen, wird auf das erste Element aus dem Vektor an der Position i zugegriffen.
</code>
<code id="5282291a7f50d">
(define gesamtwert-rekursiv-memo
(let ((memoliste '()))
(lambda (n k)
(let ((rek-aufrufe 0))
(letrec
((gesamtwert-memo
(lambda (i g)
(let ((memowert (assoc (cons i g) memoliste)))
(if memowert
(cdr memowert)
(let ((resultat (gesamtwert i g)))
(set! memoliste
(cons (cons (cons i g) resultat) memoliste))
resultat)))))
(gesamtwert
(lambda (i g)
(set! rek-aufrufe (+ rek-aufrufe 1))
(cond
((= i 0) 0)
((> (gewicht i) g) (gesamtwert-memo (- i 1) g))
(else
(max
(gesamtwert-memo (- i 1) g)
(+ (gesamtwert-memo (- i 1) (- g (gewicht i)))(wert i))))))))
(list (gesamtwert n k) rek-aufrufe (length memoliste)))))))
</code>
<run id="5282291a7f596">(gesamtwert-rekursiv-memo 5 10)</run>
Als Résumé bleibt festzuhalten, dass die Ergebnisse mit denen der iterativen Prozedur übereinstimmen. Die rekursive Berechnung ohne memoizing ist selbstverständlich nicht tauglich, da durch die unnötige Mehrfachberechnung die Zahl der rekursiven Aufrufe viel zu hoch ist. Der memoizing- Methode wiederum sollte man den Vorzug vor der iterativen Methode geben, denn sie ist mindestens so schnell wie diese, ermöglicht eine direkte Ableitung der rekursiven Regeln und vermeidet die fehleranfällige Transformation in einen iterativen Bottom-up-Algorithmus.
== 0/1 Rucksackproblem ==
Die Optimalitätsbedingung ist erfüllt, da der Gegenstand i in den bis dahin optimal gepackten Rucksack, natürlich bisher ohne i, gepackt wird. So erhält man auf jeden Fall einen optimal gepackten Rucksack, der den Gegenstand i enthält. Dadurch werden alle Gegenstände, wenn sie noch hineinpassen, in einen optimal gepackten Rucksack eingepackt.
Für Gesamtwert wert(n, k) des Rucksacks folgende rekursive Beziehung:
<p>
<math>wert(i,g) = \left {0, wenn i = 0\\
{wert(i - 1, g), wenn i > 0 und g - g_{i} < 0}\\ max(wert(i-1,g), wert(i - 1, g-g_{i} + w_{i}), sonst </math>
</p>
<p>
Die Bezeichnung wert(n,K) bezeichnet den größtmöglichen Wert des Rucksackinhaltes, wobei man am Anfang die volle Kapazität K zur Verfügung hat. Die Gegenstände werden mit 1, 2, … durchnummeriert.
Der Fall wert(i,g) = wert(i-1,g) zeigt an, dass der Gegenstand i nicht in den Rucksack gepackt wurde, da der Gesamtinhalt sonst die verbliebene Kapazität überschritten hätte. Der Maximalwert, der durch die Aufnahme von Gegenständen aus 1, 2, …, i-1 erzielt worden ist, wird mit wert(i-1, g) bezeichnet und berücksichtigt die vorhandene Kapazität. Logischerweise gibt es keinen Wertzuwachs, wenn der Gegenstand i, obwohl er in den Rucksack passen würde, nicht eingepackt wird. Der dritte Fall der Definition beschreibt die Aufnahme von i, die Reduzierung der Restkapazität durch g-gi und die Steigerung des Gesamtwertes durch wi. Dabei wird nicht ausgeschlossen, dass ein höherer Gesamtwert entsteht, wenn man den Gegenstand i, obwohl man ihn hätte einpacken können, nicht einpackt. Deswegen ist die in der Definition angegebene Maximumbestimmung aus wert(i-1,g) und wert(i-1, g-gi)+wi erforderlich.
Zunächst verwendet man die traditionelle Form der Implementierung der „Dynamischen Programmierung“, wobei man die rekursiv definierte Funktion wert nicht verwenden darf, aber die Überlegungen, die zu dieser führten.
</p>
<p>Beispiel mit K = 120
[[Bild:Simaknoc_Gegenstaende.PNG]]
</p>
<p>Die Gegenstände sind absichtlich nicht nach ihrem Gewicht geordnet. </p>
Für die Gegenstandsliste wird ein Vektor verwendet, dessen Komponenten von den Gewicht-Wert-Paaren der Gegenstände gebildet werden. Dabei soll die Nummerierung der Gegenstände wie in der obigen Tabelle bei 1 beginnen. Deswegen belegt man die 0-te Vektorkomponente mit „dummy“.
<code id="4be68060c950a">
(define gegenstaende
(list->vector
'("dummy"
(13 . 19)
(11 . 20)
(17 . 23)
(15 . 21)
(16 . 27)
(14 . 25)
(18 . 25)
(10 . 18)
(19 . 24)
(12 . 17))))
(define gewicht
(lambda (i)
(car (vector-ref gegenstaende i))))
(define wert
(lambda (i)
(cdr (vector-ref gegenstaende i))))
</code>
<code id="4be910be75d46">(define vector-copy
(lambda (v)
(let* ((l (vector-length v))
(v-duplikat (make-vector l)))
(do ((i 0 (+ i 1)))((= i l) v-duplikat)
(vector-set! v-duplikat i (vector-ref v i))))))</code>
Für die Lösung wird eine Tabelle mit n+1 Zeilen, also für jeden der Gegenstände i = 1, 2, …, n eine und eine zusätzliche Zeile 0 für den Wert des anfänglich leeren Rucksackes, die Initialisierung, sozusagen den Anfangsgesamtwert 0. Die Spaltenköpfe werden von allen möglichen Gewichtssummen von 0 bis K, also im Beispiel von 0 bis 120, gebildet. Der Tabellenkörper enthält jeweils die maximalen Gesamtwerte bezogen auf die bis dahin betrachteten Gegenstände (Zeilen) und das aktuelle Gesamtgewicht (Spalte).
[[Bild:Simaknoc_Tabelle_Rucksack.jpg]]
Die rechte untere Ecke der Tabelle (Matrix) zeigt das gesuchte Maximum R = wert(10,120).
Eine Implementierung des iterativen Verfahrens mit dieser Matrix ist unnötig speicheraufwändig und da man gemäß der rekursiven Vorschrift (7.1 Seite 101) die i-te Zeile mit Hilfe der i-1-ten Zeile berechnet, reicht es auch, wenn man die letzten beiden Zeilen, in der Prozedur zeilealt und zeileneu, bereithält. Für die Repräsentation in Scheme benutzt man vier Vektoren.
<code id="4be910be76518">
(define gesamtwert-iterativ
(lambda (n k)
(let ((zeilealt (make-vector (+ k 1) 0))
(zeileneu (make-vector (+ k 1) 0)))
(do (( z 1 (+ z 1))) ;Zeile
((> z n)(vector-ref zeileneu k)) ;Resultat
(set! zeilealt (vector-copy zeileneu))
(let ((gewicht-z (gewicht z)))
(do ((s 1 (+ s 1))) ;Spalte
((> s k))
(if (< s gewicht-z)
(vector-set! zeileneu s (vector-ref zeilealt s))
(vector-set! zeileneu s
(max
(vector-ref zeilealt s)
(+ (vector-ref
zeilealt
(- s gewicht-z))
(wert z)))))))))))
</code>
<run id="4be68060c9d6f">(gesamtwert-iterativ 10 120)</run>
-Wird die Protokollzeile entfernt, gibt die Prozedur einfach nur das Ergebnis, in diesem Fall 183, wider.-
----