Co to jest programowanie dynamiczne? [Zamknięte]

Co to jest programowanie dynamiczne ?

Czym różni się od rekurencji, zapamiętywania itp.?

Przeczytałem o nim artykuł w Wikipedii , ale nadal go nie rozumiem.

Programowanie dynamiczne polega na wykorzystaniu wiedzy z przeszłości w celu ułatwienia rozwiązania przyszłego problemu.

Dobrym przykładem jest rozwiązanie sekwencji Fibonacciego dla n = 1.000,002.

To będzie bardzo długi proces, ale co, jeśli dam ci wyniki dla n = 1 000 000 in = 1 000,001? Nagle problem stał się łatwiejszy do opanowania.

Programowanie dynamiczne jest często stosowane w problemach z łańcuchem, takich jak problem z edycją łańcucha. Rozwiązujesz podzbiory problemu, a następnie wykorzystujesz te informacje do rozwiązania trudniejszego problemu oryginalnego.

Dzięki programowaniu dynamicznemu przechowujesz swoje wyniki w jakiejś tabeli. Gdy potrzebujesz odpowiedzi na problem, odnieś się do tabeli i sprawdź, czy już wiesz, co to jest. Jeśli nie, wykorzystasz dane z tabeli, aby dać sobie krok w kierunku odpowiedzi.

Książka Cormen Algorytmy ma świetny rozdział o programowaniu dynamicznym. I to jest bezpłatne w Google Books! Sprawdź to tutaj.

Programowanie dynamiczne jest techniką stosowaną w celu uniknięcia wielokrotnego obliczania tego samego podproblemu w algorytmie rekurencyjnym.

Weźmy prosty przykład liczb Fibonacciego: znalezienie n- ^tej liczby Fibonacciego zdefiniowanej przez

F _n = F _n-1 + F _n-2 i F ₀ = 0, F ₁ = 1

Rekurencja

Oczywistym sposobem na to jest rekurencja:

def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1

    return fibonacci(n - 1) + fibonacci(n - 2)

Programowanie dynamiczne

• Z góry na dół - zapamiętywanie

Rekurencja wykonuje wiele niepotrzebnych obliczeń, ponieważ dana liczba Fibonacciego zostanie obliczona wiele razy. Prostym sposobem na poprawę tego jest buforowanie wyników:

cache = {}

def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    if n in cache:
        return cache[n]

    cache[n] = fibonacci(n - 1) + fibonacci(n - 2)

    return cache[n]

• Od dołu do góry

Lepszym sposobem na to jest całkowite pozbycie się rekurencji poprzez ocenę wyników we właściwej kolejności:

cache = {}

def fibonacci(n):
    cache[0] = 0
    cache[1] = 1

    for i in range(2, n + 1):
        cache[i] = cache[i - 1] +  cache[i - 2]

    return cache[n]

Możemy nawet użyć stałej przestrzeni i po drodze przechowywać tylko niezbędne częściowe wyniki:

def fibonacci(n):
  fi_minus_2 = 0
  fi_minus_1 = 1

  for i in range(2, n + 1):
      fi = fi_minus_1 + fi_minus_2
      fi_minus_1, fi_minus_2 = fi, fi_minus_1

  return fi

• Jak zastosować programowanie dynamiczne?

  1. Znajdź rekurencję w problemie.
  2. Z góry na dół: przechowuj odpowiedź dla każdego podproblemu w tabeli, aby uniknąć konieczności ich ponownego obliczania.
  3. Z dołu do góry: Znajdź odpowiednią kolejność, aby ocenić wyniki, aby częściowe wyniki były dostępne w razie potrzeby.

Programowanie dynamiczne zasadniczo działa w przypadku problemów, które mają naturalną kolejność od lewej do prawej, takich jak ciągi znaków, drzewa lub sekwencje liczb całkowitych. Jeśli naiwny algorytm rekurencyjny nie oblicza wielokrotnie tego samego podproblemu, programowanie dynamiczne nie pomoże.

Zrobiłem zbiór problemów, aby pomóc zrozumieć logikę: https://github.com/tristanguigue/dynamic-programing

Zapamiętywanie to zapisywanie poprzednich wyników wywołania funkcji (rzeczywista funkcja zawsze zwraca to samo, biorąc pod uwagę te same dane wejściowe). Nie ma to znaczenia dla złożoności algorytmu przed zapisaniem wyników.

Rekurencja jest metodą wywoływaną przez funkcję, zwykle z mniejszym zestawem danych. Ponieważ większość funkcji rekurencyjnych można przekształcić w podobne funkcje iteracyjne, nie ma to również znaczenia dla złożoności algorytmicznej.

Programowanie dynamiczne to proces rozwiązywania łatwiejszych do rozwiązania pod-problemów i budowania na ich podstawie odpowiedzi. Większość algorytmów DP będzie działać w czasie między algorytmem chciwym (jeśli taki istnieje) a algorytmem wykładniczym (wylicz wszystkie możliwości i znajdź najlepszy).

• Algorytmy DP mogą być implementowane z rekurencją, ale nie muszą tak być.
• Algorytmy DP nie mogą być przyspieszone przez zapamiętywanie, ponieważ każdy podproblem jest tylko raz rozwiązany (lub wywoływana jest funkcja „rozwiąż”).

Jest to optymalizacja algorytmu, która skraca czas działania.

Podczas gdy Chciwy Algorytm jest zwykle nazywany naiwnym , ponieważ może działać wiele razy na tym samym zestawie danych, Programowanie dynamiczne pozwala uniknąć tej pułapki poprzez głębsze zrozumienie częściowych wyników, które muszą być przechowywane, aby pomóc w zbudowaniu ostatecznego rozwiązania.

Prostym przykładem jest przemierzanie drzewa lub wykresu tylko przez węzły, które przyczyniłyby się do rozwiązania, lub umieszczenie w tabeli rozwiązań, które do tej pory znalazłeś, aby uniknąć wielokrotnego przemierzania tych samych węzłów.

Oto przykład problemu, który nadaje się do programowania dynamicznego, autorstwa internetowego sędzia UVA: Edit Steps Ladder.

Zrobię krótkie omówienie ważnej części analizy tego problemu, zaczerpniętej z książki Wyzwania programistyczne, sugeruję, aby to sprawdzić.

Przyjrzyjmy się temu problemowi, jeśli zdefiniujemy funkcję kosztu, która mówi nam, jak daleko są dwa ciągi, mamy dwa rozważające trzy naturalne typy zmian:

Podstawienie - zmień pojedynczy znak ze wzoru „s” na inny znak w tekście „t”, na przykład zmień „strzał” na „miejsce”.

Wstawianie - wstaw pojedynczy znak do wzorca „s”, aby dopasować go do tekstu „t”, np. Zmień „ago” na „agog”.

Usuwanie - usuń pojedynczy znak ze wzoru „s”, aby pomóc mu dopasować tekst „t”, na przykład zmień „godzinę” na „nasze”.

Kiedy ustawiamy każdą z tych operacji na koszt jednego kroku, definiujemy odległość edycji między dwoma łańcuchami. Jak to obliczyć?

Możemy zdefiniować algorytm rekurencyjny, obserwując, że ostatni znak w ciągu musi być dopasowany, podstawiony, wstawiony lub usunięty. Odcięcie znaków w ostatniej operacji edycji pozostawia operację pary, pozostawiając parę mniejszych ciągów. Niech i i będą ostatnim znakiem odpowiedniego prefiksu odpowiednio t. istnieją trzy pary krótszych ciągów po ostatniej operacji, odpowiadających ciągowi po dopasowaniu / podstawieniu, wstawieniu lub usunięciu. Gdybyśmy znali koszt edycji trzech par mniejszych ciągów, moglibyśmy zdecydować, która opcja prowadzi do najlepszego rozwiązania i wybrać tę opcję odpowiednio. Możemy nauczyć się tego kosztu dzięki niesamowitej rzeczy, jaką jest rekurencja:

#define MATCH 0 /* enumerated type symbol for match */
#define INSERT 1 /* enumerated type symbol for insert */
#define DELETE 2 /* enumerated type symbol for delete */


int string_compare(char *s, char *t, int i, int j)

{

    int k; /* counter */
    int opt[3]; /* cost of the three options */
    int lowest_cost; /* lowest cost */
    if (i == 0) return(j * indel(’ ’));
    if (j == 0) return(i * indel(’ ’));
    opt[MATCH] = string_compare(s,t,i-1,j-1) +
      match(s[i],t[j]);
    opt[INSERT] = string_compare(s,t,i,j-1) +
      indel(t[j]);
    opt[DELETE] = string_compare(s,t,i-1,j) +
      indel(s[i]);
    lowest_cost = opt[MATCH];
    for (k=INSERT; k<=DELETE; k++)
    if (opt[k] < lowest_cost) lowest_cost = opt[k];
    return( lowest_cost );

}

Ten algorytm jest poprawny, ale jest także niemożliwie wolny.

Uruchomienie na naszym komputerze zajmuje kilka sekund, aby porównać dwa ciągi 11 znaków, a obliczenia znikają i nigdy nie lądują na niczym.

Dlaczego algorytm jest tak wolny? Zajmuje to czas wykładniczy, ponieważ ciągle przelicza wartości. Na każdej pozycji ciągu rekurencja rozgałęzia się na trzy sposoby, co oznacza, że ​​rośnie w tempie co najmniej 3 ^ n - w rzeczywistości nawet szybciej, ponieważ większość wywołań redukuje tylko jeden z dwóch indeksów, a nie oba.

Jak więc uczynić algorytm praktycznym? Ważną obserwacją jest to, że większość tych rekurencyjnych wywołań oblicza rzeczy, które zostały już wcześniej obliczone. Skąd wiemy? Cóż, mogą być tylko | s | · | T | możliwe unikalne wywołania rekurencyjne, ponieważ istnieje tylko tyle różnych par (i, j), które służą jako parametry wywołań rekurencyjnych.

Przechowując wartości dla każdej z tych par (i, j) w tabeli, możemy uniknąć ich ponownego obliczenia i po prostu je wyszukać w razie potrzeby.

Tabela jest dwuwymiarową macierzą m, gdzie każda z | s | · | t | komórki zawierają koszt optymalnego rozwiązania tego podproblemu, a także wskaźnik nadrzędny wyjaśniający, w jaki sposób dotarliśmy do tej lokalizacji:

typedef struct {
int cost; /* cost of reaching this cell */
int parent; /* parent cell */
} cell;

cell m[MAXLEN+1][MAXLEN+1]; /* dynamic programming table */

Wersja programowania dynamicznego ma trzy różnice w stosunku do wersji rekurencyjnej.

Po pierwsze, otrzymuje swoje wartości pośrednie za pomocą wyszukiwania tabeli zamiast wywołań rekurencyjnych.

** Po drugie ** aktualizuje pole nadrzędne każdej komórki, co pozwoli nam odtworzyć sekwencję edycji później.

** Trzeci, ** Trzeci, jest instrumentowany przy użyciu bardziej ogólnej cell()funkcji celu zamiast tylko zwracania m [| s |] [| t |] .cost. Umożliwi nam to zastosowanie tej procedury do szerszej klasy problemów.

Tutaj bardzo szczególna analiza tego, co jest potrzebne do zebrania najbardziej optymalnych wyników cząstkowych, sprawia, że ​​rozwiązanie jest „dynamiczne”.

Oto alternatywne, pełne rozwiązanie tego samego problemu. Jest to również „dynamiczny”, mimo że jego wykonanie jest inne. Sugeruję sprawdzenie skuteczności rozwiązania, przekazując go internetowemu sędziemu UVA. Wydaje mi się niesamowite, jak tak skutecznie rozwiązano tak poważny problem.

Kluczowymi częściami programowania dynamicznego są „nakładające się podproblemy” i „optymalna podbudowa”. Te właściwości problemu oznaczają, że optymalne rozwiązanie składa się z optymalnych rozwiązań jego podproblemów. Na przykład problemy z najkrótszą ścieżką wykazują optymalną strukturę. Najkrótsza ścieżka od A do C to najkrótsza ścieżka od A do jakiegoś węzła B, po której następuje najkrótsza ścieżka od tego węzła B do C.

Bardziej szczegółowo, aby rozwiązać problem najkrótszej ścieżki:

• znajdź odległości od węzła początkowego do każdego węzła dotykającego go (powiedzmy od A do B i C)
• znajdź odległości od tych węzłów do węzłów dotykających ich (od B do D i E oraz od C do E i F)
• znamy teraz najkrótszą ścieżkę od A do E: jest to najkrótsza suma Ax i xE dla niektórych węzłów x, które odwiedziliśmy (B lub C)
• powtarzaj ten proces, aż dotrzemy do końcowego węzła docelowego

Ponieważ pracujemy oddolnie, mamy już rozwiązania podproblemów, kiedy przychodzi czas na ich użycie, poprzez ich zapamiętanie.

Pamiętaj, że problemy z programowaniem dynamicznym muszą mieć zarówno nakładające się podproblemy, jak i optymalną podbudowę. Generowanie sekwencji Fibonacciego nie stanowi problemu z programowaniem dynamicznym; korzysta z zapamiętywania, ponieważ ma nakładające się podproblemy, ale nie ma optymalnej podbudowy (ponieważ nie wiąże się z tym problem optymalizacji).

Programowanie dynamiczne

Definicja

Programowanie dynamiczne (DP) to ogólna technika projektowania algorytmów służąca do rozwiązywania problemów z nakładającymi się podproblemami. Technikę tę wynalazł amerykański matematyk „Richard Bellman” w latach 50. XX wieku.

Kluczowy pomysł

Kluczową ideą jest zapisanie odpowiedzi nakładających się mniejszych podproblemów, aby uniknąć ponownego obliczenia.

Dynamiczne właściwości programowania

• Instancja jest rozwiązywana przy użyciu rozwiązań dla mniejszych instancji.
• Rozwiązania dla mniejszej instancji mogą być potrzebne wiele razy, więc przechowuj ich wyniki w tabeli.
• Dlatego każda mniejsza instancja jest rozwiązywana tylko raz.
• Dodatkowa przestrzeń służy do oszczędzania czasu.

Jestem również bardzo nowy w programowaniu dynamicznym (potężny algorytm dla określonego rodzaju problemów)

Mówiąc najprościej, wystarczy pomyśleć o programowaniu dynamicznym jako podejściu rekurencyjnym z wykorzystaniem wcześniejszej wiedzy

Najważniejsza jest wcześniejsza wiedza. Śledź rozwiązania już istniejących problemów.

Rozważ ten najbardziej podstawowy przykład dp z Wikipedii

Znalezienie sekwencji Fibonacciego

function fib(n)   // naive implementation
    if n <=1 return n
    return fib(n − 1) + fib(n − 2)

Przełammy wywołanie funkcji, powiedzmy n = 5

fib(5)
fib(4) + fib(3)
(fib(3) + fib(2)) + (fib(2) + fib(1))
((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
(((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

W szczególności Fib (2) obliczono trzy razy od zera. W większych przykładach oblicza się znacznie więcej wartości Fib lub podproblemów, co prowadzi do wykładniczego algorytmu czasu.

Teraz wypróbujmy to, przechowując wartość, którą już znaleźliśmy w strukturze danych, na przykład mapę

var m := map(0 → 0, 1 → 1)
function fib(n)
    if key n is not in map m 
        m[n] := fib(n − 1) + fib(n − 2)
    return m[n]

Tutaj zapisujemy rozwiązanie podproblemów na mapie, jeśli jeszcze go nie mamy. Ta technika zapisywania wartości, które już obliczyliśmy, jest nazywana Zapamiętywaniem.

Wreszcie, w przypadku problemu, najpierw spróbuj znaleźć stany (możliwe podproblemy i spróbuj wymyślić lepsze podejście rekurencyjne, abyś mógł zastosować rozwiązanie poprzedniego podproblemu do kolejnych).

Programowanie dynamiczne to technika rozwiązywania problemów z nakładającymi się problemami podrzędnymi. Algorytm programowania dynamicznego rozwiązuje każdy problem podrzędny tylko raz, a następnie zapisuje swoją odpowiedź w tabeli (tablicy). Unikanie pracy ponownego obliczania odpowiedzi za każdym razem, gdy napotyka się problem podrzędny. Podstawową ideą programowania dynamicznego jest: Unikaj dwukrotnego obliczania tych samych rzeczy, zwykle poprzez utrzymywanie tabeli znanych wyników podproblemów.

Siedem kroków w rozwoju algorytmu programowania dynamicznego jest następujące:

1. Ustanów rekurencyjną właściwość, która daje rozwiązanie wystąpienia problemu.
2. Opracuj algorytm rekurencyjny zgodnie z właściwością rekurencyjną
3. Sprawdź, czy to samo wystąpienie problemu jest rozwiązywane ponownie w połączeniach rekurencyjnych
4. Opracuj zapamiętany algorytm rekurencyjny
5. Zobacz wzorzec przechowywania danych w pamięci
6. Przekształć zapamiętany algorytm rekurencyjny w algorytm iteracyjny
7. Zoptymalizuj iteracyjny algorytm, używając pamięci zgodnie z wymaganiami (optymalizacja pamięci)

w skrócie różnica między zapamiętywaniem rekurencyjnym a programowaniem dynamicznym

Programowanie dynamiczne, jak sugeruje nazwa, wykorzystuje poprzednią obliczoną wartość do dynamicznego konstruowania następnego nowego rozwiązania

Gdzie zastosować programowanie dynamiczne: Jeśli twoje rozwiązanie opiera się na optymalnej podbudowie i pokrywającym się podproblemie, wówczas w takim przypadku przydatne będzie użycie wcześniej obliczonej wartości, więc nie musisz jej ponownie obliczać. To podejście oddolne. Załóżmy, że musisz obliczyć Fib (n). W takim przypadku wystarczy dodać poprzednią obliczoną wartość Fib (n-1) i Fib (n-2)

Rekurencja: Zasadniczo dzielenie problemu na mniejsze części w celu jego łatwego rozwiązania, ale należy pamiętać, że nie uniknie się ponownego obliczenia, jeśli mamy taką samą wartość obliczoną wcześniej w innym wywołaniu rekurencyjnym.

Zapamiętywanie: Zasadniczo zapisywanie starej obliczonej wartości rekurencji w tabeli jest znane jako zapamiętywanie, które pozwoli uniknąć ponownego obliczenia, jeśli zostało już obliczone przez jakieś poprzednie wywołanie, więc dowolna wartość zostanie obliczona raz. Dlatego przed obliczeniem sprawdzamy, czy ta wartość została już obliczona, czy nie, jeśli już została obliczona, a następnie zwracamy to samo z tabeli zamiast ponownego obliczania. Jest to również podejście odgórne

Oto przykład prostego kodu Pythona z Recursive, Top-down, Bottom-uppodejście do serii Fibonacciego:

Rekurencyjny: O (2 ⁿ )

def fib_recursive(n):
    if n == 1 or n == 2:
        return 1
    else:
        return fib_recursive(n-1) + fib_recursive(n-2)


print(fib_recursive(40))

Z góry na dół: O (n) Wydajny przy większych wejściach

def fib_memoize_or_top_down(n, mem):
    if mem[n] is not 0:
        return mem[n]
    else:
        mem[n] = fib_memoize_or_top_down(n-1, mem) + fib_memoize_or_top_down(n-2, mem)
        return mem[n]


n = 40
mem = [0] * (n+1)
mem[1] = 1
mem[2] = 1
print(fib_memoize_or_top_down(n, mem))

Z dołu do góry: O (n) Dla uproszczenia i małych rozmiarów wejściowych

def fib_bottom_up(n):
    mem = [0] * (n+1)
    mem[1] = 1
    mem[2] = 1
    if n == 1 or n == 2:
        return 1

    for i in range(3, n+1):
        mem[i] = mem[i-1] + mem[i-2]

    return mem[n]


print(fib_bottom_up(40))