Jaka jest różnica między zapamiętywaniem a programowaniem dynamicznym? Myślę, że programowanie dynamiczne jest podzbiorem zapamiętywania. Czy to jest poprawne?
Odpowiedzi:
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:
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!
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)
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
DP ma potencjał do przekształcania rozwiązań sił wykładniczych w czasie wykładniczym w algorytmy wielomianowe.
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,
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.
W programowania dynamicznego ,
W Wczytywanie ,