W tym samouczku dowiesz się, czym jest programowanie dynamiczne. Znajdziesz również porównanie między programowaniem dynamicznym a zachłannymi algorytmami do rozwiązywania problemów.
Programowanie dynamiczne to technika w programowaniu komputerowym, która pomaga efektywnie rozwiązywać klasę problemów, które mają nakładające się podproblemy i optymalną własność podstruktury.
Takie problemy wymagają wielokrotnego obliczania wartości tych samych podproblemów w celu znalezienia optymalnego rozwiązania.
Przykład programowania dynamicznego
Weźmy przypadek generowania sekwencji Fibonacciego.
Jeśli sekwencja to F (1) F (2) F (3)… F (50), jest zgodna z regułą F (n) = F (n-1) + F (n-2)
F (50) = F (49) + F (48) F (49) = F (48) + F (47) F (48) = F (47) + F (46)…
Zauważ, że istnieją nakładające się podproblemy, musimy obliczyć F (48), aby obliczyć zarówno F (50), jak i F (49). To jest dokładnie ten rodzaj algorytmu, w którym świeci programowanie dynamiczne.
Jak działa programowanie dynamiczne
Programowanie dynamiczne działa na zasadzie przechowywania wyników podproblemów tak, że gdy ich rozwiązania są potrzebne, są pod ręką i nie musimy ich ponownie przeliczać.
Ta technika przechowywania wartości podproblemów nazywana jest zapamiętywaniem. Zapisując wartości w tablicy, oszczędzamy czas na obliczenia podproblemów, z którymi już się spotkaliśmy.
var m = map (0 → 0, 1 → 1) function fib (n) jeśli klucza n nie ma na mapie mm (n) = fib (n - 1) + fib (n - 2) return m (n)
Programowanie dynamiczne przez zapamiętywanie jest podejściem odgórnym do programowania dynamicznego. Odwracając kierunek działania algorytmu, tj. Wychodząc od przypadku podstawowego i pracując w kierunku rozwiązania, możemy również zaimplementować programowanie dynamiczne w sposób oddolny.
funkcja fib (n) if n = 0 return 0 else var prevFib = 0, currFib = 1 powtórz n - 1 razy var newFib = prevFib + currFib prevFib = currFib currFib = newFib zwraca currentFib
Programowanie rekurencyjne a programowanie dynamiczne
Programowanie dynamiczne jest głównie stosowane w algorytmach rekurencyjnych. Nie jest to przypadek, większość problemów związanych z optymalizacją wymaga rekursji, a do optymalizacji używa się programowania dynamicznego.
Ale nie wszystkie problemy wykorzystujące rekursję mogą korzystać z programowania dynamicznego. O ile nie występują nakładające się podproblemy, jak w przypadku problemu sekwencji Fibonacciego, rekurencja może osiągnąć rozwiązanie tylko przy użyciu metody dziel i zwyciężaj.
To jest powód, dla którego algorytm rekurencyjny, taki jak sortowanie przez scalanie, nie może korzystać z programowania dynamicznego, ponieważ podproblemy nie nakładają się w żaden sposób.
Chciwe algorytmy a programowanie dynamiczne
Algorytmy Greedy są podobne do programowania dynamicznego w tym sensie, że oba są narzędziami optymalizacji.
Jednak zachłanne algorytmy szukają lokalnie optymalnych rozwiązań lub innymi słowy chciwego wyboru, w nadziei na znalezienie optymalnego globalnego. Dlatego chciwe algorytmy mogą odgadnąć, że wygląda to optymalnie w danym momencie, ale staje się kosztowne i nie gwarantuje globalnego optimum.
Z drugiej strony programowanie dynamiczne znajduje optymalne rozwiązanie dla podproblemów, a następnie dokonuje świadomego wyboru połączenia wyników tych podproblemów w celu znalezienia najbardziej optymalnego rozwiązania.
