Na czym polega programowanie dynamiczne?

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:

1. wyrazić problem jako relację nawrotu;
2. 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?

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ągS [ 1 .. i ] S [ j . . n ] S [ i . . j ] n S $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 ′ 0 ≤ n ′ ≤ $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 .. i ] S [ 1 .. n ] S [ j . . n ] S [ 1 .. n ] S [ i . . j ] i , $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 x T x $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 ′ x y ′ y ( x , y ′ ) ( x ′ , y $(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 „

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]$

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

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

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

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 .O ( 2 n ) F i b ( ⋅ ) $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 .F i b ( 3 ) F i b ( 4 ) O ( n $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$

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śćA n 2 n O ( n 2 ) f ( i , ℓ $k$$A$$n$$2^n$$O(n^2)$$f(i, \ell)$$i$$\ell$, Następnie mamy:

f ( i , 1 ) = 1  dla wszystkich  i = 1 …

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