Dynamiczne cechy programowania, przykład, zalety, wady

Programowanie dynamiczne Jest to model algorytmu, który rozwiązuje złożony problem, dzieląc go na podproblemy, przechowując ich wyniki, aby uniknąć konieczności obliczania tych wyników.

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

Programowanie dynamiczne. Podprobaty nałożone na sukcesję Fibonacciego. Źródło: Wikimedia Commons, AT: Użytkownik: Dcoatzee, śledzony przez użytkownika: Stannered / Public Domena

Przed rozwiązaniem dostępnej podpuszczania podkładki algorytm dynamiczny spróbuje zbadać wyniki wcześniej rozwiązanych podproblemów. Rozwiązania podproblemów są łączone w celu osiągnięcia najlepszego rozwiązania.

Zamiast obliczać tę samą podprobą wielokrotnie, twoje rozwiązanie można przechowywać w jakiejś pamięci, kiedy pierwszy raz spełniasz tę podprobą. Kiedy pojawi się ponownie podczas rozwiązania innego podproblemu, rozwiązanie już zapisane w pamięci.

To wspaniały pomysł na skorygowanie czasu z pamięcią, gdzie podczas korzystania z dodatkowej przestrzeni możesz poprawić czas potrzebny na znalezienie rozwiązania.

[TOC]

Charakterystyka dynamicznego programowania

Poniższe podstawowe cechy to te, które można zastosować do programowania dynamicznego:

Optymalna podbudowa

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

Na przykład na wykresie optymalna podbudowa zostanie zaprezentowana na najkrótszej trasie, która przechodzi z wierzchołka do wierzchołka T:

To znaczy na tej najkrótszej trasie r możesz wziąć dowolny pośredni wierzchołek i. Jeśli R jest naprawdę najkrótszą drogą, można ją podzielić na Subrutas R1 (od S do I) i R2 (od I do T), aby z kolei były to najkrótsze trasy między odpowiednimi wierzchołkami.

Dlatego, aby znaleźć najkrótsze trasy, które można łatwo sformułować rozwiązanie rekurencyjnie, co robi algorytm Floyd-Warshall.

Nałożone podproblemy

Przestrzeń podproblemów musi być mała. Oznacza to, że każdy algorytm rekurencyjny, który rozwiązuje problem, musi w kółko rozwiązać te same podprony, zamiast generować nowe podproblemy.

Na przykład, aby wygenerować serię Fibonacciego, ten formuła rekurencyjna można rozważyć: fn = f (n-1) + f (n-2), przyjmując jako podstawowy przypadek, że f1 = f2 = 1. Wtedy będziesz musiał: f33 = f32 + f31 i f32 = f31 + f30.

Jak widać, F31 jest rozwiązywane w rekurencyjnych podwodach zarówno F33, jak i F32. Chociaż całkowita liczba podproblemów jest naprawdę niewielka, jeśli zostanie przyjęte rozwiązanie rekurencyjne, ponieważ będzie to rozwiązywać te same problemy.

Może ci służyć: 7 elementów systemu informacyjnego

Jest to brane pod uwagę przez programowanie dynamiczne, więc rozwiązuje każde podproblem. Można to osiągnąć na dwa sposoby:

Najlepsze podejście

Jeśli rozwiązanie jakiegokolwiek problemu można sformułować rekursywnie za pomocą rozwiązania ich podproblemów, a jeśli te podproblemki pokrywają się, wówczas roztwory podproblemów można łatwo zapamiętać lub przechowywać w tabeli w tabeli w tabeli.

Za każdym razem, gdy poszukiwane jest rozwiązanie nowej podpróbki, zostanie ono poddane przeglądowi w tabeli. W przypadku przechowywania rozwiązania będzie ono używane zamiast go ponownie obliczyć. W przeciwnym razie podprema zostanie rozwiązana, przechowując rozwiązanie w tabeli.

Podejście rosnące

Po rozwiązaniu problemu rekurencyjnie sformułowania pod względem podproblemów, problem można wypróbować w górę: najpierw spróbują rozwiązać podproblementy i użyć ich rozwiązań, aby osiągnąć rozwiązania największych podproblemów.

Zwykle odbywa się to również w postaci tabeli, generując iteracyjne rozwiązania coraz bardziej dużych podproblemów za pomocą rozwiązań dla małych 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

Znaczącym przynależnością problemu, który można rozwiązać przez programowanie dynamiczne, polega na tym, że powinien on mieć nakładające się podproblemy. To właśnie rozróżnia dynamiczne programowanie techniki podziału i podboju, gdzie nie jest konieczne przechowywanie najprostszych wartości.

Jest podobny do rekurencji, ponieważ poprzez obliczenie przypadków podstawowych, wartość końcową można określić indukcyjnie. To podejście rosnące działa dobrze, gdy nowa wartość zależy tylko od wcześniej obliczonych wartości.

Przykład

Minimalne kroki, aby osiągnąć 1

W przypadku dowolnej pozytywnej liczby całkowitej „e” możesz wykonać dowolny z następujących trzech kroków.

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

- Jeśli można go podzielić przez 2, jest dzielony przez 2 (jeśli e%2 == 0, to e = e/2).

- Jeśli można go podzielić przez 3, jest dzielony przez 3 (jeśli e%3 == 0, to e = e/3).

Na podstawie poprzednich kroków należy znaleźć minimalną ilość tych kroków do podjęcia i 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).

Zbliżać się

Możesz zawsze pomyśleć o wyborze kroku, który sprawia, że ​​n jest tak niskie, jak to możliwe i kontynuować, aż osiągnie 1. Można jednak zauważyć, że ta strategia nie działa tutaj.

Może Ci służyć: oprogramowanie komercyjne

Na przykład, jeśli e = 10, kroki wyniosłyby: 10/2 = 5-1 = 4/2 = 2/2 = 1 (4 kroki). Jednak optymalny sposób to: 10-1 = 9/3 = 3/3 = 1 (3 kroki). Dlatego należy udowodnić wszystkie możliwe kroki, które można wykonać dla każdej wartości N, wybierając minimalną ilość 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, biorąc jako przypadek podstawowy: f (1 ) = 0. Mając równanie nawrotów, możesz zacząć kodować rekurencję.

Można jednak zaobserwować, że nałożył podproblemki. Ponadto optymalne rozwiązanie dla danego wejścia zależy od optymalnego rozwiązania jego podproblemów.

Jak w zapamiętywaniu, gdzie rozwiązania rozdzielonych podproblemów są przechowywane, aby używać ich później. Lub jak w programowaniu dynamicznym, zaczyna się od dołu, przechodząc do danego E. Następnie oba kody:

Zapamiętanie

Dynamiczne programowanie w górę

Zalety

Jedną z głównych zalet stosowania dynamicznego programowania jest to, że przyspiesza przetwarzanie, ponieważ używane są odniesienia, które zostały wcześniej obliczone. Podobnie jak technika programowania rekurencyjnego, zmniejsza linie kodu programu.

Worace Algoritmos vs. programowanie dynamiczne

Żarłające algorytmy są podobne do programowania dynamicznego w tym sensie, że oba są narzędziami do optymalizacji. Jednak algorytm Voraz dąży do optymalnego rozwiązania na każdym etapie lokalnym. Oznacza to, że szuka chciwego wyboru z nadzieją na znalezienie globalnej optymalnej.

Dlatego żarłoczne algorytmy mogą przyjąć założenie, które w tym czasie wygląda optymalnie, ale w przyszłości staje się to drogie i nie gwarantuje globalnej optymalnej optymalnej.

Z drugiej strony programowanie dynamiczne znajduje optymalne rozwiązanie dla podproblemów, a następnie dokonuje świadomego wyboru, łącząc wyniki tych podproblemów, aby naprawdę znaleźć najbardziej optymalne rozwiązanie.

Niedogodności

- Potrzebne jest dużo pamięci do przechowywania obliczonego wyniku każdego podproblemu, bez możliwości upewnienia się, że wartość przechowywana będzie używana, czy nie.

- Wiele razy wartość wyjściowa jest przechowywana bez użycia w następujących podproblemach podczas wykonywania. To prowadzi do niepotrzebnego użycia pamięci.

- W programowaniu dynamicznym funkcje nazywane są rekurencyjnie. To sprawia, że ​​pamięć baterii pozostaje w stałym wzroście.

Rekurencyjność vs programowanie dynamiczne

Jeśli masz ograniczoną pamięć do wykonania kodu, a prędkość przetwarzania nie jest niepokojąca, można użyć rekurtyczności. Na przykład, jeśli opracowywana jest aplikacja mobilna, pamięć jest bardzo ograniczona do wykonania aplikacji.

Może ci służyć: urządzenia mieszane: cechy i przykłady

Jeśli program jest pożądany do wykonania szybciej i nie ma ograniczeń pamięci, preferowane jest użycie 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 dynamicznym paradygmacie programowania są wykorzystywane w wielu obszarach nauki, w tym w wielu przykładach sztucznej inteligencji, od rozwiązywania problemów z planowaniem po rozpoznawanie głosu.

Dynamiczne algorytmy programowania

Programowanie dynamiczne jest dość skuteczne i bardzo dobrze służy do szerokiego zakresu problemów. Wiele algorytmów można postrzegać jako zastosowania żarłocznych algorytmów, takich jak:

- Seria liczb Fibonacci.

- Hanoi Towers.

- Wszystkie najkrótsze trasy Floyd-Warshall.

- Plecak.

- Programowanie projektu.

- Najkrótsza ścieżka Dijkstra.

- Robotyka Kontrola i kontrola lotu.

- Problemy z optymalizacją matematyczną.

- Wspólny czas: Zaprogramuj pracę, aby zmaksymalizować korzystanie z procesora.

Seria liczb Fibonacci

Liczby Fibonacci są liczbami znalezionymi w następującej sekwencji: 0, 1, 1, 3, 5, 8, 13, 21, 34, 55, 89, 144 itp.

W terminologii matematycznej sukcesja FN Fibonacci jest zdefiniowana przez wzór nawrotu: f (n) = f (n -1) + f (n -2), gdzie f (0) = 0 i f (1) = 1.

Najlepsze podejście

W tym przykładzie macierz wyszukiwania ze wszystkimi wartościami początkowymi jest inicjowana z -1. Ilekroć wymagane jest rozwiązanie podproblemu, najpierw będzie poszukiwane w tej matrycy wyszukiwania.

Jeśli istnieje obliczona wartość, wartość ta zostanie zwrócona. W przeciwnym razie wynik zostanie obliczony w celu przechowywania go w matrycy wyszukiwania, a tym samym będzie w stanie go ponownie wykorzystać.

Podejście rosnące

W tym przypadku dla tej samej serii Fibonacci, f (0), a następnie f (1), f (2), f (3) i tak dalej, jest najpierw obliczane. Zatem zostaną zbudowane rozwiązania podproblemów od dołu.

Bibliografia

1. Vineet Choudhary (2020). Wprowadzenie do programowania dynamicznego. Insider Insveloper.Zaczerpnięte z: programisterinsider.współ.
2. Alex Allain (2020). Dynamiczne programowanie w c++. Programowanie C. Zaczerpnięte z: cprogrammming.com.
3. Po Akademii (2020). Pomysł dynamicznego programowania. Zaczerpnięte z: po akademii.com.
4. Aniruddha Chaudhari (2019). Dynamiczne programowanie i rekurencja | Różny. Stos CSE. Zaczerpnięte z: csestack.org.
5. Code Chef (2020). Do dynamicznego samouczka programowania. Zaczerpnięte z: Codhef.com.
6. Program (2020). Programowanie dynamiczne. Zaczerpnięte z: Programu.com.