Na czym polega programowanie dynamiczne?

33

Z góry przepraszam, jeśli to pytanie brzmi głupio ...

O ile wiem, budowanie algorytmu przy użyciu programowania dynamicznego działa w ten sposób:

wyrazić problem jako relację nawrotu;
wdrożyć relację powtarzalności albo poprzez zapamiętywanie, albo poprzez podejście oddolne.

O ile wiem, powiedziałem wszystko o programowaniu dynamicznym. Mam na myśli: programowanie dynamiczne nie daje narzędzi / reguł / metod / twierdzeń do wyrażania relacji powtarzalności ani do przekształcania ich w kod.

Więc co jest specjalnego w programowaniu dynamicznym? Co to daje, oprócz niejasnej metody podejścia do pewnego rodzaju problemów?

algorithms dynamic-programming algorithm-design

— Hej hej
źródło

11

Fakt historyczny (ten komentarz ci nie pomoże, ale Bellman jest naprawdę dobrym tropem, jeśli chcesz obciążyć teorię dynamicznym programowaniem): kiedy Bellman wymyślił coś, co jest obecnie znane jako programowanie dynamiczne, nazwał ten pomysł „programowaniem dynamicznym „ponieważ praca czysto teoretyczna nie latała wówczas ze swoim pracodawcą, dlatego potrzebował czegoś bardziej modnego, czego nie można było wykorzystać w sposób pejoratywny .

— G. Bach,

3

O ile wiem, dokładnie o tych dwóch punktach wspominasz. Staje się wyjątkowy, gdy unika eksplozyjnej eksplozji z powodu nakładających się podproblemów. To wszystko. Ach, tak przy okazji, mój profesor woli „paradygmat algorytmiczny” niż „niejasną metodę”.

— Hendrik Jan

„Programowanie dynamiczne” wydaje się być głównie modnym hasłem (od tamtej pory straciło na popularności). Nie oznacza to oczywiście, że nie jest to przydatne.

— user253751

3

Nie warta odpowiedzi, ale dla mnie programowanie dynamiczne to zdecydowanie „rzecz, której używasz, gdy próbujesz rozwiązać problem rekurencyjnie, ale w końcu marnujesz czas na powtarzanie tych samych podproblemów w kółko”.

— hobbs

@hobbs: Dokładnie, ale umiejętność polega na znalezieniu tego początkowego sposobu marnowania czasu;)

— j_random_hacker

27

Programowanie dynamiczne pozwala myśleć o projektowaniu algorytmów. Jest to często bardzo pomocne.

Metody zapamiętywania i oddolne dają regułę / metodę przekształcania relacji powtarzalności w kod. Zapamiętywanie jest stosunkowo prostym pomysłem, ale często są to najlepsze pomysły!

Programowanie dynamiczne daje uporządkowany sposób myślenia o czasie działania algorytmu. Czas działania zależy zasadniczo od dwóch liczb: liczby podproblemów, które należy rozwiązać, oraz czasu potrzebnego na rozwiązanie każdego podproblemu. Zapewnia to wygodny i łatwy sposób myślenia o problemie z algorytmem. Gdy masz relację powtarzalności kandydata, możesz na nią spojrzeć i bardzo szybko zorientować się, jaki może być czas działania (na przykład często możesz bardzo szybko powiedzieć, ile będzie podproblemów, co jest dolną granicą czas działania; jeśli istnieje wykładniczo wiele podproblemów, które musisz rozwiązać, to prawdopodobnie nie będzie to dobre podejście). Pomaga to również wykluczyć rozkład kandydatów na podproblemy. Na przykład, jeśli mamy ciąg $S[1..n]$ , Wyznaczając subproblem prefiksem lub przyrostek lub podciągu może być rozsądne (liczba podproblemów jest wielomian ), ale obejmującym subproblem przez podciąg nie może być podejście dobry (liczba podproblemów wykładniczo w ). Pozwala to przycinać „przestrzeń wyszukiwania” możliwych powtórzeń. $S[1..i]$ $S[j..n]$ $S[i..j]$ $n$ $S$ $n$

Programowanie dynamiczne zapewnia ustrukturyzowane podejście do wyszukiwania relacji powtarzalności kandydatów. Pod względem empirycznym takie podejście jest często skuteczne. W szczególności istnieją pewne heurystyki / wspólne wzorce, które można rozpoznać dla typowych sposobów definiowania podproblemów, w zależności od rodzaju danych wejściowych. Na przykład:

Jeśli wejście jest dodatnią liczbą całkowitą , jednym z kandydujących sposobów zdefiniowania podproblemu jest zastąpienie mniejszą liczbą całkowitą (st ). $n$ $n$ $n'$ $0 \le n' \le n$
Jeśli dane wejściowe są ciągiem , niektóre potencjalne sposoby zdefiniowania podproblemu obejmują: zamień na prefiks ; zastąp sufiksem ; zamień na podciąg . (Tutaj podproblem zależy od wyboru .) $S[1..n]$ $S[1..n]$ $S[1..i]$ $S[1..n]$ $S[j..n]$ $S[1..n]$ $S[i..j]$ $i,j$
Jeśli dane wejściowe to lista , zrób to samo, co dla łańcucha.
Jeśli dane wejściowe to drzewo , jednym z kandydujących sposobów zdefiniowania podproblemu jest zastąpienie dowolnym poddrzewem (tj. Wybranie węzła i zastąpienie poddrzewem zrootowanym na ; podproblem zależy od wyboru ). $T$ $T$ $T$ $x$ $T$ $x$ $x$
Jeśli dane wejściowe to para , następnie rekurencyjnie spójrz na typ i typ aby zidentyfikować sposób wyboru podproblemu dla każdego. Innymi słowy, jednym z kandydujących sposobów zdefiniowania podproblemu jest zastąpienie przez gdzie jest podproblemem dla a jest podproblemem dla . (Można również rozważyć podproblemy postaci lub .) $(x,y)$ $x$ $y$ $(x,y)$ $(x',y')$ $x'$ $x$ $y'$ $y$ $(x,y')$ $(x',y)$

I tak dalej. Daje to bardzo przydatną heurystykę: po prostu patrząc na podpis typu metody, możesz wymyślić listę potencjalnych sposobów definiowania podproblemów. Innymi słowy, po prostu patrząc na opis problemu - patrząc tylko na rodzaje danych wejściowych - możesz wymyślić kilka kandydujących sposobów zdefiniowania podproblemu.

Jest to często bardzo pomocne. Nie mówi ci, jaka jest relacja powtarzalności, ale kiedy masz konkretny wybór, jak zdefiniować podproblem, często nie jest trudno wypracować odpowiednią relację powtarzalności. Często zmienia więc dynamiczny algorytm programowania w ustrukturyzowane środowisko. Na kartce papieru zapisujesz listę potencjalnych sposobów definiowania podproblemów (korzystając z powyższej heurystyki). Następnie dla każdego kandydata próbujesz zapisać relację powtarzalności i ocenić jego czas działania, licząc liczbę podproblemów i czas spędzony na podproblem. Po wypróbowaniu każdego kandydata zachowujesz najlepszego, jaki udało ci się znaleźć. Zapewnienie pewnej struktury w procesie projektowania algorytmu jest dużą pomocą, ponieważ w przeciwnym razie projektowanie algorytmu może być zastraszające (tam „

— DW
źródło

Potwierdzasz więc, że programowanie dynamiczne nie zapewnia konkretnych „procedur”, których należy przestrzegać. To tylko „sposób myślenia”, jak powiedziałeś. Zauważ, że nie twierdzę, że DP jest bezużyteczny (wręcz przeciwnie!), Po prostu próbuję zrozumieć, czy jest coś, czego mi brakuje lub czy powinienem po prostu więcej ćwiczyć.

— hej hej,

@ heyhey, cóż, tak ... i nie. Zobacz moją poprawioną odpowiedź, aby uzyskać więcej informacji. To nie jest srebrna kula, ale zapewnia pewne pół-konkretne procedury, które są często pomocne (nie gwarantuje się ich działania, ale często okazują się pomocne).

— DW

Wielkie dzięki! Ćwicząc, coraz lepiej poznaję niektóre z tych „pół-konkretnych procedur”, które opisujesz.

— hej hej,

„jeśli istnieje wykładniczo wiele podproblemów, które musisz rozwiązać, to prawdopodobnie nie będzie to dobre podejście”. W przypadku wielu problemów nie ma znanego algorytmu wielomianowego czasu. Dlaczego powinno to być kryterium korzystania z DP?

— Chiel ten Brinke

@ Chiel, to nie jest kryterium korzystania z DP. Jeśli masz problem z algorytmami czasu wykładniczego, możesz zignorować tę konkretną uwagę w nawiasie. To tylko przykład, aby spróbować zilustrować ogólny punkt, który podniosłem - nie jest to coś, co powinieneś brać zbyt poważnie lub interpretować jako twardą i szybką zasadę.

— DW

9

Twoje rozumienie programowania dynamicznego jest poprawne ( afaik ), a twoje pytanie jest uzasadnione.

Myślę, że dodatkową przestrzeń projektową, jaką otrzymujemy z rodzaju nawrotów, które nazywamy „programowaniem dynamicznym”, najlepiej można zobaczyć w porównaniu z innymi schematami podejść rekurencyjnych.

Udawajmy, że nasze dane wejściowe to tablice w celu podkreślenia pojęć. $A[1..n]$

Podejście indukcyjne

Tutaj pomysł polega na zmniejszeniu problemu, rozwiązaniu mniejszej wersji i znalezieniu rozwiązania dla oryginalnego. Schematycznie

$\qquad f(A) = g\bigl( f(A[1..n-c]), A \bigr)$

z funkcja / algorytm, który przekłada się roztwór. $g$

Przykład: Znajdowanie gwiazd w czasie liniowym
Dziel i rządź

Podziel dane wejściowe na kilka mniejszych części, rozwiąż problem dla każdej z nich i połącz. Schematycznie (na dwie części),

$\qquad f(A) = g\bigl(f(A[1..c]), f(A[c+1..n]), A\bigr)$ .

Przykłady: Merge- / Quicksort, Najkrótsza odległość parami w płaszczyźnie
Programowanie dynamiczne

Rozważ wszystkie sposoby podziału problemu na mniejsze i wybierz najlepsze. Schematycznie (na dwie części),

$\qquad f(A) = \operatorname{best} \Bigl\{ g\bigl(f(A[1..c]), f(A[c+1..n])\bigr) \Bigm| 1 \leq c \leq n-1 \Bigr\}$ .

Przykłady: edycja odległości, problem z wprowadzaniem zmian

Ważna uwaga: programowanie dynamiczne nie jest brutalną siłą ! Zastosowanie na każdym etapie znacznie zmniejsza przestrzeń wyszukiwania. $\operatorname{best}$

W pewnym sensie wiesz, że coraz mniej statycznie przechodzisz od góry do dołu i musisz podejmować coraz więcej decyzji dynamicznie.

Lekcja płynąca z uczenia się o programowaniu dynamicznym jest taka, że wypróbowanie wszystkich możliwych partycjonowania jest w porządku (cóż, jest to wymagane do poprawności), ponieważ nadal może być wydajne przy użyciu zapamiętywania.

— Raphael
źródło

„Przycinanie programowania dynamicznego” (gdy ma zastosowanie) dowodzi, że wypróbowanie wszystkich możliwości NIE jest wymagane do poprawności.

— Ben Voigt,

@BenVoigt Oczywiście. Celowo pozostawałem niejasny co do tego, co oznaczają „wszystkie sposoby podziału”; oczywiście chcesz wykluczyć jak najwięcej! (Jednak nawet jeśli spróbujesz wszystkich sposobów partycjonowania, nie otrzymasz brutalnej siły, ponieważ zawsze badasz kombinacje optymalnych rozwiązań podproblemów, podczas gdy brutalna siła bada wszystkie kombinacje wszystkich rozwiązań.)

— Raphael

Daj nam kontynuować tę dyskusję w czacie .

— Apass.Jack

5

Programowanie dynamiczne pozwala wymieniać pamięć na czas obliczeń. Rozważ klasyczny przykład Fibonacciego.

Fibonacciego definiuje się przez nawrót . Jeśli rozwiążesz za pomocą tej rekurencji, w końcu wykonasz wywołania do , ponieważ drzewo rekurencji jest drzewem binarnym o wysokości . $Fib(n)=Fib(n-1)+Fib(n-2)$ $O(2^n)$ $Fib(\cdot)$ $n$

Zamiast tego chcesz obliczyć , a następnie użyj tego, aby znaleźć , użyj tego, aby znaleźć itp. To zajmuje tylko czas . $Fib(2)$ $Fib(3)$ $Fib(4)$ $O(n)$

DP zapewnia nam również podstawowe techniki przekładania relacji rekurencji na rozwiązanie oddolne, ale są one stosunkowo proste (i generalnie obejmują użycie macierzy wymiarowej lub granicy takiej macierzy, gdzie jest liczbą parametrów w relacja powtarzalności). Zostały one dobrze wyjaśnione w dowolnym tekście dotyczącym DP. $m$ $m$

— Kittsil
źródło

1

Mówisz tylko o części zapamiętywania, która nie trafia w sedno pytania.

— Raphael

1

„Programowanie dynamiczne pozwala na wymianę pamięci na czas obliczeń” nie jest czymś, co słyszałem podczas studiów licencjackich, i jest to świetny sposób, aby spojrzeć na ten temat. To jest intuicyjna odpowiedź ze zwięzłym przykładem.

— trueshot

@trueshot: Z wyjątkiem tego, że czasami programowanie dynamiczne (a zwłaszcza „Pruned Dynamic Programming”) jest w stanie zmniejszyć wymagania czasowe i przestrzenne.

— Ben Voigt,

@Ben Nie powiedziałem, że to była transakcja jeden do jednego. Możesz również przycinać drzewo rekurencyjne. Zakładam, że odpowiedziałem na pytanie: „Co dostaje DP?” Daje nam to szybsze algorytmy, handlując przestrzenią czasu. Zgadzam się, że zaakceptowana odpowiedź jest dokładniejsza, ale jest również ważna.

— Kittsil,

2

Oto kolejny nieco inny sposób sformułowania tego, co oferuje programowanie dynamiczne. Programowanie dynamiczne dzieli wykładniczą liczbę rozwiązań kandydujących na wielomianową liczbę klas równoważności, tak że rozwiązania kandydujące w każdej klasie są w pewnym sensie nierozróżnialne.

Jako przykład weźmy problem ze znalezieniem liczby rosnących podciągów długości w tablicy o długości . Przydatne jest podzielenie zestawu wszystkich podsekwencji na klasy równoważności, tak aby dwa podsekwencje należały do tej samej klasy tylko wtedy, gdy mają tę samą długość i kończą się tym samym indeksem. Wszystkie możliwych podsekwencji należą do dokładnie jednej z klas równoważności . Partycjonowanie zachowuje wystarczającą ilość informacji, abyśmy mogli zdefiniować relację powtarzalności dla rozmiarów klas. Jeśli podaje liczbę podsekwencji, które kończą się indeksem mają długość $k$ $A$ $n$ $2^n$ $O(n^2)$ $f(i, \ell)$ $i$ $\ell$ , Następnie mamy:

f (i, ℓ) = \sum_{j < i such that A [j] < A [i]} f (j, ℓ - 1)

$f(i,\ell) = \sum_{j < i \textrm{ such that} A[j] < A[i]} f(j,\ell-1)$

f (i, 1) = 1 for all i = 1 \dots n

$f(i,1) = 1 \textrm{ for all } i = 1 \ldots n$

Ta rekurencja rozwiązuje problem w czasie . $O(n^2k)$

— jnalanko
źródło