Wenn Sie dynamische Programmierung umbenennen könnten ...

43

Wenn Sie dynamische Programmierung umbenennen könnten, wie würden Sie es nennen?

ds.algorithms soft-question terminology ho.history-overview Jack
quelle
1
Ich würde sagen, dass dynamisches Programmieren dynamisches Programmieren ist. Das ist ein anderes Konzept als Algorithmen. Wenn Sie nach "algorithmischen Anwendungen der dynamischen Programmierung" fragen würden, wäre das für mich sinnvoller.
Yoshio Okamoto
1
Natürlich ist dp dp, aber Programmierung und Dynamik bedeuten heute etwas anderes. Wenn ich dynamische Programmierung unterrichte, wünschte ich mir, sie hätte einen anderen Namen.
Jack
4
Entschuldigung, ich war nicht klar genug. Interessieren Sie sich allgemein für dynamisches Programmieren, einschließlich des Einsatzes in der Steuerungs- und Strategieplanung usw., und sogar für stochastisches dynamisches Programmieren oder nur für dynamisches Programmieren als Methode für das Algorithmusdesign? Das Hauptpublikum hier würde nur das letztere kennen, aber Ihre Frage ist recht allgemein und schließt das erstere ein.
Yoshio Okamoto
1
Yoshio, ich denke, Sie sollten nur das allgemeinere Konzept bzw. die Unterschiede in einer Antwort erklären, da dies viele von uns aufklären könnte.
Raphael
2
Eine andere, nicht ganz ironische Idee: "Die Sache, die dir Jobs bei Google einbringt" - basierend auf den Erfahrungen, die meine Schüler gemacht haben :)
Suresh Venkat

Antworten:

50

Richard Bellmans Autobiographie legt nahe, dass er den Begriff „dynamische Programmierung“ absichtlich als ablenkend bezeichnet.

Die 1950er Jahre waren keine guten Jahre für die mathematische Forschung. Wir hatten in Washington einen sehr interessanten Herrn 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 und er würde gewalttätig werden, wenn die Leute in seiner Gegenwart den Begriff "Forschung" verwenden würden. Sie können sich vorstellen, wie er sich über den Begriff "mathematisch" fühlte. Die RAND Corporation war bei der Air Force angestellt, und die Air Force hatte im Wesentlichen Wilson als Chef. Daher hatte ich das Gefühl, dass ich etwas tun musste, um Wilson und die Luftwaffe vor der Tatsache zu schützen, dass ich wirklich Mathematik innerhalb der RAND Corporation praktizierte.

Welchen Titel, welchen Namen könnte ich wählen? In erster Linie war ich daran interessiert, zu planen, Entscheidungen zu treffen, nachzudenken. Aber Planung ist aus verschiedenen Gründen kein gutes Wort. Ich habe mich daher für das Wort "Programmierung" entschieden. Ich wollte die Vorstellung vermitteln, dass dies dynamisch, mehrstufig und zeitlich variabel ist - ich dachte, wir schlagen zwei Fliegen mit einer Klappe. Nehmen wir ein Wort, das eine absolut präzise Bedeutung hat, nämlich "dynamisch" im klassischen physikalischen Sinne. Es hat auch eine sehr interessante Eigenschaft als Adjektiv, und das ist es unmöglich, das Wort "dynamisch" im abwertenden Sinne zu verwenden. Denken Sie an eine Kombination, die möglicherweise eine abwertende Bedeutung hat. Es ist unmöglich. Daher fand ich, dass „dynamisches Programmieren“ ein guter Name ist. Das konnte nicht einmal ein Kongressabgeordneter beanstanden.

(Wie Russell und Norvig in ihrem AI-Lehrbuch hervorheben, muss diese Geschichte jedoch eine kreative Verschönerung der Wahrheit sein. Bellman verwendete den Begriff "dynamische Programmierung" erstmals 1952 , und Charles Erwin Wilson wurde erst 1953 Verteidigungsminister. )

Wie auch immer, Bellmans ursprüngliche Motivation deutet auf eine mehrstufige Planung hin , aber zumindest für algorithmische Zwecke würde ich eine sparsame Bottom-Up-Rekursion bevorzugen , nur mit weniger Silben.

Jeffε
quelle
10
Natürlich, was ich würde wirklich wie zu tun ist , Umbenennungs „Bellman-Gleichung“ oder als Informatiker es nennen, „jede Wiederholung zu löschen“.
Jeffs
2
Ihre Antwort wurde hier verwendet: biostar.stackexchange.com/questions/17954
Pierre
28

Es gibt zwei wichtige Aspekte von DP: (1) Definieren der Unterprobleme (dh Erstellen einer "Tabelle", die ein mehrdimensionales Array sein kann, das möglicherweise durch Ganzzahlen, Scheitelpunkte, Untergruppen von Scheitelpunkten usw. indiziert ist) und (2) rekursives Lösen der Unterprobleme. Ich schlage "tabellarische / tabellarische Rekursion" als einen Namen vor, der sich auf beide Aspekte bezieht.

Daniel Marx
quelle
6
Die tabellarische Rekursion fühlt sich gut an.
Suresh Venkat
21

Memoization ist eine ziemlich häufige Variante.

Suresh Venkat
quelle
8
Memoization wird verwendet, charakterisiert aber nicht dp.
Jack
20
Genau. Memoisierung ist eine zufällige dynamische Programmierung.
Jeffs
@ Professor Erickson - sehr gut gesagt. ich kann nicht aufhören zu lachen.
Akash Kumar
7
Wenn wir jedoch einen neuen Namen für DP wählen können, ist die Verwendung von Memoization durchaus geeignet. ZB "Die Bearbeitungsentfernung kann mithilfe von Memoization in Mehrfachzeit berechnet werden".
Noam
Dynamisches Programmieren ist ein Sonderfall des Merkens und der expliziten Steuerung des Steuerungsflusses, anstatt der natürlichen Reihenfolge der anwendbaren Bewertung zu folgen. Es ist eine Schande, dass es in der Regel so gelehrt wird, wie es ist, da zu viel Wert auf das Ausfüllen einer Tabelle gelegt wird, anstatt auf die rekursive Angabe. Es wirkt magisch.
Neil Toronto
8

Zum Teilen und Erobern würde ich Spleißen und Kombinieren sagen .

Ich benutze normalerweise beide Wörter, spleiße und kombiniere, während ich DP unterrichte / erkläre; wird aber nicht explizit verwendet. Manchmal habe ich überlappendes Teilen und Erobern verwendet, um die beiden Paradigmen gegenüberzustellen.

V Vinay
quelle
6

Nach meinem letzten Vortrag über dynamisches Programmieren im Algorithmus-Design hatte ich die Schüler gebeten, einen neuen Namen für diese Technik vorzuschlagen. Während ich von "Tough Programming" amüsiert war, wollte ich etwas, das die Technik unvergesslicher macht. Nach der Diskussion hier kann ich zwei Namen vorschlagen, einen für Top-Down und einen für Bottom-Up:
Multiway-Divide und Memoized-Conquer (auch bekannt als Divide ^ M & Conquer ^ M) und
alle Unterprobleme zusammenführen (auch bekannt als Merge_all).

Jack
quelle
1
Ich halte es nicht für eine gute Idee, eine starke Assoziation mit dem üblichen Teilen und Erobern (wie in Mergesort) herzustellen. Dort werden Teilprobleme selbständig gelöst und nur zwei Ergebnisse zusammengeführt. In DP sind die überprüften Teilprobleme nicht unabhängig und alle Kombinationen werden überprüft. (beide in groben Zügen). Daher denke ich, dass ein Name den Unterschied hervorheben sollte, anstatt ein Gefühl der Ähnlichkeit zu erzeugen.
Raphael
@Raphael, ich teile die Besorgnis über die Gefahren einer starken Assoziation, bin aber mit Ihrer Aussage über die Unterschiede nicht einverstanden. In DP ist es entscheidend , dass die Teilprobleme sind „unabhängig gelöst“ , obwohl Lösungen subsubproblems gemeinsam genutzt werden. Ich weise normalerweise darauf hin, dass, wenn ein Orakel Ihnen die richtige Unterteilung sagt, es sich um Teilen und Erobern handelt, aber da ich kein Griechisch spreche (im Gegensatz zu meinem PhD-Berater), muss ich alle möglichen Unterteilungen ausprobieren.
Jack
2
Ja, Teilprobleme sind konzeptionell unabhängig. Ich habe sie jedoch mit denselben Teilergebnissen in Beziehung gesetzt, wie Sie hervorheben. Dies trennt DP von D & C, da es z. B. möglich ist, Letzteres zu parallelisieren, ohne Teilprobleme mehrfach zu berechnen (oder die Ergebnisse zu kommunizieren), im Gegensatz zu Ersterem. Ihre Analogie ist nett, garantiert aber in diesem Fall nicht den Namen, da das Finden der richtigen Unterteilungen ein wesentlicher Teil des Problems ist. Ich nehme an, Sie könnten sagen, dass DP eine Verallgemeinerung von D & C ist, die auf dieser Argumentation basiert.
Raphael
@Raphael, tut mir leid, dass ich pedantisch bin, aber da es sich um eine Frage des Unterrichts handelt, möchte ich, dass der Begriff der Unabhängigkeit von Teilproblemen klar ist und dass es nicht präzise ist, nur "konzeptuell unabhängig" zu sagen. Wenn Sie eine Unterteilung versuchen, weisen die von Ihnen erzeugten Unterprobleme möglicherweise keine Abhängigkeiten auf. Ihre anderen Kommentare konzentrieren sich auf die Schritte von DP-Algorithmen. Ich konzentriere mich lieber zuerst darauf, das zu lösende Problem genau zu definieren. Meine Lieblingsbeispiele: Minimale Gewichtstriangulation und minimale konvexe Zerlegung einfacher Polygone ( cs.unc.edu/~snoeyink/demos/convdecomp/MWTDemo.html )
Jack,
Pendant zu sein ist in Ordnung. Aber bedenken Sie den didaktischen Einfluss der Wortwahl: Sie sagen den Schülern, dass Teilprobleme unabhängig sind, und geben ihnen dann einen Algorithmus, der ihre Berechnung nicht trennt, sondern in der Tat stark von "verschachtelten" Berechnungen abhängt. Ich denke, das kann sehr verwirrend sein. Daher muss man irgendwann wirklich zwischen konzeptioneller / mathematischer / Optimierung / ... und rechnerischer Unabhängigkeit trennen.
Raphael
4

Dieses Papier ( paywalled doi ) nennt Probleme , die mit DP angegriffen werden können, "zerlegbar".

Yuval Filmus
quelle
2

Ich habe dies kürzlich mit einigen Kollegen besprochen, und nach einer hitzigen Diskussion kamen wir auf tabellarisches Caching von Anrufen .

Kevin Wortman
quelle
3
das klingt wie etwas, das Sie in einem ausgelagerten Callcenter tun;)
Suresh Venkat
2

Ich würde den Namen Inductive Programming vorschlagen - als eine Art Brückenschlag aus unserer Zeit bis zu den guten alten Zeiten von Euler, Kepler et al. Oder vielleicht sogar Reverse Inductive Programming . Und ja, für mich ist DP stark mit der Induktion verbunden, im alten guten Sinne des Begriffs. Memoisierung, Zwischenspeichern, Tabellen usw. sind nur Elemente der Technik und nicht der Kern des Ansatzes, Dinge zu knacken.

trg787
quelle
Mein Hauptproblem mit DP ist der P. Also bin ich kein Fan dieser Idee ..
Suresh Venkat
1

Wahrscheinlich etwas, das die Wörter table und fill enthält , da dies passiert.

Raphael
quelle
7
Bah. Bei der dynamischen Programmierung geht es nicht um Tabellen . es geht um kluge Rekursion.
Jeffs
3
Ich halte es für besser, zwei Aspekte zu trennen: "Eine rekursive Struktur aus dem Problem extrahieren und als Wiederholung aufschreiben" (Modellierung) und "Die erhaltene Wiederholung von unten nach oben lösen" (Algorithmen). Ich bin der Meinung, dass dynamisches Programmieren (in Algorithmen) sich auf beides bezieht, und dies gilt auch für lineares Programmieren, ganzzahliges Programmieren, semidefinites Programmieren usw.
Yoshio Okamoto,
1
Tabellen werden manchmal verwendet. Dynamische Programmierung über Bäume (zum Beispiel: Maximum Independent Set) verwendet normalerweise keine Tabelle [= Array], um sich die Wiederholung zu merken. Es wird ein Baum oder in einigen Fällen ein Baum von Arrays oder ein Array von Bäumen oder in einigen Fällen ein kartesisches Produkt von Bäumen verwendet. Ähnliches gilt für die dynamische Programmierung über Tage oder die dynamische Programmierung über Baumzerlegungen für Graphen mit begrenzter Baumbreite.
Jeffs
1
JeffE, ein Name für eine Technik, deckt kaum alle Anwendungen ab. Nehmen wir zum Beispiel "Diagonalisierung"; In fortgeschrittenen Anwendungen ist keine Diagonale in Sicht (oder zumindest kein exklusiver Aktionsbereich). Aber ich bin sowieso nicht zu sehr in "Tischfüllung" verliebt, obwohl ich denke, dass dies ein vernünftiger Name für Anfänger sein könnte.
Raphael
3
Meine 2 Cent zu diesem Thema. Dynamische Programmierung hat zwei unterschiedliche Aspekte beim Entwurf von Algorithmen. Zunächst ist die Mechanik von dp wie folgt zu verstehen: Intelligente Rekursion plus Merken, was zu einem schnelleren Algorithmus führt. Der zweite Aspekt ist, wie man erkennt, dass ein Problem eine intelligente Rekursion zulässt und darauf kommt. Beides ist wichtig zu lehren. Für letztere ist es üblich, mit begrenzter Interaktion zu teilen und zu erobern, und meiner Ansicht nach lohnt es sich, dies ausdrücklich hervorzuheben.
Chandra Chekuri
1

Rekursive Ansicht oder rekursiver Horizont

Kennzeichen
quelle
Fauler Horizont? Sie verzögern die Berechnung vieler Ergebnisse, bis sie benötigt werden. DP muss nicht rekursiv sein.
Chad Brewbaker
0

Ich würde es "Rekursion mit Memoisierung weiterleiten" nennen.

Benjamin
quelle