Metode si Tehnici de programare - limbajul C++
Adrian Runceanu
Capitolul 11 - METODA PROGRAMĂRII DINAMICE
A.Consideratii teoretice
Metoda programarii dinamice este o tehnica care conduce la o solutie optima, intr-un timp de calcul de ordin polinomial.
Cu toate acestea, aceasta metoda nu se poate aplica la toate problemele ci numai acelora care indeplinesc anumite conditii.
Astfel obtinerea unei solutii este determinata de indeplinirea unor decizii d1, d2, …, dn, unde fiecare decizie depinde de deciziile luate deja si nu este unic determinata.
Pentru aplicarea metodei este necesara indeplinirea principiului optimalitatii: daca d1, d2, …, dn, este un sir optim de decizii care transforma starea initiala s0 in starea finala sn trecand prin starile intermediare s1, . . . , sn-1, atunci sirul de decizii d2, …, dn, este optim pentru s1 ca stare initiala si sn ca stare finala.
Dupa ce principiul a fost verificat, metoda consta in a scrie relatiile de recurenta corespunzatoare si a le rezolva. Aceste relatii sunt de doua tipuri:
- fiecare decizie di depinde de deciziile di+1, . . . , dn, aici aplicandu-se metoda inainte, iar deciziile se iau în ordinea dn, dn-1, . . . , d1;
- fiecare decizie di, depinde de deciziile d1, d2, …, di-1, aici aplicandu-se metoda înapoi, iar deciziile se iau în ordinea d1, d2, …, dn.
In programarea dinamica se rezolva problema combinand solutiile problemelor ca si la Divide et Impera Cand subproblemele contin subprobleme comune, in locul metodei Divide et Impera este mai avantajos sa aplicam metoda programarii dinamice.
B.Exemple de programe
C.Exercitii si teme
1. Sa se execute programele prezentate mai sus.
2. Determinarea existenţei drumurilor
Determinati daca intr-un graf G=(V, M) exista drum de la i0 la jj (pentru orice noduri initiale date) cunoscand matricea muchiilor M.
3. Algoritmul lui ROY-WARSHALL
Determinati costul tuturor drumurilor minime dintr-un graf orientat cu costuri atasate arcelor.