Co jest „dynamiczne” w programowaniu dynamicznym?

9

Jeden z moich seniorów odbył rozmowę kwalifikacyjną i zapytano go, dlaczego nazywa się to dynamicznym. Nie mógł odpowiedzieć, a po tym, jak zrezygnował z wywiadu, powiedział, że nie ma w tym nic dynamicznego, po prostu tak to się nazywa. Trudno mi w to uwierzyć.

Czy odnosi się to do faktu, że podproblemy są rozwiązywane w czasie wykonywania i wykorzystywane do osiągnięcia ostatecznego celu? Jak dynamiczny przydział pamięci, który ma miejsce w czasie wykonywania?

[ODPOWIEDŹ]

Przepraszam, powinienem przeczytać ten artykuł wiki przed zadaniem pytania.

terminology dynamic-programming

— kintoki
źródło

2

Krótka odpowiedź, to tylko nazwa. Nie musi mieć dosłownego znaczenia.

— Yuval Filmus,

4

Prawdopodobnie typowe implementacje DP (wypełnianie tabel) są tak statyczne, jak tylko algorytm może uzyskać.

— Raphael

1

Zawsze intuicyjnie rozumiałem, że oznaczało to, że algorytmy wykorzystujące programowanie dynamiczne wydawały się „ dynamicznie ” edytować przestrzeń problemu, dopóki problem nie mógł zostać rozwiązany za pomocą chciwego algorytmu.

Na przykład, w przypadku problemu Szachownica , algorytm programowania dynamicznego edytuje całą płytkę podczas jej przechodzenia, a następnie można zastosować chciwy algorytm (podobnie z algorytmem najkrótszej ścieżki Dijkstry itp.).

Nie jestem jednak pewien, czy uogólnia to każdy problem z programowaniem dynamicznym.

— Realz Slaw
źródło

9

Właściwie w nazwie „programowanie dynamiczne” nie ma nic specjalnego; sama technika polega na inteligentnie rozwijającej się rekurencji. Zobacz to pytanie i spójrz na odpowiedź @Jeffe, w której odnotowano, że Belman wybrał tę nazwę, aby celowo odwracać uwagę.

— Massimo Cafaro
źródło

3

Chociaż teoretycznie może to odpowiedzieć na pytanie, lepiej byłoby zawrzeć tutaj istotne części odpowiedzi i podać odnośnik.

— John Dvorak,

Ktoś z Wikipedii wydaje się nie zgadzać, właśnie to odkryłem - jest dynamiczny, ponieważ wartości w tabeli są wypełniane przez algorytm oparty na innych wartościach w tabeli, a programuje w sensie ustawiania rzeczy w tabeli, takich jak sposób, w jaki telewizja programowanie dotyczy tego, kiedy transmitować to, co pokazuje - na Wikibooks

— kintoki,

@akki: istnieją przykłady programowania dynamicznego, w których stół nie jest wcale potrzebny ...

— Massimo Cafaro,

1

@akki: na przykład obliczenie liczb Fibonacciego metodą oddolną wymaga tylko stałej

O (1)

$O(1)$ spacja w celu zapisania liczb Fibonacciego wymaganych do obliczenia następnego w szeregu; obliczanie najdłuższej wspólnej sekwencji dwóch łańcuchów długości

m

$m$ i

n

$n$ można to zrobić za pomocą

O (m i n (m, n))

$O(min(m,n))$ spacja zamiast pełnego

m n

$m n$ stół i tak dalej.

— Massimo Cafaro,

2

@akki: to jest dokładnie to, o czym mówię, gdy mówię, że DP polega na inteligentnym rozwinięciu rekurencji! Ale sama nazwa była bezcelowa i pozostaje bezcelowa.

— Massimo Cafaro,

6

Jest tu ciekawa historia. Bellman był pionierem tego paradygmatu. Ale tak naprawdę były to badania matematyczne. W swoim czasie ówczesny sekretarz obrony był paranoikiem słów Research and Math (wariat, prawda!). Bellman bał się, że sekretnik będzie wściekły na swoją pracę i ostatecznie wpędzi go w kłopoty. Żeby trochę rozmyć, nazwał to Programowaniem dynamicznym , jednak nie ma w tym nic „dynamicznego”.

— Subhayan
źródło

1

Źródło tego? Wydaje się, że to naprawdę interesująca historia.

— jmite

Na marginesie: wydaje się niejasne, kto opracował programowanie dynamiczne po raz pierwszy. Bellman powinien zostać uznany za udowodnienie, że każda implementacja programowania dynamicznego, gdy jest optymalna, przestrzega tak zwanych równań Bellmana-Forda. Niestety wydaje się, że wiele osób łatwo wierzy, że to sprawia, że Bellman jest głównym badaczem oryginalnego pomysłu.

— Carlos Linares López

@jmite Przeczytałem to w jakimś miejscu (prawdopodobnie na jakimś blogu) .. postaram się podać źródło ...

— Subhayan

@jmite Historię można znaleźć w notatce wykładowej Jefa z Wykładu 5: Programowanie dynamiczne, a także na wiki: programowanie dynamiczne .

— hengxin

3

Richard Bellman nazwał to Programowaniem dynamicznym słowami w Bellman

Spędziłem dzielnicę jesień (1950 r.) W RAND. Moim pierwszym zadaniem było znalezienie nazwy dla wieloetapowych procesów decyzyjnych.

Interesujące pytanie brzmi: skąd wzięła się nazwa, programowanie dynamiczne? Lata pięćdziesiąte to nie były dobre lata na badania matematyczne. Mieliśmy w Waszyngtonie bardzo interesującego dżentelmena o imieniu Wilson. Był Sekretarzem Obrony i rzeczywiście miał patologiczny strach i nienawiść do słowa „badanie”. Nie używam tego terminu lekko; Używam tego dokładnie. Jego twarz się rozchmurzyłaby, zrobiłaby się czerwona i stałby się gwałtowny, gdyby ludzie używali terminu badanie w jego obecności. Możecie sobie wyobrazić, jak się wtedy czuł na temat matematyki. Korporacja RAND była zatrudniona przez siły powietrzne, a siły powietrzne miały w zasadzie Wilsona. Dlatego czułem, że muszę zrobić coś, aby ochronić Wilsona i Siły Powietrzne przed faktem, że naprawdę zajmowałem się matematyką w korporacji RAND. Jaki tytuł, jakie imię, czy moge wybrac Po pierwsze byłem zainteresowany planowaniem, podejmowaniem decyzji, myśleniem. Ale planowanie nie jest dobrym słowem z różnych powodów. Dlatego postanowiłem użyć słowa „programowanie”. Chciałem się przekonać, że to było dynamiczne, to było wieloetapowe, to zmieniało się w czasie. Pomyślałem: zabijmy dwa ptaki jednym kamieniem. Weźmy słowo, które ma absolutnie dokładne znaczenie, mianowicie dynamiczne, w klasycznym sensie fizycznym. Ma również bardzo interesującą właściwość jako przymiotnik i że nie można używać słowa dynamiczny w sensie pejoratywnym. Spróbuj wymyślić jakąś kombinację, która prawdopodobnie nada mu pejoratywne znaczenie. To niemożliwe. Dlatego pomyślałem, że programowanie dynamiczne to dobre imię. Było to coś, czemu nawet kongresmen nie mógł się sprzeciwić.

Źródło: Eye of the Hurricane, Richard Bellman (Autobiography)

— Anuj Gupta
źródło