Dynamische Programmierung

Irgendwann im Leben, sei es im Studium oder in der aktuellen Lektüre, trifft man auf ein Konzept, dass sich “dynamische Programmierung” nennt. Wikipedia und andere Quellen erklären dieses Konzept mit nicht trivialen Sätzen und bringen die Geschichte dahinter noch mit ein. Da ist dann etwas von Physik(ern) und einer Bellman-Optimierung zu lesen. Das kann alles sehr verwirrend sein. Dabei kann dieses Prinzip der dynamischen Programmierung auch in 10 Minuten verständlich erklärt werden:

Das Konzept “dynamische Programmierung”:

Die “dynamische Programmierung” wird auf  Probleme angewendet, die sich in kleine Teilprobleme aufspalten lassen. Das bedeutet die Lösung des großen Problems setzt sich aus den kleinen Lösungen unserer Teilprobleme zusammen:

Ein großes und komplexes Problem in kleine Teile auf zu spalten hat den Vorteil, dass diese kleinen Teile leichter zu lösen sind. Durch die vielen Teil-Lösungen kommen wir einfacher zur gesamten Lösung und somit zum Ziel. Wir sparen also beim Computer Rechenzeit. Die CPU wird entlastet. Im Gegenzug müssen wir diese Teil-Lösungen aber auch speichern um diese dann später zusammenfügen zu können. Der RAM (Arbeitspeicher) wird also belastet.

Dynamische Programmierung entlastet die CPU und belastet den RAM.

Hier ein Beispiel dieses Prinzips aus dem Alltag (es hat in diesem Fall nichts mit der Programmierung an sich zu tun):

Wir wollen unseren Kühlschrank wieder mit Nahrungsmitteln auffüllen. Würden wir nicht das Prinzip der “dynamischen Programmierung” kennen, so müssten wir jedes Nahrungsmittel (Milch, Brot, usw.) selbst herstellen. Also die Kuh melken, das Weizen ernten und weiterverarbeiten, usw. Das Kostet Zeit. Bei einem Computer wäre dies die Rechenzeit (betrifft die CPU). Wenn wir alles gemolken und geerntet haben, haben wir nach gefühlten zwei Monaten unseren Kühlschrank wieder gefüllt. :-)

Aber das geht doch sicherlich schneller?! Ja, wir kennen das: Der Supermarkt. Dieser Markt ist ein Ort, wo wir alle unsere Nahrungsmittel finden. Dort kaufen wir sie alle ein (führen sie zusammen) und stellen sie in unseren Kühlschrank. Voilà, unsere Teil-Lösungen haben unser Problem (leerer Kühlschrank) leicht gelöst. Der zeitliche Aufwand dürfte bei höchstens zwei Stunden liegen. Aber es wurde mehr Platz verbraucht. Denn die Nahrungsmittel wurden im Supermarkt “zwischengelagert”.

Dies war ein sehr abstraktes Beispiel. Das Standard-Beispiel in der Programmierung ist die Fibonacci-Folge. Im weiteren Verlauf dieses Artikels wird angenommen, dass dem Leser die Fibonacci-Folge bekannt ist. ;-)

In Java kann die Fibonacci-Folge so implementiert werden:

public int fibonacci(int var){

    if(var <= 0){
        return 0;
    }

    if(var == 1){
        return 1;
    }

    return fibonacci(var-1) + fibonacci(var-2);
}

 

Dies ist eine einfache Umsetzung der Definition für diese Folge. Es gibt noch keine dynamische Programmierung. Wir haben hier die mächtige und zumeist teure Rekursion. Ihr könnt versuchen zu zählen wie oft die CPU eine Addition für fibonacci(100) durchführen muss. Oder lasst euren Rechner fibonacci(1000000) ausrechnen. Erwartet aber bitte kein Ergebnis in diesem Jahr oder Jahrhundert… (kein Scherz!)

Viele werden jetzt (da ja dynamische Programmierung bekannt ist) ein “A-Ha”-Erlebnis haben. Richtig. fibonacci(5) ist doch fibonacci(4) plus fibonacci(3). Das bedeutet, wenn ich ein mal fibonacci(4) und die davor ausgerechnet habe, dann muss ich mir diese Ergebnisse ja nur merken und dann brauch ich keine Rekursion und die Teil-Ergebnisse (Teil-Lösungen) kann ich ganz einfach zusammenführen.

Genau. Wir merken uns einfach die vorherigen Ergebnisse. “Merken” bedeutet, wir speichern diese im Arbeitsspeicher (RAM) ab. Unsere CPU muss nicht mehr so viel Rechnen und wir bekommen ganz schnell ein End-Ergebnis.

Hier mal die Fibonacci-Folge mit dem Prinzip der dynamischen Programmierung:

public int fibonacci(int var){

    //Hier werden alle Teil-Ergebnisse gespeichert (Belastung des RAMs)
    int array[] = new int[var];

    for(int i=0;i<var;i++){
        if(i==0){
            array[i] = 0;
        }else if(i==1){
            array[i] = 1;
        }else{
            //Hier führen wir zwei Teil-Ergebnisse zu einem neuen Ergebnis zusammen!
            array[i] = array[i-1] + array[i-2];
        }
    }

    //Das End-Ergebnis
    return array(var-1) + array(var-2);
}

 

Der Code hat sich jetzt leicht verändert. Wir haben keine Rekursion mehr, dafür aber ein Array, welches alle Teil-Ergebnisse enthält. Wir speichern zwar mehr Daten im RAM, dafür ist unsere Berechnung aber um einiges schneller. Wenn wir jetzt fibonacci(1000000) ausrechnen wollen ist der Rechner so schnell fertig… Wir könnten nicht mal bis 3 zählen. (Vorausgesetzt wir haben genügend RAM ;-) ) Glückwunsch. Das Prinzip der dynamischen Programmierung wurde erfolgreich umgesetzt.

Wie Viele bemerkt haben ist dieses Konzept sehr effizient. Die Fibonacci-Folge ist nur ein kleines Beispiel. Bei anderen Problemen kann sich diese Art von Programmierung deutlich positiver auswirken. Bei mobilen Geräten (Smartphone etc.) bedeutet eine Belastung der CPU auch eine Belastung des Akkus. Und das möchte niemand! :-)

Damit wäre die “dynamische Programmierung” erklärt. Ich hoffe dieser Artikel konnte dem Ein oder Anderen helfen. Für Alle, die noch Zeit haben: Im folgenden Abschnitt erkläre ich, wie die Verwendung des RAMs verbessert werden kann. Für das Verständnis der dynamischen Programmierung ist dieser Abschnitt nicht relevant.

Optimierung: Verwendung des RAMs

Die CPU konnte jetzt erfolgreich entlastet werden. Aber manchmal haben wir nur einen begrenzten Arbeitsspeicher zur Verfügung. Um so wenig wie möglich und nur so viel wie nötig Speicher zu belegen ist es wichtig zu wissen, welche Teil-Ergebnisse wir uns eigentlich merken müssen. Bei der Fibonacci-Folge, zum Beispiel, genügen eigentlich zwei Ergebnisse: fibonacci(var-1) und fibonacci(var-2).

Ich sage euch nicht warum, ich zeige euch aber dazu den Quellcode (Java). Diesen Schritt sollte jeder selbst erarbeitet haben um das Prinzip der Optimierung zu verstehen.

public int fibonacci(int var){

    int varEven = 0;
    int varOdd = 1;

    //Abbruchbedingungen
    if(var <= 0){
        return 0;
    }

    if(var == 1){
        return 1;
    }

    //Schleife, welche die beiden Variablen aktualisiert
    for(int i=2;i<var;i++){
        if(i%2==0){
            varEven = varEven + varOdd;
        }

        if(i%2==1){
            varOdd = varEven + varOdd;
        }
    }

    //Das End-Ergebnis
    return varEven + varOdd;
}

 

Diese Optimierung ist nicht ganz trivial, aber immer noch relativ einfach. Das liegt aber hauptsächlich am Fibonacci-Beispiel. In viel komplexeren Problemen kann eine Optimierung der Verwendung des RAMs viel Zeit und Gehirnschmalz verbrauchen.

Als zeitlichen Vergleich könnt ihr die Fibonacci-Folge nehmen. Wie lange habt/hättet ihr gebraucht um diese zu Programmieren (mit Rekursion) ? Zwei Minuten? Und mit dynamischer Programmierung? 4 Minuten? Und jetzt werdet euch klar, wie lange ihr für die Optimierung der RAM-Verwendung gebraucht habt (Und sie zu verstehen). Übertragt mal diese Zeiten auf große Projekte (Probleme). Es ist jetzt zwar nur eine kleine Spinnerei aber ihr dürft ruhig Annehmen, dass diese Optimierung geistig sehr Aufwändig ist.

Wir sind nun am wirklichen Ende dieses Artikels. Anmerkungen und Kommentare sind gern gesehen. :-)