Różnica między Divide and Conquer Algo a programowaniem dynamicznym

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.

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ź:

1. Robi więcej pracy nad podproblemami i tym samym ma więcej czasu.
2. W przypadku dziel i zwyciężaj podproblemy są od siebie niezależne.

Programowanie dynamiczne:

1. Rozwiązuje podproblemy tylko raz, a następnie zapisuje je w tabeli.
2. W programowaniu dynamicznym podproblem nie jest niezależny.

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.

Programowanie dynamiczne a podobieństwa typu „dziel i zwyciężaj”

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…

Wymagania wstępne / ograniczenia dotyczące programowania dynamicznego

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 rozszerzenie programowania dla dziel i rządź

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

Więc jaka jest różnica między DP a DC

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

Programowanie dynamiczne

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.

Dziel i rządź

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:

1. Podziel problem na podproblemy.
2. Pokonaj podproblemy, rozwiązując je rekurencyjnie.
3. Połącz rozwiązanie podproblemów w rozwiązanie pierwotnego problemu.
   
   • Jest to podejście odgórne .
     
   • Wykonuje więcej pracy z podproblemami, a tym samym zajmuje więcej czasu.
   • na przykład. n-ty człon szeregu Fibonacciego można obliczyć w złożoności czasowej O (2 ^ n).
     
     

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 .

• Jest to oddolne podejście.
• Mniejsze zużycie czasu niż dzielenie i zwyciężanie, ponieważ używamy wartości obliczonych wcześniej, zamiast obliczać ponownie.
• na przykład. n-ty człon szeregu Fibonacciego można obliczyć w złożoności czasowej O (n).
  
  

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.

• Dziel i rządź
  • Włamali się do nienakładających się podproblemów
  • Przykład: liczby silnia, tj. Fakt (n) = n * fakt (n-1)

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.

• Programowanie dynamiczne
  • Włamali się do nakładających się podproblemów
  • Przykład: liczby Fibonacciego, tj. Fib (n) = fib (n-1) + fib (n-2)

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.

• W wyniku powtarzania się podproblemu w DP, możemy zachować takie wyniki w tabeli i zaoszczędzić wysiłek obliczeniowy. nazywa się to zapamiętywaniem