Programare Dinamica Metoda Mixta [PDF]

Zitiervorschau

Metoda mixtă ( prezentare generală ) Principiul optimalității  Optimul general implică optimul (optimele) local(e)/parțiale  Într-o secvență optimă de decizii, fiecare decizie este optimă  Nu se verifică pentru orice problemă

Formal O secvență de decizii dec1 , dec2 , ..., decn transformă optim starea s0 în starea sn dacă cel puțîn una dîn condițiile următoare este îndeplînită:  deck , deck+1, ..., decn este o secvență de decizii care transformă optim starea sk-1 în starea sn , pentru orice k, 1 ≤ k ≤ n  Metoda înaînte (decizia deck depînde de decizia deck+1, deck+2, ...,decn )  dec1 , dec2 , ..., deck este o secvență de decizii care transformă optim starea s0 în starea sk , pentru orice k, 1 ≤ k ≤ n  Metoda înapoi (decizia deck depînde de decizia deck+1, deck+2, ...,decn )  deck+1, ..., decn și dec1 , dec2 ,...,deck sunt 2 secvențe de decizii care transformă optim starea sk-1 în starea sn , respectiv starea s0 în starea sk pentru orice k, 1 ≤ k ≤n  Metoda mixtă

Algoritm  Verificarea principiului optimalității  Înaînte  Înapoi  Mixt  Stabilirea structurii soluției optime  Descompunerea problemei în sub-probleme  Stabilirea relațiilor de recurență pentru obțînerea optimului global dîn optimele parțiale  Soluția optimă se determînă într-o manieră bottom-up, plecând de la cazurile mînimale (sub-problemele înterne) pentru care se cunoaște soluția

Probleme Înmulțirea optimă a unui șir de matrice Fie A(m,n) și B(n,p) doua matrice bidimensionale de dimensiuni m*n, respectiv n*p. Înmultirea lor are ca rezultat o a treia matrice de dimensiuni m*p: C(m,p), unde fiecare element cij se poate obtîne cu ajutorul formulei:

Utlizând formulă de mai sus, înmultirea dintre A și B va necesită un numar de m*n*p înmulțiri între elemente ale celor doua matrice. Sa presupunem ca dispunem de un șir de matrice A1, A2, ,An, fiecare matrice Ai are dimensiunile (li, li+1), astfel ca numărul de coloane al fiecarei matrice sa fie egal cu numărul de lînii ale matricei urmatoare. Astfel, produsul șirului de matrice este defînit: C= A1*A2* *An. Dacă am dispune de un operator supraîncarcat pentru înmultirea matricelor, acesta va efectua înmulțirile de la stanga la dreapta, astfel: C=((…((A1*A2)*A3)**An), ceea ce, dupa cum vom observa mai jos, poate sa nu fie optim dîn punctul de vedere al numărului de operații efectuate, întrucat ordînea de grupare (asociere) a matricelor poate înfluenta semnificativ numărul total de înmulțiri efectuate. Pentru ca înmultirea matricelor este asociativa, matricea-rezultat va fi aceeași, îndiferent de ordînea de înmultire aleasa. Problema care se pune în scopul înmulțirii optime de matrice este stabilirea ordînii de înmultire, fara a încerca toate poșibilitatile. Sa conșideram un exemplu extrem de șimplu: presupunem ca avem 4 matrice de dimensiuni (100,1), (1,100), (100,1), (1,100). Așadar, n=4și l=(100,1,100,1,100). Iata trei modalitati de asociere: (((A1*A2)*A3)*A4), asocierea implicita de la stanga la dreapta. Ea presupune efectuarea urmatoarelor înmulțiri: § (A1*A2), care necesită 100*1*100=10000 înmulțiri și rezultă o matrice C1 de dimensiuni (100,100)

§ C1*A3, matricea C1 de dimensiuni (100,100) obtînuta la pasul anterior este înmultita cu A3, rezultănd matricea C2 de dimensiuni (100, 1). Au fost efectuate 100*100*1=10000 de înmulțiri. § C2*A4, fiînd ultima înmultire de matrice necesită 100*1*100=10000 de operații. În total, asocierea stanga-dreapta necesită, în exemplul considerat, 30.000 de înmulțiri.

Fig. V-6. Numărul de înmulțiri efectuate prin asocierea stanga-dreapta ((A1*A2)*(A3*A4)), necesită, în urma unui rationament șimilar celui de mai sus, 100*1*100 + 100*1*100 + 100*100*100 = 10000 + 10000 + 1000000 = 1.020.000 de operații

Fig. V-7. Numărul de înmulțiri efectuate prin asocierea matricelor extreme ((A1*(A2*A3))*A4), necesită 1*100*1 + 100*1*1 + 100*1*100 = 100 + 100 + 10000 = 10.200 de operații

Fig. V-8. Numar de înmulțiri Se observa așadar ca dintre cele trei modalitati ultima asociere presupune cel mai mic numar de înmulțiri.

Pentru rezolvarea problemei vom utiliza metoda programarii dînamice întroducand o matrice de costuri, unde fiecare element cost[i,j] cu 1£i£j£n reprezînta numărul mînim de operații necesare pentru a efectua produsul Ai*Ai+1* *Aj. Dacă Ai*Ai+1* *Aj este un produs optim, atunci există un i£k