Formulierung allgemeiner dynamischen Programmierproblems

Question

Ich frage mich, ob die objektive Funktion eines allgemeinen dynamischen Programmierproblem kann immer formuliert werden als in dynamische Programmierung auf dem Wiki , wo die Zielfunktion eine Summe von Produkten für die Aktion und Staat in jeder Phase ist? Oder das ist nur ein specical Fall und was ist die allgemeine Formulierung?

---

EDIT:

Mit dem „dynamischen Programmierproblem“, meine ich ein Problem, das durch dynamische Programmiertechnik gelöst werden können. Eine solche Art von Problemen haben die Eigenschaft, optimale Problem und optimale Struktur .

Aber Mietvertrag für mich ist es manchmal nicht einfach, solche Probleme zu erkennen, vielleicht, weil ich nicht geworden sind, diese Art der verbalen Beschreibung. Wenn ich über die Wikiseite für Bellman Gleichung kam, kann ich mathematische Formulierung der Kostenfunktion fühlt irgendwie helfen. Ich vermute, dass die Gesamtkosten / Gewinn-Funktion kann immer als Anhäufung von Kosten / Gewinn aus allen Stufen dargestellt werden? und die Anreicherung kann sonst additive oder multiplitive oder etwas sein?

Wenn ich meine Frage gestellt, merkte ich, dass es richtig ist die dynamische Programmierung in einem Ort mehr zu mathematischer Optimierung orientiert zu diskutieren. Aber es gibt eine ganze Menge Diskussion von Computeralgorithmen in Stackoverflow.com. Also ich habe nicht das Gefühl, unangebracht meine Frage hier entweder fragen.

Answer 1

Das ist nicht, wie ich ein beliebiges Optimierungsproblem zu charakterisieren (oder einen dynamischen Programmier-Algorithmus). Insbesondere der Faktor β ^t sieht aus wie ein Elektrotechnik-Hack, dass Programmierer nicht in der Regel wollen würde. Subtile, wie es scheint, ist es nicht immer offensichtlich ist, was die Funktion F für ein gegebenes Problem ist.

Aber ja, Satz β 1 und jede beliebige Zielfunktion können auf diese Weise formuliert werden. Im Allgemeinen wird die Zielfunktion kann jede Funktion des Anfangszustandes und alle Maßnahmen ergriffen; gegeben eine solche Funktion, ist es einfach, eine Funktion F , um den Stecker in dieser Formel.

zu definieren,

Ob das eine nützliche Sache ist, hängt zu tun oder nicht das Problem, nehme ich an.

Answer 2

in der Informatik dynamische Programmierung bezeichnet den Aufbau eines Algorithmus, der in Bezug auf die rekursiv Splitting es in Teilprobleme, wenn die gleichen Subprobleme viele Male in dieser rekursive Erweiterung erscheinen. Ein einfaches Buch Beispiel können Fibonacci-Zahlen unter Verwendung einer dynamischen Programmierung berechnet werden:

Aus der allgemeinen Wiederholung F (n) = F (n-1) + F (n-2) Sie den folgenden Algorithmus implementieren könnten:

int fibonacci(n):
  if (n < 2): return 1
  else: return fibonacci(n-1) + fibonacci(n-2)

Nun ist dies natürlich überhaupt nicht effizient, weil es eine große Anzahl von rekursiven Aufrufen erzeugt, z.

F(8) = F(7) + F(6) = [F(6) + F(5)] + [F(5) + F(4)] = ... 

So, hier sehen wir bereits, dass Fibonacci (5) berechnet wird zweimal durch die Umsetzung. Die dynamische Programmierung Paradigma ist jetzt auf "memoize" oder "Cache" die Ergebnisse, wie folgt aus:

integer_map store;
int memofibo(n):
  if (n < 2) : return 1
  else if (store.find_key(n)): return store.find_value(n)
  else:
    int f = memofibo(n-1) + memofibo(n-2)
    store.set(n, f)
    return f

gewährleisten Diese Implementierung, dass die rekursive Schritt höchstens einmal ausgeführt wird für jedes Argument Wert von n, so dass es die n-te Fibonacci-Zahl in O berechnet (n log n) Zeit (vorausgesetzt, Standard-O (log n)) Umsetzung des assoziativen Array 'Store'.

So aus der Informatik Perspektive, die Verbindung vorausgesetzt, Sie ist die Operationen / Optimierungsproblem Version der gleichen Idee Forschung (Dividieren Problem in Teilprobleme), aber die Idee hat sich in der Praxis auf diese Rekursion + memoization Muster in der Domäne abstrahiert der allgemeinen Informatik. Ich hoffe, das hilft einige der Wolken zu löschen.

Answer 3

Leute,

Es gibt eine neue (ish) Website, die konzentriert sich auf Operationen Fragen erforschen hier aber das geringe Volumen Verkehr kann nicht sehr schnell werden Sie eine gute Antwort bekommen es.

Soapbox Zeit:

Für diejenigen, die Debatte über egal, was für Stapelüberlauf angemessen ist, bemerken wir, dass ein Algorithmus ein Algorithmus ist unabhängig davon, wer behauptet, es als Teil ihres Feldes. Die Simplex-Methode, Djikstra Methode, Zweig und gebunden, Lagrangerelaxierung sind alle Algorithmen oder Methoden zur Lösung bestimmter Arten von Problemen. Viele von ihnen sind gelehrt und in beiden Bereichen, so dass die Grenze, die zwischen OR und CS ist ziemlich verschwommen in diesem Bereich.

Zum Beispiel (und eine sehr starke Instanz ist) der under Kurs in Algorithmen am MIT allen folgenden umfasst - Randomisierte Competitive Algorithmus, Dynamische Programmierung, Greedy Algorithmen, Minimum Spanning Trees, Kürzeste Wege, Dijkstra-Algorithmus, Bellman-Ford , Lineare Programmierung, Tiefensuche, topologische Sortierung und All-Paare Kürzeste Wege unter anderen Themen. Ich werde in diesem Fall an dem MIT verschieben.

ich wie Stack-Überlauf, da viele Programmierer ein Optimierungsproblem erkennen, wenn sie sie treffen, aber oft sie brauchen nur eine wenig Hilfe bei der Entscheidung, wie das Problem zu formulieren oder auch, was das Problem beim Namen genannt wird.