Czytaj więcej"/> Drukuj
Podstawą techniki programowania dynamicznego jest podział danego problemu na podproblemy względem określonych parametrów dynamicznych. Na ogół jednym z tych parametrów jest ilość elementów znajdujących się w rozpatrywanym podzbiorze problemu, drugim jest pewna wartość liczbowa, zmieniająca się w zakresie od 0 do największej wartości liczbowej występującej w problemie.
Gdy zostanie już ustalony podział na podzbiory, należy znaleźć funkcję rekurencyjną opisującą zależność rozwiązania podproblemu dla ustalonych parametrów dynamicznych od jednego z podproblemów już wcześniej rozwiązanych (takiego, w którym rozpatrywany podzbiór był mniejszy), przy czym rozwiązania każdego kolejnego podproblemu umieszcza się w tablicy zaalokowanej w pamięci operacyjnej, dzięki czemu wywołanie rekurencyjne może zostać zastąpione odwołaniem do odpowiednich komórek wspomnianej tablicy. Rozwiązanie ostatniego z rozpatrywanych podproblemów jest na ogół wartością rozwiązania zadanego problemu.
W praktyce często technika programowania dynamicznego jest wykorzystywana jako algorytm pseudowielomianowy służący do rozwiązywania problemów należących do klasy problemów NP-trudnych, które nie są jednocześnie silnie NP-trudne. Z reguły jest łączona z metodą backtrakingu, służącą do selekcji elementów, które tworzą rozwiązanie problemu. Backtracking polega na wstecznym przeglądaniu tablicy wygenerowanej przez algorytm programowania dynamicznego w celu wskazania podproblemów, które były brane pod uwagę, przy tworzeniu rozwiązania końcowego, dzięki czemu można stwierdzić, czy rozpatrywany element był uwzględniany w rozwiązaniu optymalnym, czy nie.
Programowanie dynamiczne może być również wykorzystywane jako alternatywna metoda rozwiązywania problemów zaliczanych do klasy P, o ile złożoność algorytmu wielomianowego nie jest satysfakcjonująca, a w praktyce, nawet dla dużych instancji problemu, wartości liczbowe występujące w problemie są niewielkie.
Na przykład, w przypadku problemu plecakowego jako parametry dynamiczne w metodzie programowania dynamicznego należy przyjąć rozmiar kolejno rozpatrywanych podzbiorów elementów oraz rozmiar plecaka, zmieniający się od 0 do wartości B danej w problemie.
Materiał wydrukowany z portalu zgapa.pl dnia 2020-08-08 08:39:32