Plik Programowanie dynamiczne to model algorytmu, który rozwiązuje złożony problem, dzieląc go na podproblemy, przechowując ich wyniki, aby uniknąć konieczności ponownego przeliczania tych 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 to programowanie służy do optymalizacji.
Przed rozwiązaniem dostępnego podproblemu algorytm dynamiczny podejmie próbę zbadania wyników rozwiązanych wcześniej podproblemów. Rozwiązania podproblemowe są łączone, aby osiągnąć najlepsze rozwiązanie.
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 w trakcie rozwiązywania innego podproblemu, przyjęte zostanie rozwiązanie już zapisane w pamięci.
To wspaniały pomysł na naprawienie czasu pamięci, gdzie wykorzystując dodatkową przestrzeń można skrócić czas potrzebny na znalezienie rozwiązania..
Indeks artykułów
Następujące podstawowe cechy są tym, z czym musisz mieć problem, zanim będzie można zastosować programowanie dynamiczne:
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 podstruktura 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 rzeczywiście 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 trasy, rozwiązanie można łatwo sformułować rekurencyjnie, co robi algorytm Floyda-Warshalla..
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 będziesz rozwiązywać 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:
Jeśli rozwiązanie jakiegoś problemu można sformułować rekurencyjnie za pomocą rozwiązania jego podproblemów i jeśli te podproblemy nakładają się, to rozwiązania podproblemów można łatwo zapamiętać lub przechowywać w tabeli.
Za każdym razem, gdy szukane 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.
Po rekurencyjnym sformułowaniu rozwiązania problemu w kategoriach jego podproblemów, będzie można spróbować przeformułować problem w sposób rosnący: najpierw spróbujemy rozwiązać podproblemy i użyć ich rozwiązań do rozwiązania większych podproblemów.
Odbywa się to również na ogół w formie tabelarycznej, 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.
Istotną cechą problemu, który można rozwiązać dynamicznie, jest to, że powinien on 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 bazowych wartość końcową można określić indukcyjnie. To podejście oddolne działa dobrze, gdy nowa wartość zależy tylko od wcześniej obliczonych wartości.
Dla dowolnej dodatniej liczby całkowitej „e” można wykonać dowolny z następujących trzech kroków.
- Odejmij 1 od liczby. (e = e-1).
- Jeśli jest podzielna przez 2, podziel przez 2 (jeśli e% 2 == 0, to e = e / 2).
- Jeśli jest podzielna przez 3, podziel 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, aby uzyskać 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).
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żemy rozpocząć kodowanie rekurencji.
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.
Jak w zapamiętywaniu, gdzie 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:
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 programu.
Chciwe algorytmy są podobne do programowania dynamicznego, ponieważ są narzędziami do optymalizacji. Jednak zachłanny algorytm szuka optymalnego rozwiązania na każdym kroku lokalnym. Oznacza to, że szuka chciwego wyboru w nadziei znalezienia globalnego optimum..
Dlatego chciwe algorytmy mogą przyjąć założenie, które w danym momencie wygląda optymalnie, ale w przyszłości staje się kosztowne 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..
- Potrzeba dużo pamięci do przechowywania obliczonego wyniku każdego podproblemu, nie można zagwarantować, że przechowywana wartość zostanie wykorzystana lub 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 nazywane są rekurencyjnie. Dzięki temu ilość pamięci stosu stale rośnie.
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 masz ograniczeń dotyczących pamięci, lepiej jest użyć programowania dynamicznego.
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..
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.
- Hanoi Towers.
- Wszystkie najkrótsze pary tras od Floyd-Warshall.
- Problem z plecakiem.
- Planowanie projektu.
- Najkrótsza droga przez Dijkstrę.
- Sterowanie lotem i sterowanie robotami.
- Matematyczne problemy optymalizacji.
- Timesharing - zaplanuj zadanie, aby zmaksymalizować wykorzystanie procesora.
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.
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ć.
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 będą budowane oddolnie.
Jeszcze bez komentarzy