PROGRAMOWANIE DYNAMICZNE: CHARAKTERYSTYKA, PRZYKŁAD, ZALETY, WADY - TECHNOLOGIA - 2025

Programowania dynamicznego jest algorytmem modelu, który rozwiązuje problem złożony przez podzielenie go na podproblemów, przechowywanie jej wyniki w celu uniknięcia konieczności ponownego obliczenia wyników.

Ten harmonogram jest używany, gdy masz problemy, które można podzielić na podobne podproblemy, aby można było ponownie wykorzystać ich wyniki. W większości ten harmonogram służy do optymalizacji.

Programowanie dynamiczne. Podproblemy nałożone w ciągu Fibonacciego. Źródło: Wikimedia commons, en: User: Dcoatzee, śledzone przez użytkownika: Stannered / Public domain

Przed rozwiązaniem dostępnego podproblemu algorytm dynamiczny podejmie próbę zbadania wyników rozwiązanych wcześniej podproblemów. Rozwiązania podproblemów są łączone w celu osiągnięcia najlepszego rozwiązania.

Zamiast w kółko obliczać ten sam podproblem, możesz przechowywać swoje rozwiązanie w jakiejś pamięci, kiedy po raz pierwszy napotkasz ten podproblem. Gdy pojawi się ponownie podczas rozwiązywania innego podproblemu, przyjęte zostanie rozwiązanie już zapisane w pamięci.

To wspaniały pomysł na naprawienie czasu pamięci, gdzie użycie dodatkowej przestrzeni może skrócić czas potrzebny na znalezienie rozwiązania.

Cechy programowania dynamicznego

Następujące podstawowe cechy są tym, z czym musisz mieć problem, zanim będzie można zastosować programowanie dynamiczne:

Optymalna podkonstrukcja

Ta cecha wyraża, że ​​problem optymalizacji można rozwiązać poprzez połączenie optymalnych rozwiązań składających się na niego problemów wtórnych. Te optymalne podstruktury są opisane przez rekurencję.

Na przykład na wykresie optymalna podkonstrukcja zostanie przedstawiona na najkrótszej ścieżce r, która prowadzi od wierzchołka s do wierzchołka t:

Oznacza to, że na tej najkrótszej ścieżce r można obrać dowolny pośredni wierzchołek i. Jeśli r jest naprawdę najkrótszą trasą, to można ją podzielić na podtrasy r1 (od s do i) i r2 (od i do t), w taki sposób, że są to z kolei najkrótsze trasy między odpowiednimi wierzchołkami.

Dlatego, aby znaleźć najkrótsze ścieżki, rozwiązanie można łatwo sformułować rekurencyjnie, co robi algorytm Floyda-Warshalla.

Nakładające się podproblemy

Przestrzeń podproblemu musi być mała. Oznacza to, że każdy algorytm rekurencyjny, który rozwiązuje problem, będzie musiał w kółko rozwiązywać te same podproblemy, zamiast generować nowe podproblemy.

Na przykład, aby wygenerować szereg Fibonacciego, można wziąć pod uwagę to sformułowanie rekurencyjne: Fn = F (n - 1) + F (n - 2), przyjmując jako podstawowy przypadek, że F1 = F2 = 1. Wtedy otrzymamy: F33 = F32 + F31 i F32 = F31 + F30.

Jak widać, F31 jest przekształcane na rekurencyjne poddrzewa zarówno F33, jak i F32. Chociaż całkowita liczba podproblemów jest naprawdę niewielka, jeśli zastosujesz rozwiązanie rekurencyjne, takie jak to, w końcu rozwiążesz te same problemy w kółko.

Uwzględnia to programowanie dynamiczne, więc każdy podproblem rozwiązuje tylko raz. Można to osiągnąć na dwa sposoby:

Podejście odgórne

Jeśli rozwiązanie jakiegoś problemu można sformułować rekurencyjnie przy użyciu rozwiązania jego podproblemów i jeśli te podproblemy nakładają się na siebie, wówczas rozwiązania podproblemów można łatwo zapamiętać lub przechowywać w tabeli.

Za każdym razem, gdy wyszukiwane jest nowe rozwiązanie podproblemu, w tabeli sprawdzane jest, czy zostało ono wcześniej rozwiązane. Jeśli rozwiązanie jest przechowywane, zostanie użyte zamiast obliczać je ponownie. W przeciwnym razie podproblem zostanie rozwiązany, zapisując rozwiązanie w tabeli.

Podejście oddolne

Po rekurencyjnym sformułowaniu rozwiązania problemu w kategoriach jego podproblemów, można podjąć próbę przeformułowania problemu w sposób rosnący: najpierw spróbujemy rozwiązać podproblemy i użyć ich rozwiązań, aby znaleźć rozwiązania większych podproblemów.

Odbywa się to również na ogół w formie tabeli, iteracyjnie generując rozwiązania dla większych i większych podproblemów przy użyciu rozwiązań mniejszych podproblemów. Na przykład, jeśli wartości F31 i F30 są już znane, wartość F32 można obliczyć bezpośrednio.

Porównanie z innymi technikami

Jedną z istotnych cech problemu, który może zostać rozwiązany przez programowanie dynamiczne, jest to, że powinno ono zawierać nakładające się podproblemy. To właśnie odróżnia programowanie dynamiczne od techniki dziel i rządź, w której nie jest konieczne przechowywanie najprostszych wartości.

Jest to podobne do rekurencji, ponieważ przy obliczaniu przypadków podstawowych ostateczną wartość można określić indukcyjnie. To podejście oddolne sprawdza się dobrze, gdy nowa wartość zależy tylko od wcześniej obliczonych wartości.

Przykład

Minimalne kroki do osiągnięcia 1

Dla każdej dodatniej liczby całkowitej „e” można wykonać dowolny z poniższych trzech kroków.

- Odejmij 1 od liczby. (e = e-1).

- Jeśli jest podzielna przez 2, jest dzielona przez 2 (jeśli e% 2 == 0, to e = e / 2).

- Jeśli jest podzielna przez 3, to dzieli się przez 3 (jeśli e% 3 == 0, to e = e / 3).

Na podstawie powyższych kroków należy ustalić minimalną liczbę tych kroków, która doprowadzi e do 1. Na przykład:

- Jeśli e = 1, wynik: 0.

- Jeśli e = 4, wynik: 2 (4/2 = 2/2 = 1).

- Gdy e = 7, wynik: 3 (7-1 = 6/3 = 2/2 = 1).

Skupiać

Można by pomyśleć o wybraniu zawsze kroku, który sprawia, że ​​n jest tak niskie, jak to możliwe i kontynuowaniu w ten sposób, aż osiągnie 1. Jednak widać, że ta strategia nie działa tutaj.

Na przykład, jeśli e = 10, kroki byłyby następujące: 10/2 = 5-1 = 4/2 = 2/2 = 1 (4 stopnie). Jednak optymalna forma to: 10-1 = 9/3 = 3/3 = 1 (3 kroki). Dlatego należy wypróbować wszystkie możliwe kroki, które można wykonać dla każdej znalezionej wartości n, wybierając minimalną liczbę tych możliwości.

Wszystko zaczyna się od rekurencji: F (e) = 1 + min {F (e-1), F (e / 2), F (e / 3)} jeśli e> 1, przyjmując jako podstawę: F (1) = 0. Mając równanie rekurencji, możesz zacząć kodować rekursję.

Można jednak zauważyć, że ma on nakładające się podproblemy. Ponadto optymalne rozwiązanie dla danego wejścia zależy od optymalnego rozwiązania jego podproblemów.

Podobnie jak w przypadku zapamiętywania, w którym rozwiązania podproblemów, które zostały rozwiązane, są przechowywane do późniejszego wykorzystania. Lub jak w programowaniu dynamicznym, zaczynasz od dołu, dochodząc do podanego e. Następnie oba kody:

Zapamiętanie

Dynamiczne programowanie oddolne

Korzyść

Jedną z głównych zalet korzystania z programowania dynamicznego jest to, że przyspiesza ono przetwarzanie, ponieważ używane są wcześniej obliczone odniesienia. Ponieważ jest to technika programowania rekurencyjnego, zmniejsza liczbę wierszy kodu w programie.

Żarłoczne algorytmy vs programowanie dynamiczne

Chciwe algorytmy są podobne do programowania dynamicznego, ponieważ są narzędziami optymalizacji. Jednak zachłanny algorytm szuka optymalnego rozwiązania na każdym lokalnym kroku. Oznacza to, że szuka chciwego wyboru w nadziei znalezienia globalnego optimum.

Dlatego chciwe algorytmy mogą przyjąć założenie, które wygląda optymalnie w danym momencie, ale staje się drogie w przyszłości i nie gwarantuje optymalnego globalnego.

Z drugiej strony programowanie dynamiczne znajduje optymalne rozwiązanie dla podproblemów, a następnie dokonuje świadomego wyboru, łącząc wyniki tych podproblemów w celu znalezienia najbardziej optymalnego rozwiązania.

Niedogodności

- Do przechowywania obliczonego wyniku każdego podproblemu potrzeba dużo pamięci, bez możliwości zagwarantowania, że ​​przechowywana wartość zostanie wykorzystana, czy nie.

- Wielokrotnie wartość wyjściowa jest przechowywana bez użycia jej w następujących podproblemach podczas wykonywania. Prowadzi to do niepotrzebnego wykorzystania pamięci.

- W programowaniu dynamicznym funkcje są wywoływane rekurencyjnie. Dzięki temu ilość pamięci stosu stale rośnie.

Programowanie rekurencyjne a programowanie dynamiczne

Jeśli masz ograniczoną pamięć do uruchamiania kodu, a szybkość przetwarzania nie jest problemem, możesz użyć rekursji. Na przykład, jeśli tworzysz aplikację mobilną, pamięć jest bardzo ograniczona do uruchomienia aplikacji.

Jeśli chcesz, aby program działał szybciej i nie miał ograniczeń dotyczących pamięci, lepiej jest użyć programowania dynamicznego.

Aplikacje

Programowanie dynamiczne jest skuteczną metodą rozwiązywania problemów, które w innym przypadku mogłyby wydawać się niezwykle trudne do rozwiązania w rozsądnym czasie.

Algorytmy oparte na paradygmacie programowania dynamicznego są wykorzystywane w wielu dziedzinach nauki, w tym w wielu przykładach w sztucznej inteligencji, od planowania rozwiązywania problemów po rozpoznawanie mowy.

Algorytmy oparte na programowaniu dynamicznym

Programowanie dynamiczne jest dość efektywne i działa bardzo dobrze w przypadku szerokiego zakresu problemów. Wiele algorytmów można postrzegać jako zachłanne aplikacje algorytmów, takie jak:

- Szeregi liczb Fibonacciego.

- Wieże Hanoi.

- Wszystkie pary krótszych tras przez Floyd-Warshall.

- Problem z plecakiem.

- Planowanie projektu.

- Najkrótsza droga przez Dijkstrę.

- Sterowanie lotem i sterowanie robotami.

- Matematyczne problemy optymalizacji.

- Timeshare: zaplanuj zadanie, aby zmaksymalizować wykorzystanie procesora.

Szeregi liczb Fibonacciego

Liczby Fibonacciego to liczby występujące w następującej kolejności: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 itd.

W terminologii matematycznej ciąg Fn liczb Fibonacciego jest określony wzorem powtarzalności: F (n) = F (n -1) + F (n -2), gdzie F (0) = 0 i F ( 1) = 1.

Podejście odgórne

W tym przykładzie tablica wyszukiwania ze wszystkimi wartościami początkowymi jest inicjowana z wartością -1. Zawsze, gdy potrzebne jest rozwiązanie podproblemu, ta macierz wyszukiwania będzie przeszukiwana jako pierwsza.

Jeśli obliczona wartość istnieje, zostanie ona zwrócona. W przeciwnym razie wynik zostanie obliczony i zostanie zapisany w tablicy wyszukiwania, aby można go było później ponownie wykorzystać.

Podejście oddolne

W tym przypadku dla tego samego szeregu Fibonacciego najpierw oblicza się f (0), a następnie f (1), f (2), f (3) i tak dalej. W ten sposób rozwiązania podproblemów budowane są oddolnie.

Bibliografia

1. Vineet Choudhary (2020). Wprowadzenie do programowania dynamicznego. Developer Insider. Zaczerpnięte z: developerinsider.co.
2. Alex Allain (2020). Programowanie dynamiczne w C ++. Programowanie C. Zaczerpnięte z: cprogramming.com.
3. Po Akademii (2020). Idea programowania dynamicznego. Zaczerpnięte z: afteracademy.com.
4. Aniruddha Chaudhari (2019). Programowanie dynamiczne i rekurencja - różnica, zalety na przykładzie. CSE Stack. Zaczerpnięte z: csestack.org.
5. Code Chef (2020). Samouczek do programowania dynamicznego. Zaczerpnięte z: codechef.com.
6. Programiz (2020). Programowanie dynamiczne. Zaczerpnięte z: programiz.com.