38 0 153KB
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