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

13

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?

Anonimowy
źródło

Odpowiedzi:

9

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.

Yuval Filmus
źródło
Licznik byłby wtedy taki, że za każdym razem, gdy złożoność miejsca w zapamiętywaniu jest większa niż dane wejściowe (być może tylko> O (N)), istnieje szansa, że ​​programowanie dynamiczne nie pomoże. To znaczy, kiedy rzadko spotykasz tę samą sytuację.
edA-qa mort-ora-y
1
Zapamiętywanie! = Programowanie dynamiczne!
Raphael
1
Nie sądzę, że to mówimy, ale pytanie wskazuje na zmniejszenie złożoności czasu. Dynamiczne programowanie samo dzieli problem na części. Programowanie dynamiczne + zapamiętywanie to ogólny sposób na poprawę złożoności czasu tam, gdzie to możliwe .
edA-qa mort-ora-y
@ edA-qamort-ora-y: Racja. Myślę, że należy wyraźnie to zaznaczyć, ponieważ najwyraźniej PO myli / miesza koncepcje.
Raphael
8

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

fa(0)=0fa(1)=1fa(n+2))=fa(n+1)+fa(n), n0

fafa(n)fa(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 .

Raphael
źródło
Czy mówisz, że istnieją przypadki, w których programowanie dynamiczne doprowadzi do większej złożoności czasu, ale zapamiętywanie nie pomogłoby (a przynajmniej nie tak bardzo)? Czy masz jakieś przykłady? A może po prostu mówisz, że programowanie dynamiczne jest przydatne tylko w przypadku podzbioru problemów związanych z zapamiętywaniem?
svick,
@svick: Programowanie dynamiczne nie przyspiesza niczego per se, tylko jeśli rekurencja DP jest oceniana za pomocą zapamiętywania (co zwykle ma miejsce (!)). Ponownie: DP jest sposobem modelowania problemów w zakresie rekurencji, zapamiętywanie jest techniką przyspieszającą odpowiednie algorytmy rekurencyjne (bez względu na to, czy DP). Nie ma sensu porównywanie obu bezpośrednio. Oczywiście próbujesz modelować problem jako DP, ponieważ spodziewasz się, że zastosujesz zapamiętywanie, a zatem rozwiążesz go szybciej niż mogłyby to zrobić naiwne (r) podejścia. Ale punkt widzenia DP nie zawsze prowadzi również do najbardziej wydajnego algorytmu.
Raphael
Jeśli dostępnych jest wiele procesorów, programowanie dynamiczne znacznie poprawia wydajność w świecie rzeczywistym, ponieważ można równolegle łączyć części. W rzeczywistości nie zmienia to jednak złożoności czasu.
edA-qa mort-ora-y
@ edA-qamort-ora-y: Dotyczy to każdej rekurencji. Nie jest jednak jasne, czy powoduje to dobre przyspieszenie, ponieważ zapamiętywanie jest mniej wydajne w stosunku do granic procesora.
Raphael
Korekta: ewaluacja DP-nawroty naiwnie mogą być (dużo) szybsze niż brutalna siła; por. Tutaj .
Raphael