Czy istnieje fundamentalna różnica między programowaniem dynamicznym od góry do dołu i od dołu do góry?
W szczególności, czy istnieje problem, który można rozwiązać oddolnie, ale nie odgórnie? Czy też podejście oddolne jest jedynie odwijaniem nawrotu w podejściu odgórnym?
Odpowiedzi:
Aby użyć metody oddolnej, musisz być w stanie skutecznie określić, co to jest „dno”, co zwykle oznacza, że potrzebujesz silnie ograniczonej przestrzeni problemów. Jeśli wiesz, jakie będą najniższe poziomy obliczeń i kolejność zależności w górę, warto iteracyjnie wykonywać je we właściwej kolejności i przechowywać te wyniki. Czynniki, naiwne Fibonacciego i relacja powtarzalności Eulera dla partycji są dobrymi przykładami problemów dopasowanych do tego podejścia.
Niektóre problemy nie mają łatwego do ustalenia porządku dna lub zależności dla obliczeń. Na przykład oceny pozycji w szachach są pożytecznie zapamiętywane według pozycji, a wynik oceny jest przechowywany, więc nie trzeba jej ponownie obliczać. Pozycje mogą się powtarzać na wielu poziomach drzewa wyszukiwania z powodu transpozycji transpozycji i powtórzeń, więc warto zapisać wyniki oceny. Ale nie ma sposobu, aby dowiedzieć się, jakie będą pozycje na najniższych poziomach drzewa bez rekurencyjnego schodzenia (i biorąc pod uwagę przycinanie pośrednie), więc odgórne podejście jest naprawdę jedynym wykonalnym podejściem.
Podejście odgórne: jest to bezpośrednie wyjście z rekurencyjnego sformułowania dowolnego problemu. Jeśli rozwiązanie dowolnego problemu można sformułować rekurencyjnie, stosując rozwiązanie jego podproblemów, a jeśli podproblemy się pokrywają, wówczas można łatwo zapamiętać lub zapisać rozwiązania podproblemów w tabeli. Ilekroć próbujemy rozwiązać nowy podproblem, najpierw sprawdzamy tabelę, aby sprawdzić, czy jest on już rozwiązany. Jeśli rozwiązanie zostało zarejestrowane, możemy go użyć bezpośrednio, w przeciwnym razie rozwiązujemy podproblem i dodamy jego rozwiązanie do tabeli.
Podejście oddolne: po rekurencyjnym sformułowaniu rozwiązania problemu, tak jak w przypadku jego podproblemów, możemy spróbować przeformułować problem w sposób oddolny: najpierw spróbuj rozwiązać podproblemy i użyj ich rozwiązań, aby zbudować- i znajdź rozwiązania dla większych pod-problemów. Zwykle odbywa się to również w formie tabelarycznej poprzez iteracyjne generowanie rozwiązań dla coraz większych pod-problemów za pomocą rozwiązań dla małych pod-problemów. Na przykład, jeśli znamy już wartości F41 i F40, możemy bezpośrednio obliczyć wartość F42.