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 :)
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.
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.
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.
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)
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”.
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ń.
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ć.
Odpowiedzi:
Autobiografia Richarda Bellmana sugeruje, że wybrał termin „programowanie dynamiczne”, aby celowo rozpraszać uwagę.
(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.
źródło
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.
źródło
Zapamiętywanie jest dość powszechnym wariantem.
źródło
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.
źródło
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)
źródło
Ten dokument ( paywalled doi ) nazywa problemy, które można zaatakować przy użyciu DP, „rozkładalne”.
źródło
Rozmawiałem o tym niedawno z kilkoma kolegami i po gorącej dyskusji wymyśliliśmy tabelaryczne buforowanie połączeń .
źródło
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ń.
źródło
Prawdopodobnie coś, co zawiera tabelę słów i wypełnienie , ponieważ tak się dzieje.
źródło
Widok rekurencyjny lub Horyzont rekurencyjny
źródło
Nazwałbym to „Przekazuj rekursję z zapamiętywaniem”.
źródło