Programarea dinamica este o metoda de elaborare a algoritmilor care se aplica in general problemelor pentru care se cere determinarea unui optim in urma adoptarii unor decizii. Nu exista un criteriu pe baza caruia sa identificam cu siguranta o problema pentru rezolvarea careia trebuie sa utilizam metoda programarii dinamice, dar putem formula doua proprietati care sugereaza o solutie prin programare dinamica.
Primul capitol al acestei lucrari este redata o prezentare generala despre structura optimala si subproblemee superpozabile cat si despre alte operatii optimale.
In al doilea capitol sunt prezentati algoritmi de programare dinamica si trei principii fundamentale ale programarii dinamice.
Capitolul trei prezinta cateva metode de sortare, algoritmii divide et impera si tehnica divide et impera.
Programarea dinamica si cateva probleme de alocare unidimensionala, sunt prezentate in ultimul capitol al acestei lucrari.
PREZENTARE GENERALA 1. 1. Substructura optimala Problema data poate fi descompusa in subprobleme si solutia optima a problemei depinde de solutiile optime ale subproblemelor sale.
Acest criteriu nu indica neaparat o solutie prin programare dinamica, ar putea fi si un indiciu ca se poate aplica metoda Greedy sau metoda Divide et Impera.
1. 2. Subprobleme superpozabile Subproblemele problemei date nu sunt independente, ci se suprapun. Datorita faptului ca subproblemele problemei date se suprapun, deducem ca o abordare prin metoda Divide et Impera ar fi dezastruoasa din punctul de vedere al timpului de executie (datorita faptului ca problemele se suprapun se ajunge la rezolvarea repetata a aceleiasi subprobleme). Prin urmare, vom rezolva subproblemele o singura, data, retinand rezultatele intr-o structura de date suplimentara (de obicei un tablou). Rezolvarea unei probleme prin programare dinamica presupune urmatorii pasi: - Se identifica subproblemele problemei date. - Se alege o structura de date suplimentara, capabila sa retina solutiile subproblemelor. - Se caracterizeaza substructura optimala a problemei printr-o relatie de recurenta.
Pentru a determina solutia optima, se rezolva relatia de recurenta in mod bottom-up (se rezolva subproblemele in ordinea crescatoare a dimensiunii lor). In cele ce urmeaza vom exemplifica pas cu pas modul de rezolvare a problemelor prin metoda programarii dinamice.
1. 3. Inmultirea optimala a matricelor Fie n matrice A1, A2, ., An, de dimensiuni d0xd1, d1xd2, ., dn-1xdn. Produsul A1xA2x. xAn se poate calcula in diverse moduri, aplicand asociativitatea operatiei de inmultire a matricelor. Numim inmultire elementara inmultirea a doua elemente.
In functie de modul de parantezare difera numarul de inmultiri elementare necesare pentru calculul produsului A1xA2x. xAn. Determinati o parantezare optimala a produsului A1xA2x. xAn (costul parantezarii, adica numarul total de inmultiri elementare sa fie minim). Exemplu: Pentru n=3 matrice cu dimensiunile (10, 1000), (1000, 10) si (10, 100), produsul ...
EMIL CERCHEZ - "PROGRAMARE DINAMICA" - BUCURESTI, 1998
TUDOR SORIN - "METODA BACKTRACKING" - CRAIOVA, 1996
TUDOR SORIN - "ALGORITMI DE PROGRAMARE" - CRAIOVA, 1994
D. E. KNUTH - "TRATAT DE PROGRAMAREA CALCULATOARELOR. SORTARE SI CAUTARE"
VEGA. UNITBV. RO - "ALGORITMI DIVIDE ET IMPERA"
Pentru a descărca acest document,
trebuie să te autentifici in contul tău.
