Worum geht es bei dynamischer Programmierung?

33

Sorry im Voraus, wenn diese Frage dumm klingt ...

Soweit ich weiß, funktioniert das Erstellen eines Algorithmus mit dynamischer Programmierung folgendermaßen:

  1. Drücken Sie das Problem als wiederkehrende Beziehung aus.
  2. Implementieren Sie die Wiederholungsbeziehung entweder durch Auswendiglernen oder durch einen Bottom-up-Ansatz.

Soweit ich weiß, habe ich alles über dynamische Programmierung gesagt. Ich meine: Dynamische Programmierung gibt weder Werkzeuge / Regeln / Methoden / Theoreme an, um Wiederholungsrelationen auszudrücken, noch um sie in Code umzuwandeln.

Was ist das Besondere an dynamischer Programmierung? Was gibt es dir außer einer vagen Methode, um eine bestimmte Art von Problemen anzugehen?

hey hey
quelle
11
Historisches Faktum (dieser Kommentar hilft Ihnen nicht weiter, aber Bellman ist eigentlich ein guter Hinweis, wenn Sie die Theorie der dynamischen Programmierung vertiefen möchten): Als Bellman mit dem, was heute als dynamische Programmierung bekannt ist, auf den Plan kam, nannte er die Idee "dynamische Programmierung" "weil rein theoretische arbeit zu diesem zeitpunkt nicht mit seinem arbeitgeber flog, brauchte er etwas lebhafteres, das nicht abwertend eingesetzt werden konnte .
G. Bach
3
Soweit ich weiß, erwähnen Sie genau diese beiden Punkte. Es wird besonders, wenn es eine exponentielle Explosion aufgrund überlappender Teilprobleme vermeidet. Das ist alles. Übrigens, mein Professor bevorzugt das "algorithmische Paradigma" gegenüber der "vagen Methode".
Hendrik Jan
"Dynamisches Programmieren" scheint hauptsächlich ein Schlagwort zu sein (das ist seitdem nicht mehr aktuell). Das heißt natürlich nicht, dass es nicht nützlich ist.
user253751
3
Keine Antwort wert, aber für mich ist dynamisches Programmieren definitiv "das, was Sie verwenden, wenn Sie versuchen, ein Problem rekursiv zu lösen, aber am Ende verschwenden Sie Zeit damit, dieselben Teilprobleme immer wieder zu wiederholen."
Hobbs
@hobbs: Genau, aber die Fähigkeit besteht darin , diese anfängliche Art der Zeitverschwendung zu finden;)
j_random_hacker

Antworten:

27

Dynamische Programmierung gibt Ihnen die Möglichkeit, über das Algorithmus-Design nachzudenken. Das ist oft sehr hilfreich.

Memo- und Bottom-Up-Methoden bieten eine Regel / Methode, mit der Sie Wiederholungsrelationen in Code umwandeln können. Memoization ist eine relativ einfache Idee, aber die besten Ideen sind oft!

Die dynamische Programmierung gibt Ihnen eine strukturierte Möglichkeit, über die Laufzeit Ihres Algorithmus nachzudenken. Die Laufzeit wird im Wesentlichen durch zwei Zahlen bestimmt: die Anzahl der zu lösenden Teilprobleme und die Zeit, die zur Lösung jedes Teilproblems benötigt wird. Dies bietet eine bequeme und einfache Möglichkeit, über das Algorithmus-Design-Problem nachzudenken. Wenn Sie eine Kandidaten - Wiederholungsbeziehung haben, können Sie sich diese ansehen und sehr schnell ein Bild von der Laufzeit machen (z. B. können Sie oft sehr schnell feststellen, wie viele Unterprobleme es geben wird, was eine Untergrenze für das ist Laufzeit; wenn es exponentiell viele zu lösende Teilprobleme gibt, ist die Wiederholung wahrscheinlich kein guter Ansatz). Dies hilft Ihnen auch dabei, mögliche Zerlegungen von Teilproblemen auszuschließen. Zum Beispiel, wenn wir eine Zeichenfolge haben , wobei ein Unterproblem durch ein Präfix S [ 1 .. i ] oder ein Suffix S [ j] definiert wird . . n ] oder Teilzeichenfolge S [ i . . j ] mag vernünftig sein (die Anzahl der Teilprobleme ist in n polynomisch), aber die Definition eines Teilproblems durch eine Teilsequenz von S ist wahrscheinlich kein guter Ansatz (die Anzahl der Teilprobleme ist in n exponentiell). Auf diese Weise können Sie den "Suchbereich" für mögliche Wiederholungen beschneiden.S[1..n]S[1..i]S[j..n]S[i..j]nSn

Dynamische Programmierung bietet Ihnen einen strukturierten Ansatz für die Suche nach Kandidaten-Wiederholungsrelationen. Empirisch ist dieser Ansatz oft effektiv. Insbesondere gibt es einige Heuristiken / allgemeine Muster, die Sie je nach Art der Eingabe für allgemeine Methoden zum Definieren von Unterproblemen erkennen können. Zum Beispiel:

  • Wenn die Eingabe eine positive ganze Zahl , besteht ein möglicher Weg zum Definieren eines Unterproblems darin, n durch eine kleinere ganze Zahl n 'zu ersetzen (st 0 n 'n ).nnn0nn

  • Wenn es sich bei der Eingabe um eine Zeichenfolge , gibt es folgende Möglichkeiten, ein Unterproblem zu definieren: Ersetzen Sie S [ 1 .. n ] durch ein Präfix S [ 1 .. i ] ; Ersetzen Sie S [ 1 .. n ] durch ein Suffix S [ j . . n ] ; Ersetzen Sie S [ 1 .. n ] durch eine Teilzeichenfolge S [ i . . j ]S[1..n]S[1..n]S[1..i]S[1..n]S[j..n]S[1..n]S[i..j]. (Hier wird das Teilproblem durch die Wahl von .)i,j

  • Wenn es sich bei der Eingabe um eine Liste handelt , verfahren Sie genauso wie bei einer Zeichenfolge.

  • Wenn die Eingabe ein Baum , besteht ein möglicher Weg zum Definieren eines Unterproblems darin, T durch einen beliebigen Teilbaum von T zu ersetzen (dh einen Knoten x auszuwählen und T durch den Teilbaum zu ersetzen, der bei x verwurzelt ist ; das Unterproblem wird durch die Wahl von x bestimmt ).TTTxTxx

  • Wenn die Eingabe ein Paar , überprüfen Sie rekursiv den Typ von x und den Typ von y , um einen Weg zu finden, für jedes ein Unterproblem auszuwählen. Mit anderen Worten, ein möglicher Weg, ein Unterproblem zu definieren, besteht darin, ( x , y ) durch ( x ' , y ' ) zu ersetzen , wobei x ' ein Unterproblem für x ist und y ' ein Unterproblem für y ist . (Sie können auch Teilprobleme der Form ( x , y(x,y)xy(x,y)(x,y)xxyy Oder ( x ' , y ) .)(x,y)(x,y)

Und so weiter. Dies gibt Ihnen eine sehr nützliche Heuristik: Wenn Sie sich nur die Typensignatur der Methode ansehen, können Sie eine Liste von Kandidaten für die Definition von Teilproblemen erstellen. Mit anderen Worten, wenn Sie sich nur die Problemstellung ansehen - nur die Arten der Eingaben -, können Sie eine Handvoll von Kandidaten für die Definition eines Teilproblems finden.

Das ist oft sehr hilfreich. Es sagt Ihnen nichts über die Wiederholungsrelation aus, aber wenn Sie eine bestimmte Wahl zur Definition des Unterproblems haben, ist es oft nicht allzu schwierig, eine entsprechende Wiederholungsrelation zu erarbeiten. Daher wird das Design eines dynamischen Programmieralgorithmus häufig zu einer strukturierten Erfahrung. Sie notieren sich auf dem Altpapier eine Liste der möglichen Möglichkeiten, um Unterprobleme zu definieren (unter Verwendung der obigen Heuristik). Anschließend versuchen Sie, für jeden Kandidaten eine Wiederholungsrelation aufzuschreiben und ihre Laufzeit durch Zählen der Anzahl der Teilprobleme und der pro Teilproblem aufgewendeten Zeit zu bewerten. Nachdem Sie jeden Kandidaten ausprobiert haben, behalten Sie den besten, den Sie finden konnten. Das Bereitstellen einer Struktur für den Algorithmusentwurf ist eine wichtige Hilfe, da der Algorithmusentwurf ansonsten einschüchternd sein kann (da '

DW
quelle
Sie bestätigen also, dass die dynamische Programmierung keine konkreten "Prozeduren" enthält, die befolgt werden müssen. Es ist nur "eine Art zu denken", wie Sie sagten. Beachten Sie, dass ich nicht behaupte, dass DP nutzlos ist (im Gegenteil!), Ich versuche nur zu verstehen, ob es etwas gibt, das mir fehlt, oder ob ich einfach mehr üben sollte.
hey hey
@heyhey, na ja ... und nein. Weitere Informationen finden Sie in meiner überarbeiteten Antwort. Es ist keine Wunderwaffe, aber es bietet einige halb-konkrete Vorgehensweisen, die oft hilfreich sind (die nicht garantiert funktionieren, sich aber oft als hilfreich erweisen).
DW
Danke vielmals! Durch das Üben mache ich mich immer mehr mit einigen der von Ihnen beschriebenen "semikonkreten Verfahren" vertraut.
hey hey
"Wenn es exponentiell viele Teilprobleme gibt, die Sie lösen müssen, ist die Wiederholung wahrscheinlich kein guter Ansatz." Für viele Probleme ist kein polynomieller Zeitalgorithmus bekannt. Warum sollte dies ein Kriterium für die Verwendung von DP sein?
Chiel ten Brinke
@Chiel, es ist kein Kriterium für die Verwendung von DP. Wenn Sie ein Problem haben, bei dem Sie mit einem Exponential-Zeit-Algorithmus zufrieden wären, können Sie diese besondere Bemerkung in Klammern ignorieren. Es ist nur ein Beispiel, um zu versuchen, den allgemeinen Punkt zu veranschaulichen, den ich machte - nicht etwas, das Sie zu ernst nehmen oder als feste Regel interpretieren sollten.
DW
9

Ihr Verständnis von dynamischer Programmierung ist korrekt ( afaik ) und Ihre Frage ist berechtigt.

Ich denke, der zusätzliche Gestaltungsspielraum, den wir durch die Art von Wiederholungen erhalten, die wir "dynamische Programmierung" nennen, kann am besten im Vergleich zu anderen Schemata rekursiver Ansätze gesehen werden.

Angenommen, unsere Eingaben sind Arrays um die Konzepte hervorzuheben.A[1..n]

  1. Induktiver Ansatz

    Hier besteht die Idee darin, Ihr Problem zu verkleinern, die kleinere Version zu lösen und eine Lösung für die ursprüngliche abzuleiten. Schematisch,

    f(A)=g(f(A[1..nc]),A)

    mit die Funktion / den Algorithmus, der die Lösung übersetzt.g

    Beispiel: Superstars in linearer Zeit finden

  2. Teilen & Erobern

    Teilen Sie die Eingabe in mehrere kleinere Teile auf, lösen Sie das Problem für jedes und kombinieren Sie sie. Schematisch (für zwei Teile),

    f(A)=g(f(A[1..c]),f(A[c+1..n]),A)

    Beispiele: Merge- / Quicksort, Kürzeste paarweise Distanz in der Ebene

  3. Dynamische Programmierung

    Betrachten Sie alle Möglichkeiten, das Problem in kleinere Probleme zu unterteilen, und wählen Sie die besten aus. Schematisch (für zwei Teile),

    f(A)=best{g(f(A[1..c]),f(A[c+1..n]))|1cn1}

    Beispiele: Distanz bearbeiten, Änderungsproblem

    best

In gewisser Weise wissen Sie immer weniger, wie statisch von oben nach unten vorgegangen wird, und müssen immer mehr Entscheidungen dynamisch treffen.

Die Lehre aus dem Erlernen der dynamischen Programmierung ist, dass es in Ordnung ist , alle möglichen Partitionen zu testen (nun, es ist für die Korrektheit erforderlich), da die Verwendung von Memoization immer noch effizient sein kann.

Raphael
quelle
"Pruned Dynamic Programming" (sofern zutreffend) beweist, dass das Ausprobieren aller Möglichkeiten NICHT für die Richtigkeit erforderlich ist.
Ben Voigt
Natürlich. Ich blieb absichtlich vage darüber, was "alle Arten der Aufteilung" bedeutet; du willst natürlich so viele wie möglich ausschließen! (Selbst wenn Sie alle Arten der Partitionierung ausprobieren, erhalten Sie keine Brute Force, da Sie immer nur Kombinationen optimaler Lösungen für Teilprobleme untersuchen, wohingegen Brute Force alle Kombinationen aller Lösungen untersuchen würde .)
Raphael
Lassen Sie uns diese Diskussion im Chat fortsetzen .
Apass.Jack
5

Mit der dynamischen Programmierung können Sie Speicher gegen Rechenzeit tauschen. Betrachten Sie das klassische Beispiel Fibonacci.

Fib(n)=Fib(n1)+Fib(n2)O(2n)Fib()n

Fib(2)Fib(3)Fib(4)O(n)

mm

Kittsil
quelle
1
Sie sprechen nur über den Memo-Teil, der den Punkt der Frage verfehlt.
Raphael
1
"Dynamische Programmierung ermöglicht es Ihnen, Speicher gegen Rechenzeit auszutauschen", hörte ich während des Studiums nicht und es ist eine großartige Möglichkeit, dieses Thema zu betrachten. Dies ist eine intuitive Antwort mit einem kurzen Beispiel.
trueshot
@trueshot: Abgesehen davon, dass die dynamische Programmierung (und insbesondere die "beschnittene dynamische Programmierung") manchmal sowohl den Zeit- als auch den Platzbedarf reduzieren kann.
Ben Voigt
@Ben Ich habe nicht gesagt, dass es ein Eins-zu-Eins-Handel ist. Sie können auch einen Wiederholungsbaum beschneiden. Ich gehe davon aus, dass ich die Frage beantwortet habe: "Was bringt uns DP?" Es bringt uns schnellere Algorithmen, indem wir Raum gegen Zeit tauschen. Ich bin damit einverstanden, dass die akzeptierte Antwort gründlicher ist, aber dies gilt auch.
Kittsil
2

Hier ist eine andere Art der Formulierung, die Ihnen dynamische Programmierung bietet. Dynamisches Programmieren kollabiert eine exponentielle Anzahl von Kandidatenlösungen in eine polynomielle Anzahl von Äquivalenzklassen, so dass die Kandidatenlösungen in jeder Klasse in gewisser Weise nicht unterscheidbar sind.

kAn2nO(n2)f(i,)i

f(i,)=j<i such thatA[j]<A[i]f(j,1)
f(i,1)=1 for all i=1n

O(n2k)

jnalanko
quelle