Jak rozpoznajesz problem jako odpowiedni do programowania dynamicznego?

19

Ostatnio czytałem o programowaniu dynamicznym. Chciałbym usłyszeć od kogoś, kto zaczął od zera, a teraz jest całkiem dobry w identyfikowaniu i rozwiązywaniu problemów z DP. Mam problemy z identyfikacją tych problemów jako DP i sformułowaniem zwięzłego rozwiązania.

Przeszedłem przez większość problemów DP dla początkujących i zasobów MIT itp

użytkownik110036
źródło

Odpowiedzi:

17

Pochodzę z fizyki, a więc z wielu matematyki. Łatwo dostrzegam problemy dobrze dopasowane do rozwiązań programowania rekurencyjnego / dynamicznego, znajdując podobieństwa z dowodem indukcyjnym .

Dowód indukcyjny składa się z dwóch części:

  • udowadniasz, że jeśli coś jest prawdziwe dla iteracji N, to dotyczy to również iteracji N + 1
  • udowodnisz, że dotyczy to iteracji 1

W programowaniu rekurencyjnym / programowaniu dynamicznym:

  • rozpoznajesz warunek wyjścia (na przykład sztywno podłączysz rozwiązanie dla iteracji 1)
  • obliczasz rozwiązanie dla iteracji N, biorąc pod uwagę rozwiązanie dla iteracji N-1

Tak więc, jak odpowiedzieli inni, jest to kwestia doświadczenia i wybrania wskazówek, ale możesz ponownie użyć innych umiejętności, aby cię poprowadzić. Następnie musisz zawsze mieć dwie części, o których wspomniałem: jeśli nie, to nie będzie działać.

Na przykład, aby wygenerować wszystkie permutacje zestawu:

  • warunek wyjścia: jeśli masz tylko jeden element, zwróć go
  • rekurencja: permutacje zestawu N elementów to N zestawów permutacji, które otrzymujesz poprzez wybranie każdego elementu i połączenie ze wszystkimi zestawami N-1 (wielu) permutacji podzbioru, które otrzymujesz przez usunięcie elementu.
Sklivvz
źródło
8

Większość problemów z dynamicznym programowaniem można rozwiązać poprzez zapamiętywanie. Zapamiętywanie jest zwykle bardziej intuicyjne i łatwiejsze do kodowania. Pomocne może być myślenie w kategoriach zapamiętywania zamiast DP.

Zwykle łatwiej jest zrozumieć, czy problem jest odpowiedni do zapamiętywania (kroki są takie same jak odpowiedź Slivvza , ale myślę, że zmiana mentalna jest nieco krótsza). Jednak po rozwiązaniu problemu przez zapamiętywanie możesz sprawdzić, w jaki sposób pamięć podręczna jest zapełniana, a następnie wypełnić ją w kolejności, bez rekurencji ... co zmienia algorytm w algorytm programowania dynamicznego.

TL; DR; wersja: Łatwiej zrozumieć dynamiczne programowanie w zakresie zapamiętywania.

Zobacz także StackOverflow: Programowanie dynamiczne i zapamiętywanie: podejścia oddolne vs odgórne .

Brian
źródło
4

Programowanie dynamiczne to definitywnie dwie rzeczy:

  1. Optymalna podbudowa
    Większe rozwiązania można uzyskać z mniejszych rozwiązań; rozwiązywanie nie jest dwukierunkowe.

  2. Nakładające się na siebie podproblemy
    Małe rozwiązania zostaną ponownie wykorzystane wiele razy. Jeśli podproblemy w ogóle się nie pokrywają, nie zyskujesz na DP / zapamiętywaniu; co masz jest podział i przejęcie zamiast.

Ogólne podejście do problemów związanych z DP:

  • Napisz naiwną rekurencyjną lub iteracyjną wersję, która działa.

  • Zauważ, że funkcja wykonuje zbędną pracę.

  • Znajdź sposób na uniknięcie zbędnej pracy, często przez zapamiętywanie.

Jon Purdy
źródło
Wszystkie są prawdziwe z teoretycznego punktu widzenia. IMO potrzebuje trochę więcej praktyki, aby lepiej poznać szybką identyfikację :)
user110036
2

Nigdy nie wdrożyłem ani jednego dynamicznego solvera programistycznego - moim doświadczeniem jest matematyka / fizyka / obliczenia numeryczne, a nie CS - jeszcze kilka lat temu, kiedy zacząłem robić problemy z Project Euler . Rozwiązane tam problemy DP (np. 76 , 158 , 161 , 242, ale jest ich o wiele więcej), okazało się być moim ulubionym rodzajem. Zdecydowanie lepiej radzisz sobie z rozpoznawaniem, kiedy będzie to przydatna technika: po prostu szukaj rzeczy, które wydają się być możliwe do rozwiązania za pomocą pewnego rodzaju rekurencyjnego, dzielącego i podbijającego podejścia, w którym można również oswoić eksplozję ścieżek wymagających do zbadania przez rozpoznanie powtarzających się podproblemów i ponowne wykorzystanie wcześniej obliczonych wyników; umiejętność zidentyfikowania minimalnego wektora stanu do zapamiętania - i co nieistotnej „historii” można usunąć - jest kluczowym krokiem.

czas
źródło