Dynamisches Programmieren SS09

Aus ProgrammingWiki

Archivierte Version vom 2009-05-08T09:13:54+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. Ein populäres Beispiel vom Schach ist das Springerproblem oder auch Rösselsprung genannt. Dabei geht es darum, dass ein Springer jedes Feld auf einem beliebig großen Schachbrett genau einmal besucht. Eine mögliche Lösung unterteilt das Schachbrett in kleinere Teilrechtecke, für die spezielle Lösungen existieren. Dabei können aber verbleibende Rechtecke erheblich schwerer zu lösende Teilprobleme darstellen, zudem gewisse Anschlussbedingungen zwischen den Rechtecken realisiert werden müssen. Wer sich näher für das Problem interessiert, dem wird folgende Seite empfohlen: http://www.axel-conrad.de/springer/springer.html.

Da bei dynamischer Programmierung alle Teilprobleme berechnet werden kann eine sehr große Anzahl dieser ebenfalls zum Problem werden. 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

Bei der Iterativen Berechnung spricht man dann, wenn ein schrittweiser Zugriff/Ablauf/Berechnung zum einsatz kommt. Durch die Schrittweise Berechnung werde auch Teilberechnungen/Teilprobleme berechnet die evtl. nicht benötigt werden. Aber es kommt zu keiner Mehrfachberechnung.

Beim Rucksackproblem wird die Tabelle schrittweise ausgerechnet und befüllt, deswegen sprechen wir auch bei der ersten Lösung von der Iterativen Lösung des Rucksackproblems.

Die folgende Formel zeigt erst einmal die rekursive Beschreibung der Lösung.

$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}$

Die Umwandlung aus der rekursiven in eine iterative Berechnung ist nicht so trival wie man evtl. denkt. Denn da müssen die rekursiven aufrufe in zwei verschachtelte for-anweisungen verpackt werden.

Prozedur: gesamtwertIterativ
Zweck: Rucksack Algorithmus zur Berechnung des maximalen Werts
Parameter: int kapazitaet
int-Array zeileAlt
int-Array zeileNeu
FOR z := 1 TO Anzahl der gegenstaende STEP 1 DO
 Kopiere die zeileAlt auf zeileNeu
 gewicht := das Gewicht vom dem aktuellen Gegenstand(z)
 FOR s := 0 TO kapazitaet STEP 1 Do
  wenn s < gewicht dann 
   zeileNeu[s] := zeileAlt[s] //zeileNeu erhält den Wert von zeileAlt an der Postition s
  sonst
   temp := zeileAlt[s-gwicht] + Wert von gegenstaend[z]
   zeileNeu[s] := Max(temp, zeileAlt[s]) //zeileNeu bekommt den max-Wert entweder temp oder den alten
  wenn_ende
 next
next

Ergebnis: zeileNeu[kapazitaet] // letzte Spalte im Array steht der Maximale Wert

Im Abschnitt Iterative Berechnung - Implementation wurde es in Java umgesetzt.

Rückkehr des Rucksackproblems

Das Rucksackproblem wurde zwar in den verschiedenen Kapiteln schon einmal angesprochen, aber wir werden es trotzdem noch einmal kurz erklären. Es ist auch unter den Namen Knapsack problem, Transportproblem oder einfach nur Rucksack. Dabei handelt es sich um ein bekanntes Optimierungsproblem der Kombinatorik.

Der Name Transportproblem ist schon sehr gut gewählt. Das Ziel ist, n-Gegenstände einzupacken/zutransportieren, wobei jeder Gegenstand ein Gewicht/Volumen und einen Wert hat. Jedoch sollen die n-Gegenstände so kombiniert werden, dass der Wert alle eingepackten Gegenstände maximal ist, jedoch darf das Gewicht/Volumen nicht überschritten werden.

Dieser Algorithmus oder dies Optimierungsverfahren findet Anwendung in der Beladung von LKWs, Schiffen - überall dort wo man den maximalen finanziellen Gewinn erwirtschaften will.

Bei der Dynamischen Lösung des Problems sollen nun die Probleme der rekursiven Lösung entfernt werden. Wie schon erwähnt, werden Teilprobleme/Teilberechnungen evtl. doppeltdurchgeführt. Mithilfe der Dynamischen Optimierung/Programmierung tritt dies nun nicht mehr auf. Bevor ein Wert ausgerechnet wird, wird erst einmal geschaut, ob er schon vorhanden ist, wenn ja dann wird dieser genommen, wenn nein dann wird der neue Wert berechnet und dann in die Tabelle eingetragen.

Die Implementation der dynamischen Lösung mit rekursiven ansatz und memoizing ist unter Rekursive Berechnung - mit memoizing umgesetzt wurden.

Dimension der Tabelle

ausführlicher

Wie schon oben erwähnt werden die Daten in einer Tabelle gespeichert.

Am Beispiel des Rucksackproblems hat die Tabelle so viele Zeilen wie Gegenstände+1 und Spalten wie es Kapazität+1.

Implementation

Aufgrund von der eingeschränkten Umgebung, wo wir keine eigenen Klassen nehmen können und es auch keine generischen Datentypen gibt (HashMap<>). Deswegen haben wir Point genommen. Dabei ist der erste Wert das Gewicht und der zweite Werte der Wert ist.

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

public int[] iterativ(int kapazitaet)
    {
        int[] zeileAlt = new int[kapazitaet+1];
        int[] zeileNeu = new int[kapazitaet+1];
        String[] zeileAltG = new String[kapazitaet+1];
        String[] zeileNeuG = new String[kapazitaet+1];
        for(int z = 1; z <= gegenstaende.size();z++)
        {
            System.arraycopy(zeileNeu, 0, zeileAlt, 0, zeileNeu.length);
            System.arraycopy(zeileNeuG, 0, zeileAltG, 0, zeileNeuG.length);
            //zeileAlt = zeileNeu.clone();
            int gewicht = (int)gegenstaende.get(z).getX();
            for(int s = 0; s <= kapazitaet; s++)
            {
                if(s >= gewicht)
                {
                    int temp = zeileAlt[s-gewicht] + (int)gegenstaende.get(z).getY();
                    if(temp>zeileAlt[s])
                    {
                        zeileNeu[s] = temp;
                        if(zeileAltG[s-gewicht] == null)
                        {
                            zeileNeuG[s] = z+"";
                        }                        
                        else
                        {
                            
                            zeileNeuG[s] = zeileAltG[s-gewicht] + ";" + z;
                        }
                    }
                }
            }
        }
       if(zeileNeuG[kapazitaet] != null)
       {
           String[] g = zeileNeuG[kapazitaet].split(";");
           int[] back = new int[g.length];
           for(int i=0; i<g.length; i++)
           {
               back[i] = Integer.parseInt(g[i]);
           }
           return back;
       }
        return null;
    }

<eval>printIterativ(120);</eval>

private void initCanvas(int kapazitaet)
{
        canvas.clear();
        canvas.line(20,0,20,200);
        canvas.line(0,20,1100,20);
        for(int i = 0 ; i <= kapazitaet ; i++)
        {
            canvas.text(30+i*25,15,""+i);
        }
        for(int i = 0 ; i <= kapazitaet ; i++)
        {
            canvas.text(30+i*25,35,"0");
        }
        for(int i = 0 ; i <= gegenstaende.size() ; i++)
        {
            canvas.text(2,20+(i+1)*15,""+i);
        }
}
private void ansichtCanvas(int kapazitaet)
{
        initCanvas(kapazitaet);
        int[] zeileAlt = new int[kapazitaet+1];
        int[] zeileNeu = new int[kapazitaet+1];
        for(int z = 1; z <= gegenstaende.size();z++)
        {
            System.arraycopy(zeileNeu, 0, zeileAlt, 0, zeileNeu.length);
            //zeileAlt = zeileNeu.clone();
            int gewicht = (int)gegenstaende.get(z).getX();
for(int s = 0; s <= kapazitaet; s++)
            {
                if(s < gewicht)
                {
                    zeileNeu[s] = zeileAlt[s];
                    canvas.setColor(255,0,0);
                    canvas.text(30+s*25,5+(z+1)*15,""+zeileAlt[s]);
                    canvas.setColor(0,0,0);
                    canvas.text(30+s*25,20+(z+1)*15,""+zeileNeu[s]);
               //     Thread.sleep(100);
                    canvas.text(30+s*25,5+(z+1)*15,""+zeileAlt[s]);
                }
                else
                {
                    int temp = zeileAlt[s-gewicht] + (int)gegenstaende.get(z).getY();
                    if(temp>zeileAlt[s])
                    {
                        zeileNeu[s] = temp;
                        canvas.setColor(255,0,0);
                        canvas.text(30+s*25,20+(z+1)*15,""+zeileNeu[s]);
                        canvas.text(30+(s-gewicht)*25,5+(z+1)*15,""+zeileAlt[s-gewicht]);
                    //    Thread.sleep(800);
                        canvas.setColor(0,0,0);
                        canvas.text(30+s*25,20+(z+1)*15,""+zeileNeu[s]);
                        canvas.text(30+(s-gewicht)*25,5+(z+1)*15,""+zeileAlt[s-gewicht]);
                    }
                    else
                    {
                        zeileNeu[s] = zeileAlt[s];
                        canvas.setColor(255,0,0);
                        canvas.text(30+s*25,5+(z+1)*15,""+zeileAlt[s]);
                        canvas.setColor(0,0,0);
                        canvas.text(30+s*25,20+(z+1)*15,""+zeileNeu[s]);
                  //      Thread.sleep(350);
                        canvas.text(30+s*25,5+(z+1)*15,""+zeileAlt[s]);
                    }
                }
                
            }
/*
            for(int s = 0; s <= kapazitaet; s++)
            {
                if(s < gewicht)
                {
                    zeileNeu[s] = zeileAlt[s];
                }
                else
                {
                    int temp = zeileAlt[s-gewicht] + (int)gegenstaende.get(z).getY();
                    if(temp>zeileAlt[s])
                    {
                        zeileNeu[s] = temp;
                    }
                    else
                    {
                        zeileNeu[s] = zeileAlt[s];
                    }
                }
                canvas.setColor(255,0,0);
                canvas.text(30+s*25,20+(z+1)*15,""+zeileNeu[s]);
                canvas.text(30+s*25,5+(z+1)*15,""+zeileAlt[s]);
                Thread.sleep(200);
                canvas.setColor(0,0,0);
                canvas.text(30+s*25,20+(z+1)*15,""+zeileNeu[s]);
                canvas.text(30+s*25,5+(z+1)*15,""+zeileAlt[s]);
            }*/
        }
}

Aufgrund von verschiedenen Desktopauflösungen, haben wir uns auf 1024 x egal entschieden und somit wird maximal eine Kapazität von 30 gezeichnet. <eval></eval>

       ansichtCanvas(30);

Aufwandsbetrachtung

siehe S.104 ff

Rekursive Berechnung

ToDo - Markus

ohne memoizing

private int rekursiveAufrufe;

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();
                return java.lang.Math.max(var1,var2);
            }
        }
    }

<eval> System.out.println("Ergebnis rekursiv ohne memoizing: " + gesamtwertRekursiv(120)); System.out.println("Rekursive Aufrufe: " + rekursiveAufrufe); </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();
                return java.lang.Math.max(var1,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;
        }
    }
    private 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: " + gesamtwertRekursivMemo(120)); System.out.println("Rekursive Aufrufe: " + rekursiveAufrufe); System.out.println("Länge der Memoliste: " + getLengthMemoListe()); System.out.println("----------------------"); System.out.println("Ergebnis rekursiv mit memoizing: " + gesamtwertRekursivMemo(120)); System.out.println("Rekursive Aufrufe: " + rekursiveAufrufe); System.out.println("Länge der Memoliste: " + getLengthMemoListe()); </eval>

Fazit

Optimale Teilstruktur

ToDo - Markus

Möchte man ein Problem mithilfe dynamischer Programmierung lösen, wirft sich schnell eine entscheidende Frage auf: "Wie stelle ich die optimale Teilstruktur fest, bzw. existiert diese überhaupt?"

Wie wir uns erinnern, war dies ja die Vorraussetzung dafür, dass ein Problem überhaupt mit dynamischer Programmierung lösbar ist, da die Teilprobleme ihrerseits wieder eine optimale Lösung besitzen müssen. Wir müssen also absichern, dass der Bereich der von uns betrachteten Teilprobleme die von der optimalen Lösung verwendeten einschließt. Wir haben bereits beim Rucksackproblem die optimale Teilstruktur entdeckt, indem wir von der Annahme ausgegangen sind, dass ein optimal gepackter Rucksack aus einem bis dahin optimal gepacktem 'Teil-Rucksack' und einem weiteren hinzugefügten Gegenstand besteht. Diese Annahme lässt sich sehr leicht beweisen. Wenn der 'Teil-Rucksack' vor dem Einpacken des nächsten Gegenstandes G_{i} (der zur optimalen Lösung gehört) nämlich nicht optimal gepackt wäre, würde eine andere Lösung durch hinzufügen desselben Gegenstandes G_{i} eine bessere Lösung ergeben als die optimale. Dies ist ganz klar ein Widerspruch und somit ist unsere vorherige Annahme damit auch bewiesen.

Vorgehensweise beim Aufdecken

So wie beim Aufdecken der optimalen Teilstruktur beim Rucksackproblem, können wir auch bei anderen Problemen einem allgemeinem Muster folgen:

1. Zunächst gilt es zu zeigen, dass ein Problem gelöst wird, indem man eine Wahl trifft, wie das Finden des optimal gepackten 'Teil-Rucksacks'. Nach Treffen dieser Wahl erhält man wiederum eines oder mehrere noch zu lösende Teilprobleme.

2. Weiterhin ist anzunehmen, dass die Wahl, die zu einer optimalen Lösung führt, zu einem gegebenen Problem bekannt ist. Wie diese Wahl getroffen wird, muss noch nicht bekannt sein.

3. Daraufhin ist nun zu bestimmen, welche Teilprobleme sich ergeben, wobei der resultierende Raum der Teilprobleme am bestmöglichsten beschrieben werden muss.

4. Nun ist noch zu zeigen, dass die Teilprobleme, die innerhalb einer optimalen Lösung verwendet werden, selbst optimal sein müssen. Dazu greift man auf ein "Cut & Paste-Verfahren" zurück, bei dem man annimmt, dass keine der Lösungen eines Teilproblems optimal ist und diese Annahme dann zum Widerspruch führt. Um das zu erreichen wird gezeigt, dass man eine bessere Lösung erhalten kann, wenn man die nicht optimale Lösung ausschneidet und die optimale dafür einfügt.

Raum der Teilprobleme charakterisieren

Bei der Charakterisierung des Raumes der Teilprobleme ist es vorteilhaft, diesen zunächst so klein wie möglich zu halten. Später kann man diesen auch noch erweitern, falls dies notwendig ist.

Beim Rucksackproblem bestand der Raum der Teilprobleme aus optimal gepackten 'Teil-Rucksäcken' die eine geringere Kapazität besaßen, als der für die Gesamtlösung betrachtete Rucksack. Da diese Lösung gut funktionierte bestand keine Notwendigkeit den Raum der Teilprobleme weiter zu verallgemeinern.

Wie man an späteren Beispielen aber noch sehen wird, ist es nicht immer so leicht eine optimale Teilstruktur festzulegen. Diese variiert in den verschiedenen Problemgebieten zum Einen in der Anzahl der Teilprobleme die innerhalb der optimalen Lösung des Ausgangsproblems verwendet werden, zum Anderen aber auch in der Zahl der Auswahlmöglichkeiten bei der Entscheidung, welche Teilprobleme in einer optimalen Lösung verwendet werden. Dabei wird der Aufwand zur Lösung eines Problems, durch die Multiplikation dieser beiden Faktoren ermittelt.

Betrachten wir dazu noch einmal das Rucksackproblem, erkennen wir, dass sich dadurch unsere Aufwandsbetrachtung der Iterativen Berechnung bestätigt. Dabei entspricht die Kapazität K des Rucksacks der Anzahl der Teilprobleme und die Anzahl der Gegenstände n den Auswahlmöglichkeiten, die beim befüllen eines Rucksackes mit einer bestimmten Kapazität zu treffen sind. Das führt uns wie bereits bekannt zu einem Aufwand von O(Kn). Dabei ist zu berücksichtigen, dass sich der Aufwand durch rekursive Berechnung mit memoizing verringert, da nur die Teilprobleme berechnet werden, die auch wirklich zur Lösung benötigt werden und Mehrfachberechnungen entfallen.

Ungewichteter einfacher Pfad

Das nachfolgende Beispiel zum ungewichteten einfachen Pfad, soll verdeutlichen, dass es nicht vorteilhaft ist eine optimale Teilstruktur anzunehmen, wenn diese nicht vorhanden ist. Dieses Problem ist nicht zu verwechseln mit dem Rundreiseproblem, bei dem die Pfade eine bestimmte Gewichtung besitzen.

Bild und Vergleich: kürzester und längster 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 memoizing

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 - ?

SVN Zugang für Beispiele (Java, evtl C#/F#/Scheme)

https://norbstgr.dyndns.org:8443/svn/AuK/

Username: Jederauk

Passwort: AuK#Jeder

Ihr habt nur lese Rechte!

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 memoizing

Rundreiseproblem

(Ablaufkoordination von Magnetbändern)

SVN Zugang für Beispiele (Java, evtl C#/F#/Scheme)

Files

Links

Literatur

Suche