Jaka jest różnica między zapamiętywaniem a programowaniem dynamicznym?

Jaka jest różnica między zapamiętywaniem a programowaniem dynamicznym? Myślę, że programowanie dynamiczne jest podzbiorem zapamiętywania. Czy to jest poprawne?

Odpowiedni artykuł na temat programowania. Przewodnik : Programowanie dynamiczne a zapamiętywanie vs tabulacja

Jaka jest różnica między zapamiętywaniem a programowaniem dynamicznym?

Zapamiętywanie jest terminem opisującym technikę optymalizacji, w której buforowane są wcześniej obliczone wyniki, i zwracany jest buforowany wynik, gdy ponownie potrzebne jest to samo obliczenie.

Programowanie dynamiczne jest techniką rozwiązywania problemów o charakterze rekurencyjnym, iteracyjnie i ma zastosowanie, gdy obliczenia podproblemów się pokrywają.

Programowanie dynamiczne jest zwykle realizowane za pomocą tabel, ale może być również realizowane za pomocą zapamiętywania. Jak widać, żaden z nich nie jest „podzbiorem” drugiego.

Rozsądne pytanie uzupełniające brzmi: jaka jest różnica między tabelowaniem (typową techniką programowania dynamicznego) a zapamiętywaniem?

Kiedy rozwiązujesz problem z programowaniem dynamicznym za pomocą tabulacji, rozwiązujesz problem „ oddolnie ”, tzn. Najpierw rozwiązując wszystkie powiązane podproblemy, zwykle wypełniając tabelę n- wymiarową. Na podstawie wyników w tabeli obliczane jest następnie rozwiązanie problemu „górnego” / oryginalnego.

Jeśli użyjesz notatki do rozwiązania problemu, zrobisz to, utrzymując mapę już rozwiązanych problemów podrzędnych. Robisz to „z góry na dół ” w tym sensie, że najpierw rozwiązujesz problem „z góry” (który zwykle powtarza się, aby rozwiązać pod-problemy).

Dobry slajd z tego miejsca (link jest już martwy, ale slajd jest nadal dobry):

• Jeśli wszystkie podproblemy muszą zostać rozwiązane przynajmniej raz, algorytm programowania dynamicznego typu bottom-up zwykle przewyższa algorytm zapamiętywany odgórnie o stały współczynnik
  • Bez obciążenia na rekurencję i mniej na utrzymanie stołu
  • Istnieją pewne problemy, w przypadku których można wykorzystać regularny wzór dostępu do tabeli w algorytmie programowania dynamicznego, aby jeszcze bardziej zmniejszyć wymagania dotyczące czasu lub miejsca
• Jeśli niektóre podproblemy w przestrzeni podproblemów wcale nie muszą być rozwiązane, zapamiętane rozwiązanie ma tę zaletę, że rozwiązuje tylko te podproblemy, które są zdecydowanie wymagane

Dodatkowe zasoby:

• Wikipedia: Memoization , Programowanie dynamiczne
• Powiązane SO Q / A: Zapamiętywanie lub podejście tabelaryczne dla programowania dynamicznego

Programowanie dynamiczne jest paradygmatem algorytmicznym, który rozwiązuje dany złożony problem poprzez rozbicie go na podproblemy i przechowuje wyniki podproblemów, aby uniknąć ponownego obliczania tych samych wyników.

http://www.geeksforgeeks.org/dynamic-programming-set-1/

Zapamiętywanie jest łatwą metodą śledzenia wcześniej rozwiązanych rozwiązań (często implementowanych jako para klucz-wartość skrótu, w przeciwieństwie do tabelarycznego obliczania, które często oparte jest na tablicach), dzięki czemu nie są ponownie obliczane, gdy zostaną ponownie napotkane. Może być stosowany zarówno w metodach od dołu do góry, jak i od góry do dołu.

Zobacz tę dyskusję na temat zapamiętywania vs tabelowania.

Programowanie dynamiczne jest więc metodą rozwiązywania niektórych klas problemów przez rozwiązywanie relacji / rekurencji rekurencji i przechowywanie wcześniej znalezionych rozwiązań za pomocą tabelarycznej lub zapamiętywania. Memoizacja to metoda śledzenia rozwiązań wcześniej rozwiązanych problemów i może być używana z dowolną funkcją, która ma unikalne deterministyczne rozwiązania dla danego zestawu danych wejściowych.

Programowanie dynamiczne jest często nazywane zapamiętywaniem!

1. Zapamiętywanie jest techniką odgórną (zacznij rozwiązywanie danego problemu przez jego rozbicie), a programowanie dynamiczne jest techniką oddolną (zacznij rozwiązywanie od trywialnego podproblemu, aż do danego problemu)

2. DP znajduje rozwiązanie, zaczynając od skrzynek podstawowych i przechodząc w górę. DP rozwiązuje wszystkie pod-problemy, ponieważ robi to oddolnie

   W przeciwieństwie do Memoization, który rozwiązuje tylko potrzebne pod-problemy

3. DP ma potencjał do przekształcania rozwiązań sił wykładniczych w czasie wykładniczym w algorytmy wielomianowe.

4. DP może być znacznie wydajniejszy, ponieważ jest iteracyjny

   Przeciwnie, Memoization musi zapłacić za (często znaczny) narzut z powodu rekurencji.

Mówiąc prościej, Memoization wykorzystuje podejście odgórne do rozwiązania problemu, tzn. Zaczyna się od głównego (głównego) problemu, a następnie dzieli go na podproblemy i rozwiązuje te podproblemy podobnie. W tym podejściu ten sam podproblem może występować wiele razy i zużywać więcej cykli procesora, a zatem zwiększać złożoność czasu. Podczas gdy w programowaniu dynamicznym ten sam pod-problem nie zostanie rozwiązany wiele razy, ale wcześniejszy wynik zostanie wykorzystany do optymalizacji rozwiązania.

(1) Zapamiętywanie i DP, koncepcyjnie , to tak naprawdę to samo. Ponieważ: rozważ definicję DP: „nakładające się podproblemy” „i optymalną podkonstrukcję”. Zapamiętywanie w pełni posiada te 2.

(2) Zapamiętywanie jest DP z ryzykiem przepełnienia stosu, gdy rekurencja jest głęboka. DP od dołu nie ma tego ryzyka.

(3) Zapamiętywanie wymaga tabeli skrótów. Więc dodatkowe miejsce i trochę czasu wyszukiwania.

Aby odpowiedzieć na pytanie:

- Koncepcyjnie (1) oznacza, że ​​są tym samym.

- Biorąc pod uwagę (2), jeśli naprawdę chcesz, zapamiętywanie jest podzbiorem DP, w tym sensie, że problem rozwiązany przez zapamiętywanie będzie rozwiązany przez DP, ale problem rozwiązany przez DP może nie być rozwiązany przez zapamiętywanie (ponieważ może przepełnić stos).

- Biorąc pod uwagę (3), mają one niewielkie różnice w wydajności.

Z wikipedii:

Zapamiętywanie

W obliczeniach zapamiętywanie jest techniką optymalizacji stosowaną przede wszystkim w celu przyspieszenia programów komputerowych, ponieważ wywołania funkcji pozwalają uniknąć powtarzania obliczeń wyników dla wcześniej przetworzonych danych wejściowych.

Programowanie dynamiczne

W matematyce i informatyce programowanie dynamiczne jest metodą rozwiązywania złożonych problemów poprzez dzielenie ich na prostsze podproblemy.

Rozbijając problem na mniejsze / prostsze podproblemy, często spotykamy ten sam podproblem więcej niż jeden raz - dlatego używamy Memoization do zapisywania wyników poprzednich obliczeń, więc nie musimy ich powtarzać.

Programowanie dynamiczne często napotyka sytuacje, w których warto skorzystać z zapamiętywania, ale można zastosować jedną z technik bez konieczności korzystania z drugiej.

Zarówno memoizacja, jak i programowanie dynamiczne rozwiązują pojedynczy podproblem tylko raz.

Memoizacja wykorzystuje rekurencję i działa od góry do dołu, podczas gdy programowanie dynamiczne porusza się w przeciwnym kierunku, rozwiązując problem od dołu do góry.

Poniżej znajduje się interesująca analogia -

Z góry na dół - najpierw powiesz, że przejmie świat. Jak to zrobisz? Mówisz, że najpierw przejmę Azję. Jak to zrobisz? Najpierw przejmę Indie. Zostanę naczelnym ministrem Delhi itp. Itd.

Od dołu do góry - Mówisz, że zostanę CM z Delhi. Potem przejmie Indie, potem wszystkie inne kraje w Azji, a na końcu przejmie świat.

Chciałbym pójść z przykładem ;

Problem:

Wspinasz się po schodach. Aby dotrzeć na szczyt, potrzeba n kroków.

Za każdym razem możesz wejść na 1 lub 2 stopnie. Na ile różnych sposobów możesz wspiąć się na szczyt?

Rekurencja z zapamiętywaniem

W ten sposób przycinamy (usuwanie nadmiaru materiału z drzewa lub krzewu) drzewa rekurencyjnego za pomocą tablicy notatek i zmniejszając rozmiar drzewa rekurencyjnego do nn.

public class Solution {
    public int climbStairs(int n) {
        int memo[] = new int[n + 1];
        return climb_Stairs(0, n, memo);
    }
    public int climb_Stairs(int i, int n, int memo[]) {
        if (i > n) {
            return 0;
        }
        if (i == n) {
            return 1;
        }
        if (memo[i] > 0) {
            return memo[i];
        }
        memo[i] = climb_Stairs(i + 1, n, memo) + climb_Stairs(i + 2, n, memo);
        return memo[i];
    }
}

Programowanie dynamiczne

Jak widzimy, problem ten można podzielić na podproblemy i zawiera on optymalną właściwość podbudowy, tj. Jego optymalne rozwiązanie można skutecznie zbudować z optymalnych rozwiązań jego podproblemów, możemy zastosować programowanie dynamiczne, aby rozwiązać ten problem.

public class Solution {
    public int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

Przykłady pochodzą z https://leetcode.com/problems/climbing-stairs/

Pomyśl tylko na dwa sposoby,

1. Rozbijamy większy problem na mniejsze pod-problemy - podejście odgórne.
2. Zaczynamy od najmniejszego problemu podrzędnego i osiągamy większy problem - podejście oddolne.

W Memoization przechodzimy do (1.), gdzie zapisujemy każde wywołanie funkcji w pamięci podręcznej i stamtąd oddzwaniamy. Jest to trochę drogie, ponieważ obejmuje połączenia rekurencyjne.

W Programowaniu dynamicznym przechodzimy do (2.), gdzie utrzymujemy tabelę, oddolnie, rozwiązując podproblemy z wykorzystaniem danych zapisanych w tabeli, zwanych potocznie dp-table.

Uwaga:

• Oba mają zastosowanie do problemów z nakładającymi się podproblemami.

• Zapamiętywanie działa stosunkowo słabo w stosunku do DP z powodu narzutów związanych z wywołaniami funkcji rekurencyjnych.

• Asymptotyczna złożoność czasowa pozostaje taka sama.

W programowania dynamicznego ,

• Brak narzutu na rekurencję, mniej narzutu na utrzymanie stołu.
• Regularny wzór dostępu do tabeli może być wykorzystywany w celu zmniejszenia wymagań dotyczących czasu lub miejsca.

W Wczytywanie ,

• Niektóre podproblemy nie wymagają rozwiązania.