algorytm.org

Programowanie dynamiczne



Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Programowanie dynamiczne
Ocena użytkowników:***** / 52
SłabyŚwietny 
Wpisany przez Michał Knasiecki, 01 sierpnia 2005 22:16

Metoda ta jest pewnym rozszerzeniem metody "dziel i zwyciężaj".
Jeżeli podproblemy, na które został podzielony problem główny, nie są niezależne to w różnych podproblemach wykonywane są wiele razy te same obliczenia, warto jest wtedy zastosować ulepszenie tej metody- programowanie dynamiczne. Wyniki obliczeń są zapamiętywane w tablicy pomocniczej, która jest wykorzystywana w kolejnych krokach algorytmu, co eliminuje potrzebę wielokrotnego wykonywania tych samych obliczeń. Prowadzi to do widocznego obniżenia złożoności obliczeniowej. Przykładem może być obliczanie symbolu Newtona. Rekurencyjna funkcja wyznaczająca ten współczynnik ma złożoność wykładniczą. Po zastosowaniu programowania dynamicznego złożoność maleje do O(n2). Programowanie dynamiczne polega więc na wykonania obliczeń każdego podproblemu tylko raz i zapamiętaniu jego wyniku w tabeli. W każdym kolejnym kroku można z tej tabeli korzystać. Programowanie dynamiczne jest zazwyczaj stosowane w rozwiązywaniu problemów optymalizacyjnych, prowadzi to często do wyznaczenia kilku równoznacznych, optymalnych rozwiązań. Taka metoda tworzenia algorytmów znalazła zastosowanie m.in. w rozwiązywaniu problemu plecakowego, w optymalnym mnożeniu ciągu macierzy. Jest także stosowana w automatach do kawy przy wydawaniu reszty w taki sposób, my monet było najmniej.
Zobacz przykład: Problem załadunku

Poprawiony: 11 lipca 2013 09:22
Komentarze
photo
+4 # Anonymous 2013-01-26 18:44
Świetnie wytłumaczone ! :)
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+2 # Ignacy 2015-02-10 11:40
Dzięki wielkie :)
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz