Dynamisches Programmieren SS09

Aus ProgrammingWiki

Archivierte Version vom 2009-05-02T12:11:35+00:00. Aktuelle Version

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

Wenn nun aus der rekursiven Beschreibung eine optimale Lösung ebenfalls rekursiv erstellt werden soll, stoßen wir auf das Problem, dass wir selten unabhängige und überlappungsfreie Teilprobleme erhalten. Das wird schon deutlich wenn wir uns die Berechnung von fib(5) ansehen. Dabei müssen bei einer rekursiven Lösung erheblich viele Teilprobleme mehrfach berechnet werden. Im Bild sind diese Probleme grau hervorgehoben, ebenso wie fib(1) und fib(0), da diese bekannte Werte sind die ohnehin nicht 'berechnet' werden müssen.

Weiterhin kann es passieren das die zu lösenden Teillprobleme unausgewogen sind. Das bedeutet, dass ein besonders schwierig zu lösendes Teilproblem den Erfolg der ganzen Methode zunichte macht.

Da bei dynamischer Programmierung alle Teilprobleme berechnet werden kann eine sehr große Anzahl dieser ebenfalls zum Problem werden. So zum Beispiel beim Schach, wo es bekanntermaßen sehr viele Teilprobleme gibt, also die Kombination aller möglichen Positionen aller Figuren auf dem Brett. Zudem ist nicht bei jedem Problem garantiert, dass aus der Kombination der optimalen Teillösungen eine optimale Gesamtlösung entsteht.

Überlappenden Teilprobleme

Wie bereits bekannt finden wir selten Probleme, die aus unabhängigen Teilproblemen bestehen und somit eine rekursive Lösung einen erheblichen Mehraufwand betreiben würde. Die Anwendung Dynamischer Programmierung macht jedoch vor allem in solchen Fällen Sinn, also wenn Teilprobleme ihrerseits gemeinsame Teilprobleme nutzen. Dabei entfällt die erneute Berechnung von Teilproblemen, da deren Lösungen ja in einer Tabelle gespeichert werden. Wenn man sich das Beispiel der Berechnung von fib(5) ansieht, kann man sehr gut erkennen, dass somit die Berechnung von fib(n-2) komplett entfallen kann, da der Wert bereits durch die Berechnung von fib(n-1) bekannt ist.

Der damit eingesparte Zeitaufwand sollte dabei natürlich über dem zeitlichen Mehraufwand durch die Berechnung aller nicht benötigten Teilprobleme liegen. Das ist bei der Berechnung der Fibonacci-Zahlen natürlich immer der Fall, da sämtliche Teilprobleme zur Berechnung benötigt werden.

Iterativ oder rekursiv?

Unseren Überlegungen zufolge wäre es also nicht von Vorteil einen rekursiven Lösungsansatz zu verwenden, da eine rekursive Lösung ineffizienter ist und somit der rekursive Lösungsansatz erst in eine iterative Lösung übertragen werden muss. Dabei ist ein erheblich hoher Denkaufwand zu leisten der somit auch in hohem Maße fehleranfällig ist.

Aber gibt es eine Möglichkeit die Effizienz einer rekursiven Lösung zu steigern, und zwar: memoizing.

Dabei werden die rekursiv berechneten Teilprobleme, wie bei einem iterativen Ansatz in einer Tabelle zwischengespeichert. Vor der Berechnung eines Teilproblems wird nun zunächst in dieser Tabelle nachgeschlagen ob bereits eine Lösung vorhanden ist. Ist dies der Fall kann die erneute Berechnung entfallen. wenn nicht, so wird der gesuchte Wert berechnet und danach in die Tabelle eingetragen.

Somit können wir also doch einen rekursiven Lösungsansatz verwenden. Da dafür erheblich weniger Denkaufwand zu leisten ist, ist somit unsere Lösung weniger fehleranfällig.

Im folgenden werden nun iterative und rekursive Lösungen am Beispiel des bereits bekannten Rucksackproblems verglichen.

Iterative Berechnung

ToDo - Norbert

Rückkehr des Rucksackproblems

Dimension der Tabelle

Implementation

Aufwandsbetrachtung

Rekursive Berechnung

ToDo - Markus

ohne memoizing

private int rekursiveAufrufe;
private java.util.HashMap gegenstaende = new java.util.HashMap();
        gegenstaende.put(1, new java.awt.Point(13,19));
        gegenstaende.put(2, new java.awt.Point(11,20));
        gegenstaende.put(3, new java.awt.Point(17,23));
        gegenstaende.put(4, new java.awt.Point(15,21));
        gegenstaende.put(5, new java.awt.Point(16,27));
        gegenstaende.put(6, new java.awt.Point(14,25));
        gegenstaende.put(7, new java.awt.Point(18,25));
        gegenstaende.put(8, new java.awt.Point(10,18));
        gegenstaende.put(9, new java.awt.Point(19,24));
        gegenstaende.put(10, new java.awt.Point(12,17));

private int gesamtwertRekursiv(int kapazitaet)
    {
        rekursiveAufrufe = 0;
        return gesamtWert(gegenstaende.size(),kapazitaet);
    }
private int gesamtWert(int pos,int kapazitaet)
    {
        rekursiveAufrufe++;
        if(pos==0)
        {
            return 0;
        }
        else
        {
            if(gegenstaende.get(pos).getX()>kapazitaet)
            {
                return gesamtWert(pos-1,kapazitaet);
            }
            else
            {
                int var1 = gesamtWert(pos-1,kapazitaet);
                int var2 = gesamtWert(pos-1,kapazitaet-(int)gegenstaende.get(pos).getX()) + (int)gegenstaende.get(pos).getY();
                if(var1>var2)
                {
                    return var1;
                }
                else
                {
                    return var2;
                }
            }
        }
    }
private int getRekursiveAufrufe()
    {
        return rekursiveAufrufe;
    }

<eval> System.out.println("Ergebnis rekursiv ohne memoizing: " + gesamtwertRekursiv(120)); System.out.println("Rekursive Aufrufe: " + getRekursiveAufrufe()); </eval>

mit memoizing

private HashMap memoliste = new java.util.HashMap();

private int gesamtwertRekursivMemo(int kapazitaet)
    {
        rekursiveAufrufe = 0;
        return gesamtWert1(gegenstaende.size(),kapazitaet);
    }
private int gesamtWert1(int pos,int kapazitaet)
    {
        rekursiveAufrufe++;
        if(pos==0)
        {
            return 0;
        }
        else
        {
            if(gegenstaende.get(pos).getX()>kapazitaet)
            {
                return gesamtWertMemo(pos-1,kapazitaet);
            }
            else
            {
                int var1 = gesamtWertMemo(pos-1,kapazitaet);
                int var2 = gesamtWertMemo(pos-1,kapazitaet-(int)gegenstaende.get(pos).getX()) + (int)gegenstaende.get(pos).getY();
                if(var1>var2)
                {
                    return var1;
                }
                else
                {
                    return var2;
                }
            }
        }
    }
    private int gesamtWertMemo(int pos, int kapazitaet)
    {
        if(memoliste.containsKey(pos))
        {
            if(memoliste.get(pos).containsKey(kapazitaet))
            {
                return memoliste.get(pos).get(kapazitaet);
            }
            else
            {
                int resultat = gesamtWert1(pos,kapazitaet);
                memoliste.get(pos).put(kapazitaet, resultat);
                return resultat;
            }
        }
        else
        {
            int resultat = gesamtWert1(pos,kapazitaet);
            HashMap temp = new HashMap();
            temp.put(kapazitaet, resultat);
            memoliste.put(pos, temp);
            return resultat;
        }
    }
    public int getRekursiveAufrufe()
    {
        return rekursiveAufrufe;
    }
    public int getLengthMemoListe()
    {
        int size = 0;
        for(int i= 0 ; i < memoliste.size();i++)
        {
            size+=memoliste.get(i).size();
        }
        return size;
    }

<eval> System.out.println("Ergebnis rekursiv mit memoizing: " + dynaRucksack.gesamtwertRekursivMemo(120)); System.out.println("Rekursive Aufrufe: " + dynaRucksack.getRekursiveAufrufe()); System.out.println("Länge der Memoliste: " + dynaRucksack.getLengthMemoListe()); </eval>

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

int fib(int n)
    {
        if (n < 2)
        {
            return 1;
        }
        else
        {
            return fib(n - 1) + fib(n - 2);
        }
    }

<eval>System.out.println(fib(15));</eval>

mit memoziing

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));
        }
    }

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

Rundreiseproblem

ToDo - Markus

(Ablaufkoordination von Magnetbändern)

ToDo - ?

Java, C# und F# Versionen

Beispiele als Java Version

Beispiele als C# und teilweise in F#

Files

Folien, Beispiele...

Links

MSDN F#

F# Compiler Download (auch für Mono)

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

Dynamisches Programmieren SS09

Inhaltsverzeichnis

Eigenschaften

Bottom-up

Schwierigkeiten

Überlappenden Teilprobleme

Iterativ oder rekursiv?

Iterative Berechnung

Rückkehr des Rucksackproblems

Dimension der Tabelle

Implementation

Aufwandsbetrachtung

Rekursive Berechnung

ohne memoizing

mit memoizing

Fazit

Optimale Teilstruktur

Vorgehensweise beim Aufdecken

Raum der Teilprobleme charakterisieren

Ungewichteter einfacher Pfad

Beispiele

Fibonacci-Zahl

ohne memoizing

mit memoziing

Rundreiseproblem

(Ablaufkoordination von Magnetbändern)

Java, C# und F# Versionen

Files

Links

Literatur

Suche