Jaka jest różnica między algorytmami dzielenia i zwyciężania a algorytmami programowania dynamicznego? Czym różnią się te dwa terminy? Nie rozumiem różnicy między nimi.
Proszę posłużyć się prostym przykładem, aby wyjaśnić różnice między nimi i na jakiej podstawie wydają się być podobne.
Odpowiedzi:
Dziel i rządź
Dziel i rządź działa, dzieląc problem na podproblemy, pokonując rekursywnie każdy podproblem i łącząc te rozwiązania.
Programowanie dynamiczne
Programowanie dynamiczne to technika rozwiązywania problemów z nakładającymi się podproblemami. Każdy problem podrzędny jest rozwiązywany tylko raz, a wynik każdego problemu podrzędnego jest przechowywany w tabeli (zwykle zaimplementowanej jako tablica lub tablica mieszająca) do przyszłych odniesień. Te pod-rozwiązania mogą być wykorzystane do uzyskania oryginalnego rozwiązania, a technika przechowywania rozwiązań podproblemów jest znana jako zapamiętywanie.
Możesz pomyśleć DP = recursion + re-use
Klasycznym przykładem zrozumienia różnicy byłoby zobaczenie obu tych podejść do uzyskania n-tej liczby Fibonacciego. Sprawdź ten materiał z MIT.
Podejście dziel i rządź
Dynamiczne podejście do programowania
Inną różnicą między dziel i zwyciężaj a programowaniem dynamicznym może być:
Dziel i rządź:
Programowanie dynamiczne:
czasami, gdy programujesz rekurencyjnie, wielokrotnie wywołujesz funkcję z tymi samymi parametrami, co jest niepotrzebne.
Słynny przykład liczb Fibonacciego:
index: 1,2,3,4,5,6...
Fibonacci number: 1,1,2,3,5,8...
function F(n) {
if (n < 3)
return 1
else
return F(n-1) + F(n-2)
}
Uruchommy F (5):
F(5) = F(4) + F(3)
= {F(3)+F(2)} + {F(2)+F(1)}
= {[F(2)+F(1)]+1} + {1+1}
= 1+1+1+1+1
Więc nazwaliśmy: 1 razy F (4) 2 razy F (3) 3 razy F (2) 2 razy F (1)
Podejście do programowania dynamicznego: jeśli wywołasz funkcję z tym samym parametrem więcej niż jeden raz, zapisz wynik w zmiennej, aby następnym razem uzyskać do niej bezpośredni dostęp. Sposób iteracyjny:
if (n==1 || n==2)
return 1
else
f1=1, f2=1
for i=3 to n
f = f1 + f2
f1 = f2
f2 = f
Nazwijmy ponownie F (5):
fibo1 = 1
fibo2 = 1
fibo3 = (fibo1 + fibo2) = 1 + 1 = 2
fibo4 = (fibo2 + fibo3) = 1 + 2 = 3
fibo5 = (fibo3 + fibo4) = 2 + 3 = 5
Jak widać, zawsze, gdy potrzebujesz wywołania wielokrotnego, po prostu uzyskujesz dostęp do odpowiedniej zmiennej, aby uzyskać wartość, zamiast ją ponownie obliczać.
Nawiasem mówiąc, programowanie dynamiczne nie oznacza przekształcania kodu rekurencyjnego w kod iteracyjny. Możesz również zapisać podwyniki w zmiennej, jeśli chcesz uzyskać kod rekurencyjny. W tym przypadku technika nazywa się zapamiętywaniem. W naszym przykładzie wygląda to tak:
// declare and initialize a dictionary
var dict = new Dictionary<int,int>();
for i=1 to n
dict[i] = -1
function F(n) {
if (n < 3)
return 1
else
{
if (dict[n] == -1)
dict[n] = F(n-1) + F(n-2)
return dict[n]
}
}
Tak więc związek z dzieleniem i zwyciężaniem polega na tym, że algorytmy D&D opierają się na rekurencji. W niektórych wersjach występuje to „wywołanie wielu funkcji z tym samym problemem z parametrami”. Wyszukaj „mnożenie łańcucha macierzy” i „najdłuższy wspólny podciąg” dla takich przykładów, w których DP jest potrzebne do ulepszenia T (n) algo D&D.
Jak na razie to widzę, mogę powiedzieć, że programowanie dynamiczne jest rozszerzeniem paradygmatu dziel i rządź .
Nie traktowałbym ich jako czegoś zupełnie innego. Ponieważ oba działają na zasadzie rekurencyjnego podziału problemu na dwa lub więcej podproblemów tego samego lub pokrewnego typu, dopóki nie staną się one na tyle proste, aby można je było rozwiązać bezpośrednio. Rozwiązania podproblemów są następnie łączone, aby dać rozwiązanie pierwotnego problemu.
Dlaczego więc nadal mamy różne nazwy paradygmatów i dlaczego nazwałem programowanie dynamiczne rozszerzeniem. Dzieje się tak, ponieważ dynamiczne podejście do programowania można zastosować do problemu tylko wtedy, gdy problem ma pewne ograniczenia lub warunki wstępne . Po tym dynamicznym programowaniu rozszerza się podejście dziel i zwyciężaj z zapamiętywaniem lub techniką tabelaryczną .
Przejdźmy krok po kroku…
Jak właśnie odkryliśmy, istnieją dwa kluczowe atrybuty, które muszą posiadać problem, który dzieli i pokonuje, aby programowanie dynamiczne mogło mieć zastosowanie:
Optymalna podkonstrukcja - optymalne rozwiązanie można zbudować z optymalnych rozwiązań jej podproblemów
Nakładające się podproblemy - problem można rozbić na podproblemy, które są wykorzystywane wielokrotnie lub rekurencyjny algorytm dla problemu rozwiązuje ten sam podproblem w kółko, zamiast zawsze generować nowe podproblemy
Gdy te dwa warunki zostaną spełnione, możemy powiedzieć, że ten problem „dziel i rządź” można rozwiązać za pomocą metody programowania dynamicznego.
Dynamiczne podejście do programowania rozszerza podejście dziel i zwyciężaj za pomocą dwóch technik ( zapamiętywania i tworzenia tabel ), które mają na celu przechowywanie i ponowne wykorzystanie rozwiązań podproblemów, które mogą drastycznie poprawić wydajność. Na przykład naiwna rekurencyjna implementacja funkcji Fibonacciego ma złożoność czasową, w O(2^n)której rozwiązanie DP robi to samo tylko z O(n)czasem.
Memoizacja (wypełnianie pamięci podręcznej z góry na dół) odnosi się do techniki buforowania i ponownego wykorzystywania wcześniej obliczonych wyników. Zapamiętana fibfunkcja wyglądałaby więc następująco:
memFib(n) {
if (mem[n] is undefined)
if (n < 2) result = n
else result = memFib(n-2) + memFib(n-1)
mem[n] = result
return mem[n]
}
Tabulacja (wypełnianie pamięci podręcznej od dołu do góry) jest podobna, ale koncentruje się na wypełnianiu wpisów w pamięci podręcznej. Obliczanie wartości w pamięci podręcznej jest najłatwiejsze do wykonania iteracyjnie. Wersja tabelaryczna programu fibwyglądałaby następująco:
tabFib(n) {
mem[0] = 0
mem[1] = 1
for i = 2...n
mem[i] = mem[i-2] + mem[i-1]
return mem[n]
}
Możesz przeczytać więcej o zapamiętywaniu i porównaniu tabelarycznym tutaj .
Główną ideą, którą powinieneś tu zrozumieć, jest to, że ponieważ nasz problem dziel i rządź ma nakładające się podproblemy, możliwe staje się buforowanie rozwiązań podproblemów, a zatem zapamiętywanie / tabulacja wkraczają na scenę.
Ponieważ jesteśmy teraz zaznajomieni z warunkami wstępnymi DP i jej metodologiami, jesteśmy gotowi umieścić wszystko, o czym wspomniano powyżej, w jednym obrazku.
Jeśli chcesz zobaczyć przykłady kodu, możesz przyjrzeć się bardziej szczegółowemu wyjaśnieniu tutaj, w którym znajdziesz dwa przykłady algorytmów: wyszukiwanie binarne i minimalna odległość edycji (odległość Levenshteina), które ilustrują różnicę między DP i DC.
Zakładam, że przeczytałeś już Wikipedię i inne zasoby akademickie na ten temat, więc nie będę przetwarzał żadnej z tych informacji. Muszę również zastrzec, że w żadnym wypadku nie jestem ekspertem informatycznym, ale podzielę się swoimi dwoma centami na moje zrozumienie tych tematów ...
Rozkłada problem na dyskretne podproblemy. Algorytm rekurencyjny dla sekwencji Fibonacciego jest przykładem programowania dynamicznego, ponieważ rozwiązuje on fib (n), rozwiązując najpierw dla fib (n-1). Aby rozwiązać pierwotny problem, rozwiązuje inny problem.
Algorytmy te zazwyczaj rozwiązują podobne elementy problemu, a na końcu łączą je razem. Mergesort to klasyczny przykład dziel i rządź. Główna różnica między tym przykładem a przykładem Fibonacciego polega na tym, że w przypadku łączenia, dzielenie może (teoretycznie) być dowolne i bez względu na to, jak go podzielisz, nadal scalasz i sortujesz. Tyle samo pracy trzeba wykonać, aby scalić tablicę, bez względu na sposób jej podzielenia. Rozwiązanie dla fib (52) wymaga więcej kroków niż rozwiązanie dla fib (2).
Myślę o Divide & Conquerpodejściu rekurencyjnym i Dynamic Programmingjako o wypełnianiu tabeli.
Na przykład Merge Sortto Divide & Conqueralgorytm, ponieważ w każdym kroku dzielisz tablicę na dwie połowy, rekurencyjnie wywołujesz Merge Sortdwie połowy, a następnie je łączysz.
Knapsackto Dynamic Programmingalgorytm wypełniający tabelę przedstawiającą optymalne rozwiązania podproblemów całego plecaka. Każdy wpis w tabeli odpowiada maksymalnej wartości, jaką można przewozić w worku o wadze w danych pozycji 1-j.
Divide and Conquer obejmuje trzy kroki na każdym poziomie rekurencji:
Programowanie dynamiczne obejmuje cztery następujące kroki:
1. Scharakteryzuj strukturę optymalnych rozwiązań.
2. Rekurencyjnie definiować wartości optymalnych rozwiązań.
3. Oblicz wartość optymalnych rozwiązań.
4. Skonstruuj optymalne rozwiązanie na podstawie obliczonych informacji .
Aby ułatwić zrozumienie, zobaczmy dziel i rządź jako rozwiązanie brutalnej siły, a jego optymalizację jako programowanie dynamiczne.
Uwaga: algorytmy dzielenia i zwyciężania z nakładającymi się podproblemami można optymalizować tylko za pomocą dp.
fact(5) = 5* fact(4) = 5 * (4 * fact(3))= 5 * 4 * (3 *fact(2))= 5 * 4 * 3 * 2 * (fact(1))
Jak widać powyżej, żaden fakt (x) się nie powtarza, więc silnia nie ma nakładających się problemów.
fib(5) = fib(4) + fib(3) = (fib(3)+fib(2)) + (fib(2)+fib(1))
Jak widać powyżej, zarówno fib (4), jak i fib (3) używają fib (2). podobnie, wiele fraz (x) zostaje powtórzonych. dlatego Fibonacci ma nakładające się podproblemy.