ALG#9

9.3. Programowanie dynamiczne 239

Wbrew pozorom nic jest to paradoks technika programowania dynamicznego bazuje właśnie na tym - zdawałoby się niemożliwym do zrealizowania - postulacie. Nadaje się ona szczególnie dobrze do rozwiązywania problemów o charakterze numerycznym:

•    obliczanie najkrótszej drogi w grafach (które poznamy szczegółowo w rozdziale 10);

•    wyliczenie pewnej skomplikowanej wartości podanej przy pomocy równania rekurencyjnego...

Konstrukcja programu wykorzystującego zasadę programowania dynamicznego może być sformułowana w trzech etapach:

koncepcja:

•    dla danego problemu P stwórz rekurencyjny model jego rozwiązania (wraz z jednoznacznym określeniem przypadków elementarnych);

•    stwórz tablicę, w której będzie można zapamiętywać rozwiązania przypadków' elementarnych i rozwiązania pod-problemów, które zostaną obliczone na ich podstawie;

inicjacja:

•    wpisz do tablicy wartości numeryczne, odpowiadające przypadkom elementarnym;

progresja:

•    na podstawie wartości numerycznych wpisanych do tablicy używając formuły rckurencyjnej, oblicz rozwiązanie problemu wyższego rzędu i wpisz je do tablicy:

•    postępuj w ten sposób do osiągnięcia pożądanej wartości.

Być może powyższy zapis brzmi enigmatycznie, ale jak to wyniknie z dalszych przykładów, metoda jest naprawdę nieskomplikowana. Zanim jednak przejdziemy do ilustracji tej techniki programowania, porównajmy ją z wcześniej poznaną metodą „dziel-i-rządź”.

„dziel-i-rządź”

•    problem rzędu N rozłóż na pod-problemy mniejszego „kalibru” i rozwiąż je;

•    połącz rozwiązania pod-problemów w- celu otrzymania rozwiązania globalnego.