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?
Odpowiedzi:
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:
(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.
fib(100)
, po prostu wywołałbyś to, a on zadzwoniłbyfib(100)=fib(99)+fib(98)
, który wywołałbyfib(99)=fib(98)+fib(97)
, ... itd ..., który zadzwonifib(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.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.
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).(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ą
fib
funkcję, 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:
źródło
python memoization decorator
; niektóre języki pozwolą ci napisać makro lub kod, który zawiera wzór zapamiętania. Wzorzec zapamiętywania to nic innego jak „zamiast wywoływać funkcję, wyszukaj wartość z pamięci podręcznej (jeśli wartości nie ma, oblicz ją i najpierw dodaj do pamięci podręcznej)”.fib(513)
. Przeładowana terminologia, którą uważam, przeszkadza. 1) Zawsze możesz wyrzucić podproblemy, których już nie potrzebujesz. 2) Zawsze możesz uniknąć obliczania podproblemów, których nie potrzebujesz. 3) 1 i 2 mogą być znacznie trudniejsze do zakodowania bez jawnej struktury danych do przechowywania podproblemów, LUB, trudniej, jeśli przepływ sterowania musi splatać się między wywołaniami funkcji (możesz potrzebować stanu lub kontynuacji).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.
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.
źródło
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.
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 onfib(50)
sam! Jednak wykonywanych jest wiele niepotrzebnych prac.fib(50)
zadzwonifib(49)
ifib(48)
, ale wtedy oba z nich zakończą połączeniefib(47)
, mimo że wartość jest taka sama. W rzeczywistościfib(47)
zostanie obliczony trzykrotnie: przez bezpośrednie połączenie odfib(49)
, przez bezpośrednie połączenie odfib(48)
, a także przez bezpośrednie połączenie od innegofib(48)
, tego, który został wywołany przez obliczeniefib(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.
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 .
źródło
Weźmy jako przykład serię Fibonacciego
Inaczej mówiąc,
W przypadku pierwszych pięciu liczb Fibonacciego
Spójrzmy teraz na przykład rekurencyjnego algorytmu szeregów Fibonacciego
Teraz, jeśli wykonamy ten program za pomocą następujących poleceń
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.
I wykonujemy tę metodę w następujący sposób
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,
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ą.
źródło
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
DP ma potencjał, aby przekształcić rozwiązania siłowe w czasie wykładniczym w algorytmy czasu wielomianowego.
DP może być znacznie wydajniejszy, ponieważ jest iteracyjny
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.
źródło
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.
źródło
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:
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.
źródło
Top-Down : Śledzenie obliczonej wartości do tej pory i zwracanie wyniku, gdy warunek bazowy zostanie spełniony.
Oddolne : bieżący wynik zależy od wyniku podproblemu.
źródło