Co jest „dynamiczne” w programowaniu dynamicznym?

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.

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.

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ę.

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”.

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)