AuK/Dynamisches Programmieren SS10
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
'''Autoren:'''
<p>Katja Lemberg ([mailto:sikalemb@stud.hs-zigr.de sikalemb@hs-zigr.de])</p>
<p>Marlene Knoche ([mailto:simaknoc@stud.hs-zigr.de simaknoc@hs-zigr.de])</p>
----
== Einführung ==
Das Ziel der dynamischen Programmierung ist die Suche nach effizienten Algorithmen für Optimierungs- und Entscheidungsprobleme. Dabei ist der Begriff „Dynamisches Programmieren“ eher unpassend, da sich der Begriff „Programmieren“ in diesem Zusammenhang auf die tabellarische Methode und nicht auf das Schreiben von Code bezieht. Besser wäre der Begriff „Dynamisches Optimieren“, da eigentlich die Optimierung des Programmablaufes angestrebt wird.
Die Grundlage für die „Dynamische Programmierung“ war „Teile und Herrsche“.
----
== Dynamisches Programmieren ==
=== Bottom up Ansatz ===
Dieser Ansatz besagt, dass sich die optimale Lösung eines Problems aus optimalen Lösungen von Teilproblemen des Gesamtproblems zusammen setzt, was man auch als Optimalitätsbedingung bezeichnet. Dabei werden alle Teillösungen „von unten her“ betrachtet und die Lösungen werden in eine Tabelle eingetragen. Die Berechnung jeweils aufeinander folgender Tabelleneinträge nutzt bereits vorhandene Einträge zur Berechnung.
Die Entwicklung eines dynamischen Programmes kann man in vier Schritten darstellen.
# Charakterisieren der Struktur einer optimalen Lösung
# Wert einer optimalen Lösung rekursiv definieren
# Wert einer optimalen Lösung durch Bottom-Up-Ansatz berechnen
# zugehörige optimale Lösung aus schon berechneten Daten konstruieren
Auch bei der „Dynamischen Programmierung“ gibt es gewisse Schwierigkeiten. Zum einen ist die Zerlegung eines großen Problems in kleinere unabhängige und überlappungsfreie Teilprobleme meist eine Illusion und die Teilprobleme sind meist nicht ausgewogen, das heißt, dass ein besonders aufwändig zu lösendes Teilproblem den Erfolg der Methode zunichte machen kann. Die Optimalitätsbedingung muss nicht in jedem Fall erfüllt sein. Das bedeutet, dass nicht zwingend ein Zusammenfügen aller optimalen Teillösungen eine optimale Gesamtlösung ergibt. Außerdem kann die Anzahl der Teilprobleme, die gelöst werden müssten, unvertretbar hoch sein, somit wäre der Aufwand für die Anwendung der „Dynamischen Programmierung“ höher als der Aufwand für die Lösung des Gesamtproblems.
Der Berechnungsprozess wird traditionell iterativ organisiert. Es werden also die Zeilen einer entsprechenden Tabelle nacheinander ausgefüllt. Auf den ersten Blick ist diese Berechnungsmethode aus Aufwandsgründen der rekursiven vorzuziehen, da für jedes Feld der Tabelle oder Matrix mit der Form (z,s) genau ein Resultat ermittelt werden muss. Es kann bei Lösungen, die rekursiv definiert und durch rekursive Prozeduren berechnet wurden, zu Mehrfachberechnungen von Teilausdrücken kommen.
Beispiel: Fib(5)
[[Bild:Simaknoc_Fibbaum.png]]
Bei „Dynamischer Programmierung“ wird der Aufwand für wiederholte und somit unnötige Berechnungen vermieden, was jedoch nicht einfach so passiert. Um diese Vermeidung herbeizuführen berechnet man alle Teillösungen, also auch diejenigen, die mit der optimalen Gesamtlösung am Ende nichts zu tun, somit keinen Einfluss auf diese haben.
Wesentlich problematischer als diese zusätzlichen Berechnungen ist es den rekursiven Top-Down-Ansatz in einen Bottom-Up-Algorithmus umzuwandeln. Ein Bottom-Up-Algorithmus durchläuft eine zweidimensionale Tabelle im Allgemeinen mittels zwei verschachtelter Schleifen. Deswegen kann die Umwandlung schwierig sein, da sie mentalen Zusatzaufwand erfordert und somit fehleranfällig ist. Dazu kommt das eine Lösung durch eine rekursive Beschreibung fixiert ist und sich der „Geist dagegen sträubt“ die Transformation durchzuführen.
Der Ausweg aus dieser Zwickmühle heißt „Memoizing“. Die Idee besteht darin rekursiv erzeugte Teilprobleme einmal zu berechnen und die Lösungen danach in eine Tabelle einzutragen. So kann und wird vor der Ausführung jeder Berechnung geprüft, ob der Wert schon in der Tabelle vorhanden ist. Sollte dem so sein, wird der Wert einfach übernommen, anderenfalls wird der Wert ganz einfach berechnet und danach in die Tabelle eingetragen.
=== Vergleich zu "Teile und Herrsche" ===
[[Bild:Simaknoc_Vergleichstabelle.PNG]]
----
<language>Scheme</language>
== 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 hidden>(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).
<!--Tabelle ausm Buch!-->
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>
(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>
<eval id="4be68060c9d6f">(gesamtwert-iterativ 10 120)</eval>
-Wird die Protokollzeile entfernt, gibt die Prozedur einfach nur das Ergebnis, in diesem Fall 183, wider.-
----
== Aufwandsbetrachtung ==
Beim Betrachten der Prozedur gesamtwert-iterativ ist direkt zu erkennen, dass ein Aufwand zur Berechnung der Tabelle in
<math>\mathcal{O}(n * K) * \mathcal{O} (1) = \mathcal{O} (nK) </math>
erforderlich ist.
In Anbetracht des uniformen Komplexitätsmaßes kann man K als Konstante auffassen, wodurch sich ein linearer Aufwand <math>\mathcal{O}(n)</math>ergibt. Allerdings handelt es sich dabei nicht um Tatsachen, da für alle n Gegenstände <math>g_{i}<= K</math> gilt. Damit hat K einen direkten Bezug auf n.
Im Folgenden untersuchen wir die Eingabelänge einer beliebigen Instanz des 0/1 Rucksackproblems.
Die Eingabe setzt sich aus 2n+1 natürlichen Zahlen zusammen:
<math>g_{1}, g_{2}, ..., g_{n}, w_{1}, w_{2}, ..., w_{n}</math> und K in Binärdarstellung.
Zudem definieren wir <math> \hat w = max \lbrace{w_{1}, w_{2}, ..., w_{n}}\rbrace </math>
Die Eingabelänge wird durch <math> \mathcal{O} (n*(log_{2}K + log_{2} \hat w) + log_{2}K) = \mathcal{O}(n* (log_{2} K + \hat w ))</math> nach oben beschränkt.
Angenommen, K lässt sich in der Form <math>K = 2_{n}</math> darstellen und, so liegt die Eingabelänge in <math> \mathcal{O} (n^2)</math> und die Rechenzeit des Algorithmus ist exponentiell, nämlich <math>\mathcal {O}(n * 2^n) </math>.
Die Beschränkung für K und damit auch für sämtliche <math>g_{i}</math>durch Polynom in n gilt für viele Anwendungen. So zum Beispiel <math> K \leq n^{10}</math>, wodurch sich eine tatsächliche Rechenzeit in <math>\mathcal{O}(n^{11} )</math> ergibt.
Allgemein ist das aber nicht die Regel. So ist die Suche nach einem Lösungsverfahren mit Polynomzeit recht aussichtslos.
Dennoch: Das 0/1-Rucksackproblem ist eines der wenigen Probleme mit folgenden Eigenschaften:
* Die größte Zahl der Eingabe, also K, lässt sich durch kein Polynom in der Länge der Eingabe in der üblichen Darstellung, hier also 2n+1 oder einfach n, beschränken.
* Es gibt einen Algorithmus zur Lösung des Problems, dessen Rechenzeit durch ein Polynom, hier <math>\mathcal{O}(nK)</math>, in der Eingabelänge und der größten Zahl der Eingabe abgeschätzt werden kann.
Ein solcher Algorithmus heißt pseudopolynomial. Es gibt nicht sehr viele Algorithmen dieser Art.
Das uniforme Komplexitätsmaß reicht also nicht aus, um die Komplexität des Verfahrens zu bewerten. Durch die Bit-Komplexität, welche die Länge der Eingabewerte berücksichtigt, wurde der exponentielle Aufwand offen gelegt. Es wird deutlich, dass das uniforme Maß in vielen Fällen zu grob ist oder überhaupt nicht anwendbar ist, wie es auch bei den pseudoplolynomialen Algorithmen der Fall ist.
Eine Rückkopplung hierfür ist in der Einführung im Abschnitt 1.4 vorzufinden.
----
== Memoizing ==
----
== Rundreiseproblem ==
----
== Übungsaufgaben ==
----
== Quellen ==
=== Literatur ===
; [1] Christian Wagenknecht
: Algorithmen und Komplexität.- Fachbuchverlag Leipzig, 2003. - ISBN 3-446-22314-2