Programowanie dynamiczne

Problem wydawania reszty, programowanie dynamiczne (1) Rozwiązanie problemu wydawania reszty z wykorzystaniem programowania dynamicznego

Programowanie dynamiczne – technika projektowania algorytmów polegająca na rozwiązywaniu podproblemów i zapamiętywaniu ich wyników. W technice tej, podobnie jak w metodzie dziel i zwyciężaj, problem dzielony jest na mniejsze podproblemy. Wyniki rozwiązywania podproblemów są jednak zapisywane w tabeli, dzięki czemu w przypadku natrafienia na ten sam podproblem nie trzeba go ponownie rozwiązywać.

Wykorzystując programowanie dynamiczne można zastosować metodę zstępującą z zapamiętywaniem lub metodę wstępującą.

  • Metoda zstępująca z zapamiętywaniem polega na rekurencyjnym wywoływaniu funkcji z zapamiętywaniem wyników. Metoda ta jest podobna do metody dziel i zwyciężaj – różni się od niej tym, że jeśli rozwiązanie danego problemu jest już w tabeli z wynikami, to należy je po prostu stamtąd odczytać.
  • Metoda wstępująca polega na rozwiązywaniu wszystkich możliwych podproblemów, zaczynając od tych o najmniejszym rozmiarze. Wówczas w momencie rozwiązywania podproblemu na pewno są już dostępne rozwiązania jego podproblemów. W tym podejściu nie zużywa się pamięci na rekurencyjne wywołania funkcji. Może się jednak okazać, że część podproblemów została rozwiązana nadmiarowo (nie były one potrzebne do rozwiązania głównego problemu).

Własność optymalnej podstruktury

Programowanie dynamiczne jest stosowane do rozwiązywania problemów, które wykazują własność optymalnej podstruktury. Własność ta oznacza, że optymalne rozwiązanie problemu jest funkcją optymalnych rozwiązań podproblemów (czyli znając optymalne rozwiązania podproblemów można efektywnie wyznaczyć rozwiązanie problemu).

Przykłady algorytmów

Przykładowe algorytmy oparte na programowaniu dynamicznym to:

Zobacz też

Bibliografia

  • T.H. Cormen, Ch.E. Leiserson, R.L. Rivest, C. Stein, Wprowadzenie do algorytmów, Wydawnictwo Naukowe PWN, Warszawa, 2012, ISBN 9788301169114.
Ocena: 0 Tak Nie
Liczba głosów: 6.

Dodano: 1 lipca 2017 14:22, ostatnia edycja: 30 stycznia 2019 15:52.

REKLAMA

Zobacz też

K-opt, algorytm k-optymalny – algorytm lokalnej optymalizacji wykorzystywany przy rozwiązywaniu problemu komiwojażera. Algorytm ten nie służy do samego wyznaczania trasy, a jedynie do ulepszania jej. Najprostszą wersją tego algorytmu jest algorytm 2-optymalny.

→ Czytaj całość

Minimalne drzewo rozpinające (ang. minimum spanning tree, w skrócie MST), inaczej drzewo rozpinające o minimalnej wadze – drzewo łączące wszystkie wierzchołki pewnego grafu spójnego mające najmniejszą możliwą sumę wag krawędzi.

Jeśli graf ma v wierzchołków, to jego drzewo rozpinające zawsze będzie miało v-1 krawędzi. Jeśli ten graf ma e krawędzi, aby utworzyć drzewo rozpinające, trzeba usunąć z grafu e-v+1 krawędzi. Liczba ta jest określana jako liczba cyklomatryczna.

→ Czytaj całość

2-opt, algorytm 2-optymalny – algorytm lokalnej optymalizacji wykorzystywany przy rozwiązywaniu problemu komiwojażera. Jest to szczególny przypadek algorytmu k-optymalnego.

Algorytm 2-opt nie służy do wyznaczania trasy, a jedynie do ulepszania jej. Samą trasę można wyznaczyć np. za pomocą algorytmu najbliższego sąsiada. Algorytm może być wykorzystany do ulepszenia algorytmu genetycznego – w ten sposób powstanie algorytm memetyczny.

→ Czytaj całość
Polityka prywatnościKontakt