Jeśli możesz zmienić nazwę programowania dynamicznego…

43

Gdybyś mógł zmienić nazwę programowania dynamicznego, jak byś to nazwał?

— Jack
źródło

1

Powiedziałbym, że programowanie dynamiczne to programowanie dynamiczne. To oddzielna koncepcja od algorytmów. Gdybyś zapytał „algorytmiczne zastosowania programowania dynamicznego”, miałoby to dla mnie większy sens.

— Yoshio Okamoto

1

Oczywiście dp jest dp, ale zarówno programowanie, jak i dynamika oznaczają dziś coś innego, więc kiedy uczę programowania dynamicznego, chciałbym, aby miał inną nazwę.

— Jack

4

Przepraszam, nie byłem wystarczająco jasny. Czy interesuje Cię ogólnie programowanie dynamiczne, w tym zastosowanie w kontroli i planowaniu polityki itp., A nawet stochastyczne programowanie dynamiczne, czy po prostu programowanie dynamiczne jako metoda projektowania algorytmów? Główna publiczność tutaj zna tylko to drugie, ale twoje pytanie jest dość ogólne i obejmuje to pierwsze.

— Yoshio Okamoto,

1

Yoshio, myślę, że powinieneś po prostu wyjaśnić bardziej ogólną koncepcję i różnice w odpowiedzi, ponieważ może to oświecić wielu z nas.

— Raphael

2

Kolejny niezupełnie wymowny pomysł: „rzecz, która daje ci pracę w Google” - na podstawie doświadczeń, jakie mieli moi uczniowie :)

— Suresh Venkat

50

Autobiografia Richarda Bellmana sugeruje, że wybrał termin „programowanie dynamiczne”, aby celowo rozpraszać uwagę.

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 „badania”. Nie używam tego terminu lekko; Używam tego dokładnie. Jego twarz się rozchmurzyłaby, zmieniłaby kolor na czerwony i stałby się gwałtowny, gdyby ludzie używali terminu „badania” w jego obecności. Możesz więc sobie wyobrazić, jak się czuł w związku z terminem „matematyczne”. 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ę mogę wybrać? 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 dynamiczne, wieloetapowe, zmienne w czasie - pomyślałem, zabijmy dwa ptaki jednym kamieniem. Weźmy słowo, które ma absolutnie dokładne znaczenie, mianowicie „dynamiczny”, w klasycznym sensie fizycznym. Ma również bardzo interesującą właściwość jako przymiotnik i nie można używać słowa „dynamiczny” w znaczeniu 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ć.

(Jak wskazują Russell i Norvig w swoim podręczniku sztucznej inteligencji, ta historia musi być twórczym upiększeniem prawdy. Bellman po raz pierwszy użył wyrażenia „programowanie dynamiczne” w 1952 r. , A Charles Erwin Wilson został sekretarzem obrony dopiero w 1953 r. )

W każdym razie oryginalna motywacja Bellmana sugeruje planowanie wieloetapowe , ale przynajmniej dla celów algorytmicznych wolałbym coś w rodzaju oszczędnej rekurencji oddolnej , z mniejszą liczbą sylab.

— Jeffε
źródło

10

Oczywiście, naprawdę chciałbym zmienić nazwę na „Równanie Bellmana” lub, jak nazywają to informatycy, „jakikolwiek nawrót”.

— Jeffε

2

Twoja odpowiedź została wykorzystana tutaj: biostar.stackexchange.com/questions/17954

— Pierre

28

Istnieją dwa ważne aspekty DP: (1) zdefiniowanie podproblemów (tj. Utworzenie „tabeli”, która może być wielowymiarową tablicą indeksowaną może przez liczby całkowite, wierzchołki, podzbiory wierzchołków itp.) Oraz (2) rekurencyjne rozwiązywanie podproblemy. Proponuję „rekurencję tabelaryczną / tabelaryczną” jako nazwę odnoszącą się do obu aspektów.

— Daniel Marks
źródło

6

tabelaryczna rekurencja jest miła w dotyku.

— Suresh Venkat

21

Zapamiętywanie jest dość powszechnym wariantem.

— Suresh Venkat
źródło

8

Zapamiętywanie jest używane, ale nie charakteryzuje dp.

— Jack

20

Dokładnie. Zapamiętywanie jest programowaniem dynamicznym przez przypadek.

— Jeffε

@professor erickson - bardzo dobrze powiedziane. nie mogę przestać się śmiać.

— Akash Kumar

7

Jeśli jednak wybieramy nową nazwę dla DP, użycie memoizacji byłoby do tego odpowiednie. Np. „Odległość edycji można obliczyć w czasie wielokrotnym za pomocą zapamiętywania”.

— Noam

Programowanie dynamiczne to szczególny przypadek zapamiętywania, a także jawne kierowanie przepływem sterowania zamiast przestrzegania naturalnego polecenia oceny zastosowania. Szkoda, że zwykle uczy się tak, jak jest, ponieważ zbyt duży nacisk kładzie się na wypełnienie tabeli zamiast rekurencyjnej specyfikacji. Wydaje się to magiczne.

— Neil Toronto,

8

Aby przejść do podziału i podboju , powiedziałbym, że łączymy i łączymy.

Zwykle używam obu słów, łączę i łączę podczas nauczania / wyjaśniania DP; ale nie używane jawnie łączenie i łączenie. Czasami używałem nakładających się, dzielących i podbijających, aby skontrastować oba paradygmaty.

— V Vinay
źródło

6

Po ostatnim wykładzie na temat programowania dynamicznego w projektowaniu algorytmów poprosiłem studentów o zaproponowanie nowej nazwy tej techniki. Podczas gdy mnie bawiło „Trudne programowanie”, chciałem czegoś, co sprawi, że technika będzie bardziej niezapomniana. Po dyskusji tutaj mogę zaproponować dwa nazwy, jeden dla odgórnego i jeden dla oddolnego:
Multiway-Divide i Memoized-Conquer (alias Divide ^ M & Conquer ^ M) i
Scal wszystkie podproblemy (alias Merge_all)

— Jacek
źródło

1

Nie sądzę, aby stworzenie silnego związku ze zwykłymi działaniami typu dziel i rządź (jak w Mergesort) jest dobrym pomysłem. Tam podproblemy są rozwiązywane niezależnie i łączone są tylko dwa wyniki. W DP sprawdzone podproblemy nie są niezależne i wszystkie kombinacje są sprawdzane. (oba w przybliżeniu). Dlatego uważam, że nazwa powinna podkreślać różnicę, a nie tworzyć poczucie podobieństwa.

— Raphael

@ Rafael, podzielam obawy dotyczące niebezpieczeństw związanych z tworzeniem silnych skojarzeń, ale nie zgadzam się z twoim stwierdzeniem różnic. W DP kluczowe jest, aby podproblemy były „rozwiązywane niezależnie”, nawet jeśli rozwiązania podproblemów są wspólne. Zazwyczaj zwracam uwagę, że gdyby jakaś wyrocznia powiedziała ci właściwy podział, to podział i podbój, ale ponieważ nie mówię po grecku (w przeciwieństwie do mojego doktora), muszę spróbować wszystkich możliwych podziałów.

— Jack

2

Tak, podproblemy są koncepcyjnie niezależne. Jednakże, jak pan zauważył, odnosiłem się do nich, stosując te same częściowe wyniki. To oddziela DP od D&C, ponieważ możliwe jest np. Zrównoleglenie tego ostatniego bez wielokrotnego obliczania podproblemów (lub przekazywania wyników) w przeciwieństwie do tych pierwszych. Twoja analogia jest dobra, ale nie uzasadnia nazwy w tym przypadku, ponieważ znalezienie właściwych podziałów jest istotną częścią problemu. Przypuszczam, że można powiedzieć, że DP jest uogólnieniem D&C opartym na tym rozumowaniu.

— Raphael

@ Rafael, przepraszam, że jestem pedantyczny, ale ponieważ jest to pytanie dotyczące nauczania, chcę, aby pojęcie niezależności od podproblemów było jasne, a samo powiedzenie „koncepcyjnie niezależny” nie jest precyzyjne. Podczas próby podziału tworzone podproblemy mogą nie być zależne. Pozostałe komentarze skupiają się na krokach algorytmów DP; Wolę skupić się najpierw na precyzyjnym zdefiniowaniu problemu do rozwiązania. Moje ulubione przykłady: minimalna triangulacja masy i min wypukły rozkład prostych wielokątów ( cs.unc.edu/~snoeyink/demos/convdecomp/MWTDemo.html )

— Jack

W porządku być zawieszonym. Ale zastanów się nad dydaktycznym znaczeniem wyboru słów: powiedz uczniom, że podproblemy są niezależne, a następnie daj im algorytm, który nie rozdziela ich obliczeń, ale w rzeczywistości opiera się w dużej mierze na obliczeniach „przeplatanych”. Myślę, że to może być bardzo mylące. Dlatego naprawdę musisz oddzielić konceptualną / matematyczną / optymalizacyjną / ... i niezależność obliczeniową w pewnym momencie.

— Raphael

4

Ten dokument ( paywalled doi ) nazywa problemy, które można zaatakować przy użyciu DP, „rozkładalne”.

— Yuval Filmus
źródło

2

Rozmawiałem o tym niedawno z kilkoma kolegami i po gorącej dyskusji wymyśliliśmy tabelaryczne buforowanie połączeń .

— Kevin Wortman
źródło

3

to brzmi jak coś, co robisz w outsourcingu call center;)

— Suresh Venkat

2

Sugerowałbym nazwać Programowanie Indukcyjne - jako coś w rodzaju pomostu od naszych czasów do starych dobrych czasów Eulera, Kepler i in. A może nawet odwrotne programowanie indukcyjne . I tak, dla mnie DP jest silnie związany z Indukcją, w starym dobrym tego słowa znaczeniu. Zapamiętywanie, buforowanie, tabele itp. To tylko elementy techniki, a nie rdzeń podejścia do łamania zabezpieczeń.

— trg787
źródło

moim głównym problemem z DP jest P., więc nie jestem fanem tego pomysłu ..

— Suresh Venkat

1

Prawdopodobnie coś, co zawiera tabelę słów i wypełnienie , ponieważ tak się dzieje.

— Raphael
źródło

7

Bah. Programowanie dynamiczne nie dotyczy tabel ; chodzi o inteligentną rekurencję.

— Jeffε

3

Uważam, że lepiej jest oddzielić dwa aspekty: „Wyodrębnianie struktury rekurencyjnej z problemu i zapisywanie jako rekurencję” (modelowanie) oraz „Rozwiązywanie uzyskanej rekurencji w sposób oddolny” (algorytmy). Wydaje mi się, że programowanie dynamiczne (w algorytmach) odnosi się do obu, i dotyczy to również programowania liniowego, programowania liczb całkowitych, programowania półfinałowego itp.

— Yoshio Okamoto

1

Czasami używane są tabele . Programowanie dynamiczne w drzewach (na przykład: maksymalny niezależny zestaw) zwykle nie używa tabeli [= macierzy] do zapamiętywania powtarzalności; wykorzystuje drzewo, a w niektórych przypadkach drzewo tablic, tablicę drzew lub w niektórych przypadkach kartezjański produkt drzew. Podobnie jest w przypadku programowania dynamicznego za pomocą dagów lub programowania dynamicznego nad rozkładami drzew dla wykresów ograniczonej szerokości.

— Jeffε

1

JeffE, nazwa techniki, która prawie nigdy nie obejmuje wszystkich aplikacji. Weźmy na przykład „diagonalizację”; w zaawansowanych aplikacjach nigdzie nie widać przekątnej (a przynajmniej wyłącznego obszaru działania). Ale i tak nie jestem zbytnio zakochany w „zapełnianiu stolików”, choć myślę, że dla początkujących może to być rozsądna nazwa.

— Raphael

3

Moje 2 centy na ten temat. Programowanie dynamiczne ma dwa różne aspekty projektowania algorytmów. Po pierwsze, należy zrozumieć mechanikę dp jak w: inteligentna rekurencja plus zapamiętywanie prowadzące do szybszego algorytmu. Drugi aspekt polega na tym, jak rozpoznać, że problem może pozwolić na inteligentną rekurencję i ją wymyślić. Oba są ważne do nauczenia. W tym drugim przypadku powszechnym przypadkiem jest dzielenie i podbijanie z ograniczoną interakcją i moim zdaniem warto wyraźnie to podkreślić.

— Chandra Chekuri

1

Widok rekurencyjny lub Horyzont rekurencyjny

— znak
źródło

Leniwy horyzont? Opóźniasz obliczanie wielu wyników, dopóki nie są one potrzebne. DP nie musi być rekurencyjny.

— Chad Brewbaker

0

Nazwałbym to „Przekazuj rekursję z zapamiętywaniem”.

— Benzoes
źródło