Kiedy mogę zastosować programowanie dynamiczne, aby zmniejszyć złożoność czasową mojego algorytmu rekurencyjnego?

Programowanie dynamiczne może skrócić czas potrzebny do wykonania algorytmu rekurencyjnego. Wiem, że programowanie dynamiczne może pomóc w zmniejszeniu złożoności czasowej algorytmów. Czy ogólne warunki są takie, że spełnienie algorytmu rekurencyjnego oznaczałoby, że zastosowanie programowania dynamicznego zmniejszy złożoność czasową algorytmu? Kiedy powinienem używać programowania dynamicznego?

Programowanie dynamiczne jest przydatne, ponieważ algorytm rekurencyjny wielokrotnie trafia w te same sytuacje (parametry wejściowe). Istnieje ogólna transformacja z algorytmów rekurencyjnych do programowania dynamicznego znanego jako zapamiętywanie , w której znajduje się tabela przechowująca wszystkie wyniki kiedykolwiek obliczone przez procedurę rekurencyjną. Gdy wywoływana jest procedura rekurencyjna dla zestawu danych wejściowych, które zostały już wykorzystane, wyniki są po prostu pobierane z tabeli. Zmniejsza to rekurencyjne Fibonacciego do iteracyjnego Fibonacciego.

Programowanie dynamiczne może być jeszcze mądrzejsze dzięki zastosowaniu bardziej szczegółowych optymalizacji. Na przykład, czasami nie ma potrzeby przechowywania całej tabeli w pamięci w danym momencie.

Jeśli chcesz przyspieszyć algorytm rekurencyjny, może być wystarczające zapamiętywanie . Jest to technika przechowywania wyników wywołań funkcji, aby przyszłe wywołania o tych samych parametrach mogły po prostu ponownie wykorzystać wynik. Ma to zastosowanie, jeśli (i tylko jeśli) twoja funkcja

• nie ma skutków ubocznych i
• zależy tylko od jego parametrów (tj. nie od niektórych stanów).

Zaoszczędzi ci czasu, jeśli (i tylko wtedy) funkcja będzie wywoływana z tymi samymi parametrami w kółko. Popularne przykłady to rekurencyjna definicja liczb Fibonacciego

$\qquad \begin{align} f(0) &= 0 \\ f(1) &= 1 \\ f(n+2) &= f(n+1) + f(n) \qquad ,\ n \geq 0 \end{align}$

$f$$f(n)$$f(n+1)$

Zauważ, że w przeciwieństwie do tego, zapamiętywanie jest prawie bezużyteczne w przypadku algorytmów takich jak sortowanie po scaleniu: zwykle kilka (jeśli w ogóle) częściowych list jest identycznych, a kontrole równości są kosztowne (sortowanie jest tylko nieco droższe!).

W praktycznych implementacjach sposób przechowywania wyników ma ogromne znaczenie dla wydajności. Używanie tabel skrótów może być oczywistym wyborem, ale może popsuć lokalizację. Jeśli parametrami są nieujemne liczby całkowite, tablice są naturalnym wyborem, ale mogą powodować ogromne obciążenie pamięci, jeśli użyjesz tylko niektórych pozycji. Zatem zapamiętywanie jest kompromisem między efektem a kosztem; to, czy się opłaca, zależy od konkretnego scenariusza.

Programowanie dynamiczne to zupełnie inna bestia. Dotyczy to problemów z nieruchomościami, które

• może być podzielony na podproblemy (prawdopodobnie na więcej niż jeden sposób),
• te podproblemy można rozwiązać niezależnie,
• (optymalne) rozwiązania tych podproblemów można łączyć z (optymalnymi) rozwiązaniami pierwotnego problemu i
• podproblemy mają tę samą właściwość (lub są trywialne).

Jest to zwykle (domyślnie) implikowane, gdy ludzie powołują się na zasadę optymalności Bellmana .

Teraz opisuje to tylko klasę problemów, które można wyrazić przez pewien rodzaj rekurencji. Ich ocena jest (często) skuteczna, ponieważ zapamiętywanie można zastosować z dużym efektem (patrz wyżej); zwykle mniejsze podproblemy występują jako część wielu większych problemów. Popularne przykłady to odległość edycji i algorytm Bellmana-Forda .