Dynamische Programmierung

[rb4k]

Hallo liebes Forum,

ich bin noch sehr unerfahren mit Python und muss für eine Uni-Hausarbeit ein dynamisches Programm programmieren. Das Programm dient dazu einen Ertragswert zu ermitteln, der Abhängig ist von bestimmten Entscheidungen. Die Entscheidungen sind voneinander abhängig, was damit das Dynamische Programm ausmacht.

Ich versuche es vereinfacht zu formulieren: Ich muss irgendwie einen Entscheidungsbaum generieren, der t Schritte hat. In jedem Schritt kann ein bestimmter Systemzustand erreicht werden. Gestartet wird zB im Zustand t = 3 und es wird abwärts gezählt. Der Startzustand hat 2 unterschiedliche Ressourcen mit einer jeweiligen Kapazität von 2. Das bedeutet der Startzustand hat einen Wert W([2, 2], 3). Dieser Zustand kann verlassen werden zu den darauffolgenden Zuständen zum Zeitpunkt t = 2. Diese lauten dann W([2, 2], 2), W([2, 1], 2), W([2, 0], 2), W([1, 2], 2), W([0, 2], 2), W([1, 1], 2) und W([0, 0], 2). Abhängig welche Ressource reduziert wird… Jetzt kann das Programm für jeden Zustand aus t = 2 natürlich wieder in einen nachfolgenden Zustand in t = 1 überführt werden. Damit wird ein recht komplexer Entscheidungsbaum bis zur letzten Periode t = 0 aufgebaut. (Ich hoffe das war verständlich…)

Wie kann ich jetzt diesen Entscheidungsbaum (Graphen) mittels Python, Numpy, SciPy, PyDecode oder ähnlich aufbauen?

Ich bin etwas frustriert, da ich echt nicht mehr weiter komme… Ich hoffe Ihr könnt mir einen kleinen Schups in die richtige Richtung geben.

Liebe Grüße, Rb4k

[MagBen]

Male das Programm auf. Baue den Entscheidungsbaum aus Ovalen auf, die Du mit Strichen verbindest. Jeder Typ von Oval ist eine Klasse, jedes Oval ist ein Objekt und jeder Strich ist eine Referenz von einem Objekt auf ein anderes Objekt. Das ist Dein Objektmodell.
Jetzt wird etwas mit diesem Objektmodell getan, das stellst Du im Bild mit Pfeilen dar, für diese Pfeile programmierst Du Methoden (OO-Sprech für Funktionen).

[BlackJack]

@MagBen: Das klingt jetzt nach objektorientierter Analyse und nicht nach dem was der OP gefragt hat, denn das hilft ihm ja nicht wirklich dabei das Problem mit dynamischer Programmierung umzusetzen.

@rb4k: Du hast ja anscheinend schon einen rekursiven Ansatz. Bei dynamischer Programmierung geht man nicht rekursiv bis zum Rekursionsanker zurück sondern baut sich eine Wertetabelle oder Datenstruktur vom Rekursionsanker ausgehend aus auf, bis man an dem Punkt angekommen ist bei dem man mit einer rekursiven Lösung aus starten würde.

[rb4k]

Hallo nochmal,

also aufzeichnen und rechnen kann ich es (Also die grundsätzliche mathematische Vorgehensweise aufm Blatt Papier). Daher weiß ich auch was prinzipiell mit einer Wertetabelle gemeint ist. Leider verstehe ich nur nicht, wie ich es programmieren kann.

Gibt es irgendwo ein gutes Tutorium zum Thema? Irgendwelche Literatur mit dieser Problemstellung?

Mein aktuelles Vorgehens ist es die möglichen Zustände des Systems als Numpy Array abzubilden, sprich np.array([[[2, 2],2], [[2, 1],1], [[2, 0], 0], [[1, 2],2], [[0, 1],1], [[0, 2], 0]]). Dabei besteht ein jeweiliger Vektor aus einem Kapazitätsvektor und der Zeitangabe… Sprich: [Kapazität1, Kapazität2],Zeitpunkt].

Sobald ich es geschafft habe alle möglichen Zustände zu beschreiben, muss ich dann die Zustände verbinden. Wie ich das hinbekomme? Keine Ahnung… Ein Systemzustand zum Zeitpunkt 0 ist 0 und dementsprechend kann ich diese Zustände verwenden um das Dynamische Programm rückwärts zu lösen.

Oder ist es doch ratsamer die mathematische Gleichung in Python darzustellen?

Die Formel lautet:

Wert zum Zeitpunkt t mit Kapazität c = Summe aller Wahrscheinlichkeiten der Anfrage nach einem Produkt j * max( Wert zum Zeitpunkt t+1 mit Kapazität c *oder* Wert zum Zeitpunkt t+1 mit Kapazität c - Kapazitätsverbrauch a) + Wahrscheinlichkeiten, dass keine Anfrage eintrifft.

Ich hoffe ich konnte die Problemstellung ausreichend abstrahieren…

[rb4k]

So sieht die Formel aus, aber der Code funktioniert so selbstverständlich nicht…

Code: Alles auswählen

def test_value(products, capacities, consumtions, revenues, probs, times):
    for i in products:
        for t in times:
                reject = test_value(products, capacities, consumtions, revenues, probs, times[t+1])
                accept = test_value(products, capacities-consumtions[i], consumtions, revenues, probs, times[t+1])
                reject + sum(probs[i][t] * (revenues[i] - reject + accept) for i in products)
    return

Es gibt irgendwann einen Zeitpunkt times[n], an dem reject und accept den Wert = 0 annehmen und von diesem Punkt müsste dann der Entscheidungsbaum gelöst werden. Also sprich V([0, 0], 0)=0 und dieser wird in V([0,0], 1) eingesetzt (V(Kapazitäten, Zeit)).

Man erkennt schnell, dass mir das handwerkliche Geschick bei der Programmierung fehlt. Der Code müsste eig Werte abspeichern und diese in „Nachbarrechnungen“ einsetzen, diese ebenfalls berechnen und dann ebenfalls abspeichern.

Ich danke für jede Hilfe!!!

[rb4k]

Hey,

hab es selbst geschafft.

Hab es durch eine rekursive Implementierung geschafft. Iterativ leider nicht. Hab die einzeln aufgerufenen Funktionen durch mehrere If-Befehle (Grenzbedingungen) beschränkt, was hoffentlich nicht allzu sehr der Performance schadet. Konnte auch eine Memofunktion einarbeiten, sodass keine doppelten Rechenschritte getätigt werden.

Ich denke mal der Code reicht aus für die weitere Ausarbeitung meiner Masterarbeit. Danke an alle Leser und für die Kommentare.