Was ist „dynamisch“ an dynamischer Programmierung?

Einer meiner Senioren hatte ein Vorstellungsgespräch und wurde gefragt, warum es dynamisch heißt. Er konnte nicht antworten und nachdem er aufgegeben hatte, sagte der Interviewer, dass es nichts Dynamisches gibt, es heißt einfach so. Das fällt mir schwer zu glauben.

Bezieht es sich auf die Tatsache, dass die Teilprobleme zur Laufzeit gelöst und zum Erreichen des Endziels verwendet werden? Wie eine dynamische Speicherzuweisung, die zur Laufzeit erfolgt?

[ANTWORTEN]

Ich hätte diesen Wiki-Artikel lesen sollen, bevor ich die Frage gestellt habe, sorry.

Ich habe immer verstanden, dass Algorithmen mit dynamischer Programmierung den Problemraum " dynamisch " zu bearbeiten schienen, bis das Problem mit einem gierigen Algorithmus gelöst werden konnte.

Bei dem Checkerboard- Problem bearbeitet der dynamische Programmieralgorithmus beispielsweise die gesamte Karte, während sie durchlaufen wird, und schließlich kann schließlich ein gieriger Algorithmus verwendet werden (ähnlich mit dem Dijkstra-Algorithmus für kürzeste Wege usw.).

Ich bin mir nicht sicher, ob dies auf jedes dynamische Programmierproblem verallgemeinert wird.

Eigentlich ist der Name "dynamische Programmierung" nichts Besonderes; Bei der Technik selbst geht es nur darum, die Rekursion intelligent abzuwickeln. Sehen Sie sich diese Frage an und sehen Sie sich die Antwort von @Jeffe an, in der berichtet wird, dass Belman diesen Namen gewählt hat, um absichtlich abzulenken.

Hier gibt es eine interessante Geschichte. Bellman war Pionier dieses Paradigmas. Aber das war eigentlich mathematische Forschung. Zu seiner Zeit war der damalige Verteidigungsminister paranoid gegenüber den Worten Forschung und Mathematik (verrückter Typ, richtig!). Bellman hatte Angst, dass der Secretart wütend auf seine Arbeit sein und ihn schließlich in Schwierigkeiten bringen würde. Um die Dinge ein wenig zu verwischen, nannte er es Dynamische Programmierung , aber es ist nichts "Dynamisches" daran.

Richard Bellman nannte es Dynamische Programmierung in den Worten in Bellman

Ich habe das Herbstquartal (1950) bei RAND verbracht. Meine erste Aufgabe war es, einen Namen für mehrstufige Entscheidungsprozesse zu finden.

Eine interessante Frage ist: Woher kommt der Name, dynamische Programmierung? Die 1950er Jahre waren keine guten Jahre für die mathematische Forschung. Wir hatten einen sehr interessanten Herrn in Washington namens Wilson. Er war Verteidigungsminister und hatte tatsächlich eine pathologische Angst und einen Hass gegen das Wort Forschung. Ich benutze den Begriff nicht leichtfertig; Ich benutze es genau. Sein Gesicht würde durchdringen, er würde rot werden und er würde gewalttätig werden, wenn die Leute den Begriff Forschung in seiner Gegenwart verwenden würden. Sie können sich vorstellen, wie er sich dann über den Begriff mathematisch fühlte. Die RAND Corporation war bei der Luftwaffe angestellt, und die Luftwaffe hatte im Wesentlichen Wilson als Chef. Daher hatte ich das Gefühl, ich musste etwas tun, um Wilson und die Luftwaffe vor der Tatsache zu schützen, dass ich wirklich Mathematik innerhalb der RAND Corporation mache. Welcher Titel, welcher Name, könnte ich wählen? Erstens interessierte ich mich für Planung, Entscheidungsfindung, Denken. Aber Planung ist aus verschiedenen Gründen kein gutes Wort. Ich entschied mich daher, das Wort "Programmierung" zu verwenden. Ich wollte auf die Idee kommen, dass dies dynamisch, mehrstufig und zeitlich variabel ist. Ich dachte, lass uns zwei Fliegen mit einer Klappe schlagen. Nehmen wir ein Wort, das eine absolut genaue Bedeutung hat, nämlich dynamisch im klassischen physikalischen Sinne. Es hat auch eine sehr interessante Eigenschaft als Adjektiv und dass es unmöglich ist, das Wort Dynamik in einem abwertenden Sinne zu verwenden. Versuchen Sie, an eine Kombination zu denken, die ihm möglicherweise eine abwertende Bedeutung verleiht. Es ist unmöglich. Daher hielt ich dynamische Programmierung für einen guten Namen. Es war etwas, gegen das nicht einmal ein Kongressabgeordneter Einwände erheben konnte.

Quelle: Auge des Hurrikans, Richard Bellman (Autobiographie)