Jaka jest różnica między oddolnym a odgórnym?

Oddolne podejście (do programowania dynamicznego) polega na pierwsze spojrzenie na „mniejsze” podproblemów, a następnie rozwiązać większych podproblemów użyciu rozwiązanie do mniejszych problemów.

Top-down polega na rozwiązywaniu problemu w sposób „naturalny” i sprawdź, czy masz obliczył rozwiązanie subproblem wcześniej.

Jestem trochę zdezorientowany. Jaka jest różnica między tymi dwoma?

rev4: Bardzo wymowny komentarz użytkownika Sammaron zauważył, że być może ta odpowiedź była wcześniej mylona z góry na dół i z dołu do góry. Chociaż pierwotnie ta odpowiedź (rev3) i inne odpowiedzi mówiły, że „oddolne jest zapamiętywaniem” („załóżmy podproblemy”), może być odwrotne (to znaczy „odgórne” może oznaczać „zakładanie podproblemów” i „ oddolnie „może być„ składać podproblemy ”). Wcześniej czytałem o zapamiętywaniu będącym innym rodzajem programowania dynamicznego w przeciwieństwie do podtypu programowania dynamicznego. Cytowałem ten punkt widzenia, mimo że go nie podzielałem. Przepisałem tę odpowiedź tak, aby była agnostyczna w stosunku do terminologii, dopóki w literaturze nie będzie można znaleźć odpowiednich odniesień. Przekonwertowałem również tę odpowiedź na wiki społeczności. Proszę preferować źródła akademickie. Lista referencji:} {Literatura: 5 }

Podsumować

Programowanie dynamiczne polega na porządkowaniu obliczeń w taki sposób, aby uniknąć ponownego obliczania powielonych prac. Masz główny problem (korzeń twojego drzewa podproblemów) i podproblemy (poddrzewa). Podproblemy zwykle się powtarzają i nakładają .

Weźmy na przykład pod uwagę swój ulubiony przykład Fibonnaci. To jest pełne drzewo podproblemów, gdybyśmy wykonali naiwne wywołanie rekurencyjne:

TOP of the tree
fib(4)
 fib(3)...................... + fib(2)
  fib(2)......... + fib(1)       fib(1)........... + fib(0)
   fib(1) + fib(0)   fib(1)       fib(1)              fib(0)
    fib(1)   fib(0)
BOTTOM of the tree

(W niektórych innych rzadkich problemach drzewo to może być nieskończone w niektórych gałęziach, reprezentując brak zakończenia, a zatem jego spód może być nieskończenie duży. Ponadto w niektórych problemach możesz nie wiedzieć, jak wygląda pełne drzewo przed Dlatego możesz potrzebować strategii / algorytmu, aby zdecydować, które podproblemy ujawnić).

Memoization, Tabulation

Istnieją co najmniej dwie główne techniki programowania dynamicznego, które nie wykluczają się wzajemnie:

• Zapamiętywanie - jest to podejście laissez-faire: zakładasz, że obliczyłeś już wszystkie podproblemy i nie masz pojęcia, jaka jest optymalna kolejność oceny. Zazwyczaj wykonywałbyś wywołanie rekurencyjne (lub jakiś iteracyjny odpowiednik) z korzenia i albo miałbyś nadzieję, że zbliżysz się do optymalnej kolejności oceny, albo uzyskasz dowód, że pomożesz ci dojść do optymalnej kolejności oceny. Zapewniłbyś, że rekurencyjne wywołanie nigdy nie przelicza podproblemu, ponieważ buforujesz wyniki, a zatem zduplikowane poddrzewa nie są ponownie obliczane.

  • Przykład: Jeśli obliczasz ciąg Fibonacciego fib(100), po prostu wywołałbyś to, a on zadzwoniłby fib(100)=fib(99)+fib(98), który wywołałby fib(99)=fib(98)+fib(97), ... itd ..., który zadzwoni fib(2)=fib(1)+fib(0)=1+0=1. W końcu to rozwiązałoby się fib(3)=fib(2)+fib(1), ale nie trzeba go ponownie obliczać fib(2), ponieważ zapisaliśmy go w pamięci podręcznej.
  • Rozpoczyna się na szczycie drzewa i ocenia podproblemy od liści / poddrzewów z powrotem do korzenia.

• Tabulacja - Możesz również myśleć o programowaniu dynamicznym jako o algorytmie "wypełniania tabeli" (choć zwykle jest to wielowymiarowe, ta 'tabela' może w bardzo rzadkich przypadkach mieć geometrię nieeuklidesową *). Jest to podobne do zapamiętywania, ale bardziej aktywne i obejmuje jeden dodatkowy krok: musisz z wyprzedzeniem wybrać dokładną kolejność wykonywania obliczeń. Nie powinno to oznaczać, że kolejność musi być statyczna, ale masz znacznie większą elastyczność niż zapamiętywanie.

  • Przykład: Jeśli wykonujesz Fibonacciego, można wybrać do obliczania liczby w tej kolejności: fib(2), fib(3), fib(4)... buforowanie każdą wartość, dzięki czemu można łatwiej obliczyć kolejnych. Możesz również myśleć o tym jako o zapełnianiu tabeli (inna forma buforowania).
  • Osobiście nie słyszę często słowa „tabulacja”, ale jest to bardzo przyzwoity termin. Niektórzy uważają to za „programowanie dynamiczne”.
  • Przed uruchomieniem algorytmu programista bierze pod uwagę całe drzewo, a następnie pisze algorytm do oceny podproblemów w określonej kolejności w kierunku korzenia, generalnie wypełniając tabelę.
  • * przypis: Czasami „tabela” nie jest tabelą prostokątną z połączeniami podobnymi do siatki per se. Może raczej mieć bardziej skomplikowaną strukturę, taką jak drzewo lub strukturę specyficzną dla domeny problemowej (np. Miasta w niewielkiej odległości na mapie), a nawet diagram kratowy, który, choć podobny do siatki, nie ma struktura połączeń góra-dół-lewa-prawa itd. Na przykład user3290797 połączył przykład programowania dynamicznego polegający na znalezieniu maksymalnego niezależnego zbioru w drzewie , co odpowiada wypełnieniu pustych miejsc w drzewie.

(Najogólniej mówiąc, w paradygmacie „programowania dynamicznego” powiedziałbym, że programista bierze pod uwagę całe drzewo, a następniepisze algorytm, który implementuje strategię oceny podproblemów, która może zoptymalizować dowolne właściwości, jakie chcesz (zwykle połączenie złożoności czasowej i złożoności przestrzennej). Twoja strategia musi się gdzieś zacząć, od jakiegoś konkretnego podproblemu i być może może się dostosować w oparciu o wyniki tych ocen. W ogólnym sensie „programowania dynamicznego”, możesz spróbować buforować te podproblemy, a bardziej ogólnie, unikać powracania do podproblemów z subtelnym rozróżnieniem, być może w przypadku wykresów w różnych strukturach danych. Bardzo często te struktury danych są rdzeniem, podobnie jak tablice lub tabele. Rozwiązania podproblemów można wyrzucić, jeśli już ich nie potrzebujemy).

[Wcześniej ta odpowiedź zawierała stwierdzenie dotyczące terminologii odgórnej i oddolnej; wyraźnie istnieją dwa główne podejścia zwane memoization i tabulation, które mogą być sprzeczne z tymi terminami (choć nie do końca). Ogólnym terminem używanym przez większość ludzi jest nadal „programowanie dynamiczne”, a niektórzy ludzie mówią „zapamiętanie” w odniesieniu do tego konkretnego podtypu „programowania dynamicznego”. Ta odpowiedź nie mówi, która jest odgórna i oddolna, dopóki społeczność nie znajdzie odpowiednich odniesień w artykułach naukowych. Ostatecznie ważne jest, aby zrozumieć rozróżnienie, a nie terminologię.]

Plusy i minusy

Łatwość kodowania

Memoizacja jest bardzo łatwa do zakodowania (generalnie możesz * napisać adnotację "memoizer" lub funkcję wrapper, która zrobi to automatycznie za ciebie) i powinna być twoją pierwszą linią podejścia. Wadą tabeli jest to, że musisz wymyślić porządek.

* (w rzeczywistości jest to łatwe tylko wtedy, gdy sam piszesz funkcję i / lub kodujesz w nieczystym / niefunkcjonalnym języku programowania ... na przykład, jeśli ktoś już napisał prekompilowaną fibfunkcję, koniecznie wykonuje ona rekursywne wywołania do siebie i nie możesz magicznie zapamiętać funkcji bez upewnienia się, że te rekurencyjne wywołania wywołują twoją nową zapamiętaną funkcję (a nie oryginalną niezapamiętywaną funkcję))

Rekurencyjność

Zwróć uwagę, że zarówno od góry do dołu, jak i od dołu do góry można zaimplementować za pomocą rekursji lub iteracyjnego wypełniania tabeli, chociaż może to nie być naturalne.

Praktyczne obawy

Przy zapamiętywaniu, jeśli drzewo jest bardzo głębokie (np. fib(10^6)), Zabraknie Ci miejsca na stosie, ponieważ każde opóźnione obliczenie musi zostać umieszczone na stosie, a będziesz miał ich 10 ^ 6.

Optymalność

Każde podejście może nie być optymalne czasowo, jeśli kolejność odwiedzania podproblemów nie jest optymalna, szczególnie jeśli istnieje więcej niż jeden sposób obliczenia podproblemu (zwykle buforowanie rozwiązałoby ten problem, ale teoretycznie jest możliwe, że buforowanie może nie w niektórych egzotycznych przypadkach). Memoizacja zwykle dodaje złożoność czasową do złożoności przestrzeni (np. W przypadku tworzenia tabel masz większą swobodę w odrzucaniu obliczeń, na przykład używanie tabelowania z Fib pozwala na użycie przestrzeni O (1), ale zapamiętywanie z Fib wykorzystuje O (N) miejsce na stosie).

Zaawansowane optymalizacje

Jeśli również wykonujesz niezwykle skomplikowane problemy, możesz nie mieć innego wyjścia, jak tylko dokonać zestawienia (lub przynajmniej wziąć bardziej aktywną rolę w kierowaniu zapamiętywaniem tam, gdzie chcesz). Również jeśli jesteś w sytuacji, w której optymalizacja jest absolutnie krytyczna i musisz ją zoptymalizować, tabulacja pozwoli ci dokonać optymalizacji, których zapamiętywanie nie pozwoliłoby ci zrobić w rozsądny sposób. Moim skromnym zdaniem w normalnej inżynierii oprogramowania żaden z tych dwóch przypadków nigdy się nie pojawia, więc użyłbym po prostu zapamiętywania („funkcji przechowującej odpowiedzi w pamięci podręcznej”), chyba że coś (na przykład miejsce na stosie) sprawia, że ​​konieczne jest tworzenie tabel ... chociaż technicznie, aby uniknąć przepalenia stosu, możesz 1) zwiększyć limit rozmiaru stosu w językach, które na to pozwalają, lub 2) zużyć stałą dodatkową pracę w celu wirtualizacji stosu (ick),

Bardziej skomplikowane przykłady

Podajemy tutaj szczególnie interesujące przykłady, które nie są tylko ogólnymi problemami DP, ale ciekawie rozróżniają zapamiętywanie i tabelowanie. Na przykład jedna formuła może być znacznie łatwiejsza niż druga lub może istnieć optymalizacja, która zasadniczo wymaga tabelowania:

• algorytm obliczania odległości edycji [ 4 ], interesujący jako nietrywialny przykład dwuwymiarowego algorytmu wypełniania tabel

DP odgórne i oddolne to dwa różne sposoby rozwiązania tych samych problemów. Rozważmy zapamiętane (z góry na dół) i dynamiczne (z dołu do góry) rozwiązanie do obliczania liczb Fibonacciego.

fib_cache = {}

def memo_fib(n):
  global fib_cache
  if n == 0 or n == 1:
     return 1
  if n in fib_cache:
     return fib_cache[n]
  ret = memo_fib(n - 1) + memo_fib(n - 2)
  fib_cache[n] = ret
  return ret

def dp_fib(n):
   partial_answers = [1, 1]
   while len(partial_answers) <= n:
     partial_answers.append(partial_answers[-1] + partial_answers[-2])
   return partial_answers[n]

print memo_fib(5), dp_fib(5)

Osobiście uważam, że zapamiętywanie jest o wiele bardziej naturalne. Możesz wziąć funkcję rekurencyjną i zapamiętać ją za pomocą procesu mechanicznego (najpierw wyszukaj odpowiedź w pamięci podręcznej i zwróć ją, jeśli to możliwe, w przeciwnym razie oblicz ją rekurencyjnie, a następnie przed powrotem zapisz obliczenia w pamięci podręcznej do wykorzystania w przyszłości), podczas gdy wykonując oddolne programowanie dynamiczne wymaga zakodowania kolejności, w której obliczane są rozwiązania, tak aby żaden „duży problem” nie był obliczany przed mniejszym problemem, od którego on zależy.

Kluczową cechą programowania dynamicznego jest występowanie nakładających się podproblemów . Oznacza to, że problem, który próbujesz rozwiązać, można podzielić na podproblemy, a wiele z tych podproblemów ma wspólne podproblemy. To jest jak „Dziel i rządź”, ale w końcu robisz to samo wiele, wiele razy. Przykład, którego używam od 2003 roku, ucząc lub wyjaśniając te kwestie: możesz obliczać liczby Fibonacciego rekurencyjnie.

def fib(n):
  if n < 2:
    return n
  return fib(n-1) + fib(n-2)

Użyj swojego ulubionego języka i spróbuj go obsługiwać fib(50). To zajmie bardzo, bardzo dużo czasu. Mniej więcej tyle samo czasu, ile on fib(50)sam! Jednak wykonywanych jest wiele niepotrzebnych prac. fib(50)zadzwoni fib(49)i fib(48), ale wtedy oba z nich zakończą połączenie fib(47), mimo że wartość jest taka sama. W rzeczywistości fib(47)zostanie obliczony trzykrotnie: przez bezpośrednie połączenie od fib(49), przez bezpośrednie połączenie od fib(48), a także przez bezpośrednie połączenie od innego fib(48), tego, który został wywołany przez obliczenie fib(49)... Więc widzisz, mamy nakładające się podproblemy .

Dobra wiadomość: nie ma potrzeby wielokrotnego obliczania tej samej wartości. Po obliczeniu raz, zapisz wynik w pamięci podręcznej, a następnym razem użyj wartości z pamięci podręcznej! To jest istota programowania dynamicznego. Możesz to nazwać „od góry do dołu”, „zapamiętywaniem” lub jakkolwiek chcesz. Takie podejście jest bardzo intuicyjne i bardzo łatwe do wdrożenia. Po prostu napisz najpierw rozwiązanie rekurencyjne, przetestuj je na małych testach, dodaj zapamiętywanie (buforowanie już obliczonych wartości) i --- bingo! --- gotowe.

Zwykle można również napisać równoważny program iteracyjny, który działa od dołu do góry, bez rekursji. W tym przypadku byłoby to bardziej naturalne podejście: pętla od 1 do 50 obliczająca wszystkie liczby Fibonacciego na bieżąco.

fib[0] = 0
fib[1] = 1
for i in range(48):
  fib[i+2] = fib[i] + fib[i+1]

W każdym interesującym scenariuszu rozwiązanie oddolne jest zwykle trudniejsze do zrozumienia. Jednak gdy już to zrozumiesz, zwykle uzyskasz znacznie jaśniejszy, duży obraz działania algorytmu. W praktyce, rozwiązując nietrywialne problemy, radzę najpierw napisać podejście odgórne i przetestować je na małych przykładach. Następnie napisz rozwiązanie oddolne i porównaj je, aby upewnić się, że otrzymujesz to samo. Najlepiej porównać oba rozwiązania automatycznie. Napisz małą procedurę, która generowałaby wiele testów, najlepiej - wszystkomałe testy do określonego rozmiaru --- i sprawdź, czy oba rozwiązania dają ten sam wynik. Następnie użyj rozwiązania oddolnego w środowisku produkcyjnym, ale zachowaj kod od góry do dołu, zakomentowany. Ułatwi to innym programistom zrozumienie tego, co robisz: kod oddolny może być dość niezrozumiały, nawet jeśli go napisałeś i nawet jeśli dokładnie wiesz, co robisz.

W wielu aplikacjach podejście oddolne jest nieco szybsze ze względu na narzut wywołań rekurencyjnych. Przepełnienie stosu może również stanowić problem w przypadku niektórych problemów i należy pamiętać, że może to w dużym stopniu zależeć od danych wejściowych. W niektórych przypadkach możesz nie być w stanie napisać testu, powodując przepełnienie stosu, jeśli nie rozumiesz wystarczająco dobrze programowania dynamicznego, ale któregoś dnia może się tak zdarzyć.

Istnieją problemy, w przypadku których podejście odgórne jest jedynym możliwym rozwiązaniem, ponieważ przestrzeń problemowa jest tak duża, że ​​nie jest możliwe rozwiązanie wszystkich podproblemów. Jednak „buforowanie” nadal działa w rozsądnym czasie, ponieważ dane wejściowe wymagają tylko ułamka podproblemów do rozwiązania - ale jest zbyt trudne, aby jednoznacznie zdefiniować, które podproblemy należy rozwiązać, a tym samym napisać dolną rozwiązanie. Z drugiej strony są sytuacje, w których wiesz, że będziesz musiał rozwiązać wszystkie podproblemy. W takim przypadku kontynuuj i używaj oddolnego.

Osobiście użyłbym górnego dołu do optymalizacji akapitu, czyli problemu optymalizacji zawijania tekstu (spójrz na algorytmy łamania linii Knutha-Plassa; przynajmniej TeX go używa, a niektóre programy Adobe Systems używają podobnego podejścia). Użyłbym oddolnego do szybkiej transformacji Fouriera .

Weźmy jako przykład serię Fibonacciego

1,1,2,3,5,8,13,21....

first number: 1
Second number: 1
Third Number: 2

Inaczej mówiąc,

Bottom(first) number: 1
Top (Eighth) number on the given sequence: 21

W przypadku pierwszych pięciu liczb Fibonacciego

Bottom(first) number :1
Top (fifth) number: 5 

Spójrzmy teraz na przykład rekurencyjnego algorytmu szeregów Fibonacciego

public int rcursive(int n) {
    if ((n == 1) || (n == 2)) {
        return 1;
    } else {
        return rcursive(n - 1) + rcursive(n - 2);
    }
}

Teraz, jeśli wykonamy ten program za pomocą następujących poleceń

rcursive(5);

jeśli przyjrzymy się dokładniej algorytmowi, aby wygenerować piątą liczbę, potrzebna jest trzecia i czwarta liczba. Tak więc moja rekursja faktycznie zaczyna się od góry (5), a następnie przechodzi do najniższych / najniższych liczb. To podejście jest w rzeczywistości podejściem odgórnym.

Aby uniknąć wielokrotnego wykonywania tych samych obliczeń, używamy technik programowania dynamicznego. Przechowujemy wcześniej obliczoną wartość i wykorzystujemy ją ponownie. Ta technika nazywa się zapamiętywaniem. Programowanie dynamiczne to coś więcej niż zapamiętywanie, które nie jest potrzebne do omówienia aktualnego problemu.

Odgórne

Przepiszmy nasz oryginalny algorytm i dodajmy zapamiętane techniki.

public int memoized(int n, int[] memo) {
    if (n <= 2) {
        return 1;
    } else if (memo[n] != -1) {
        return memo[n];
    } else {
        memo[n] = memoized(n - 1, memo) + memoized(n - 2, memo);
    }
    return memo[n];
}

I wykonujemy tę metodę w następujący sposób

   int n = 5;
    int[] memo = new int[n + 1];
    Arrays.fill(memo, -1);
    memoized(n, memo);

To rozwiązanie jest nadal odgórne, ponieważ algorytm zaczyna od najwyższej wartości i schodzi do dołu każdego kroku, aby uzyskać naszą najwyższą wartość.

Oddolne

Ale pytanie brzmi, czy możemy zacząć od dołu, na przykład od pierwszej liczby Fibonacciego, a następnie iść w górę. Przepiszmy to za pomocą tej techniki,

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

Teraz, jeśli przyjrzymy się temu algorytmowi, faktycznie zaczyna się od niższych wartości, a następnie przechodzi do góry. Jeśli potrzebuję piątej liczby Fibonacciego, w rzeczywistości obliczam pierwszą, potem drugą, trzecią aż do piątej liczby. Techniki te faktycznie nazywały się technikami oddolnymi.

Ostatnie dwa, algorytmy w pełni wypełniają wymagania programowania dynamicznego. Ale jeden jest odgórny, a drugi oddolny. Oba algorytmy mają podobną złożoność przestrzenną i czasową.

Programowanie dynamiczne jest często nazywane zapamiętywaniem!

1.Memoizacja jest techniką odgórną (zacznij rozwiązywać dany problem, rozkładając go na części), a programowanie dynamiczne jest techniką oddolną (zacznij rozwiązywać od trywialnego problemu podrzędnego w górę w kierunku danego problemu)

2.DP znajduje rozwiązanie, zaczynając od przypadku (-ów) bazowego (-ych) i przechodzi do góry. DP rozwiązuje wszystkie podproblemy, ponieważ robi to oddolnie

W przeciwieństwie do zapamiętywania, które rozwiązuje tylko potrzebne podproblemy

1. DP ma potencjał, aby przekształcić rozwiązania siłowe w czasie wykładniczym w algorytmy czasu wielomianowego.

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

Wręcz przeciwnie, Memoization musi pokryć (często znaczący) narzut z powodu rekursji.

Mówiąc prościej, memoizacja wykorzystuje podejście odgórne do rozwiązania problemu, tj. Zaczyna się od problemu podstawowego (głównego), a następnie dzieli go na podproblemy i rozwiązuje te podproblemy w podobny sposób. W tym podejściu ten sam problem podrzędny może wystąpić wiele razy i zużywać więcej cykli procesora, co zwiększa złożoność czasową. Podczas gdy w programowaniu dynamicznym ten sam problem podrzędny nie zostanie rozwiązany wiele razy, ale poprzedni wynik zostanie wykorzystany do optymalizacji rozwiązania.

Mówiąc po prostu podejście odgórne używa rekurencji do ponownego wywoływania problemów Sub,
podczas gdy podejście oddolne używa pojedynczego bez wywoływania żadnego, a zatem jest bardziej wydajne.

Poniżej znajduje się oparte na DP rozwiązanie problemu edycji odległości, które jest odgórne. Mam nadzieję, że pomoże to również w zrozumieniu świata programowania dynamicznego:

public int minDistance(String word1, String word2) {//Standard dynamic programming puzzle.
         int m = word2.length();
            int n = word1.length();


     if(m == 0) // Cannot miss the corner cases !
                return n;
        if(n == 0)
            return m;
        int[][] DP = new int[n + 1][m + 1];

        for(int j =1 ; j <= m; j++) {
            DP[0][j] = j;
        }
        for(int i =1 ; i <= n; i++) {
            DP[i][0] = i;
        }

        for(int i =1 ; i <= n; i++) {
            for(int j =1 ; j <= m; j++) {
                if(word1.charAt(i - 1) == word2.charAt(j - 1))
                    DP[i][j] = DP[i-1][j-1];
                else
                DP[i][j] = Math.min(Math.min(DP[i-1][j], DP[i][j-1]), DP[i-1][j-1]) + 1; // Main idea is this.
            }
        }

        return DP[n][m];
}

Możesz pomyśleć o jego rekurencyjnej implementacji w domu. Jest to całkiem dobre i wymagające, jeśli wcześniej nie rozwiązałeś czegoś takiego.

Top-Down : Śledzenie obliczonej wartości do tej pory i zwracanie wyniku, gdy warunek bazowy zostanie spełniony.

int n = 5;
fibTopDown(1, 1, 2, n);

private int fibTopDown(int i, int j, int count, int n) {
    if (count > n) return 1;
    if (count == n) return i + j;
    return fibTopDown(j, i + j, count + 1, n);
}

Oddolne : bieżący wynik zależy od wyniku podproblemu.

int n = 5;
fibBottomUp(n);

private int fibBottomUp(int n) {
    if (n <= 1) return 1;
    return fibBottomUp(n - 1) + fibBottomUp(n - 2);
}