AuK/Dynamisches Programmieren SS09

Wiki-Quelltext dieser Seite.

<language>Java</language>
Autoren: Markus Ullrich & Norbert Baum

 '''Dev-Status'''



==Eigenschaften==

 '''ToDo - Markus'''

Eine Sache vorweg:

Der Begriff "Programmierung" bezieht sich in diesem Kontext nicht auf das schreiben von Code , sondern vielmehr auf eine tabellarische Methode zum Lösen von Optimierungsproblemen. Demnach sollte die Methode besser "Dynamisches Optimieren" heißen, was jedoch die traditionelle Bezeichnung nicht mehr verdrängen kann.

Im folgenden werden nun zunächst die Eigenschaften dynamischer Programmierung erläutert.

===Bottom-up===
Genau wie die Teile-und-Herrsche-Verfahren, löst auch die Dynamische Programmierung Probleme, durch die Kombination der Lösungen von Teilproblemen. Allerdings nutzt die dynamische Programmierung einen Bottom-up-Ansatz, bei dem '''''alle''''' Teillösungen "von unten her" berechnet werden. Die bereits berechneten Teillösungen werden in einer Tabelle gespeichert, womit deren erneute Berechnung entfällt. Dabei wird erwartet, dass '''''eine''''' optimale Gesamtlösung aus optimalen Teillösungen aufgebaut werden kann. Eine solche Lösung sollte bewusst nicht als ''die'' optimale Lösung bezeichnet werden, da es verschiedene Lösungen geben kann, die den optimalen Wert besitzen.

===Schwierigkeiten===

===Überlappenden Teilprobleme===
Die Anwendung Dynamischer Programmierung macht vor allem dann Sinn, wenn ein Problem aus sich überlappenden Teilproblemen aufgebaut ist, also wenn Teilprobleme ihrerseits gemeinsame Teilprobleme nutzen. In diesem Fall würde eine rekursive Lösung wie beim Teile-und-Herrsche-Verfahren die gemeinsamen Teilprobleme wiederholt lösen und somit mehr Arbeit als notwendig ausführen.

===Iterativ oder rekursiv?===

==Iterative Berechnung==
 '''ToDo - Norbert'''

===Rückkehr des Rucksackproblems===

===Dimension der Tabelle===

===Implementation===

===Aufwandsbetrachtung===

==Rekursive Berechnung==
 '''ToDo - Markus'''

===ohne memoizing===

===mit memoizing===

===Fazit===

==Optimale Teilstruktur==
 '''ToDo - Markus'''

===Vorgehensweise beim Aufdecken===

===Raum der Teilprobleme charakterisieren===

===Ungewichteter einfacher Pfad===


==Beispiele==



===Fibonacci-Zahl===
 '''ToDo - Norbert
 Fib-mem fertig bauen!
 '''
====ohne memoizing====
<code>
int fib(int n)
    {
        if (n < 2)
        {
            return 1;
        }
        else
        {
            return fib(n - 1) + fib(n - 2);
        }
    }</code>
<eval>System.out.println(fib(15));</eval>

====mit memoziing====
<code>
private java.util.HashMap fibs = new java.util.HashMap();
 fibs.put(0, java.math.BigInteger.ONE);
 fibs.put(1, java.math.BigInteger.ONE);

    private java.math.BigInteger fib_mem(Integer n)
    {
        if(fibs.containsKey(n))
        {
            return fibs.get(n);
        }
        else
        {
            java.math.BigInteger fib1 = fib_mem(n - 1);
            fibs.put(n-1, fib1);
            java.math.BigInteger fib2 = fib_mem(n - 2);
            return (fib1.add(fib2));
        }
    }

</code>
<eval>
System.out.println(fib_mem(30));
</eval>

===Rundreiseproblem===
 '''ToDo - Markus'''
===(Ablaufkoordination von Magnetbändern)===
 '''ToDo - ?'''

==Java, C# und F# Versionen==
[[Dynamisches Programmieren/Beispiele in Java | Beispiele als Java Version]]

[[Dynamisches Programmieren/Beispiele in CSharp und FSharp | Beispiele als C# und teilweise in F#]]

==Files==
Folien, Beispiele...

==Links==
[http://msdn.microsoft.com/en-us/fsharp/default.aspx MSDN F#]

[http://research.microsoft.com/en-us/um/cambridge/projects/fsharp/release.aspx F# Compiler Download (auch für Mono)]

[http://msdn.microsoft.com/de-de/magazine/cc164244.aspx Einführung F#]

== Literatur ==
* Th. H. Cormen, Ch. E. Leiserson, R. Rivest, C. Stein: ''Algorithmen - Eine Einführung'', 2.Auflage, Oldenbourg Wissenschaftsverlag GmbH 2007, ISBN 978-3-486-58262-8

* Gessner, Wacker: ''Dynamische Optimierung - Einführung-Modelle-Computerprogramme'', 1.Auflage, Carl Hanser Verlag 1972, ISBN 3-446-11539-0

* Ch. Wagenknecht: ''Algorithmen und Komplexität'', 1.Auflage, Carl Hanser Verlag 2003, ISBN 3-446-22314-2

* A. Iwainsky: ''Dynamische Optimierung - Gegenstand-Methoden-Möglichkeiten'', 1.Auflage, VEB Verlag Technik Berlin 1984

* J. Hinrichsen: ''Branch- and Bound-Verfahren zur Lösung des Rundreiseproblems'', Vandenhoeck & Ruprecht Göttingen 1975, ISBN 3-525-12432-5

* S. Wolfgang, U. Gerhard: Dissertation ''Duale Entartung in der lineare Optimierung, Transportproblem mit zusätzlichen Nebenbedingungen und Rundreiseproblem'' TU Dresden und Bergakademie Freiberg, 21.02.1975