Scrigroup - Documente si articole

Username / Parola inexistente      

Home Documente Upload Resurse Alte limbi doc  


AccessAdobe photoshopAlgoritmiAutocadBaze de dateCC sharp
CalculatoareCorel drawDot netExcelFox proFrontpageHardware
HtmlInternetJavaLinuxMatlabMs dosPascal
PhpPower pointRetele calculatoareSqlTutorialsWebdesignWindows
WordXml


Metoda programarii dinamice

c

+ Font mai mare | - Font mai mic





DOCUMENTE SIMILARE

Trimite pe Messenger
Operatii cu liste liniare simple
Introducere in C++ - Extensii ale limbajului C++
Tablouri unidimensionale - Vectori
Initializarea pointerilor
Tipul enumerat
Caractere
Serviciile BIOS
Cauta maximul elementelor din lista
LISTE - Sortare prin selectie
Baze de numeratie

TERMENI importanti pentru acest document

Metoda programarii dinamice




Prezentarea metodei

Metoda programarii dinamice se aplica problemelor de optimizare in care solutia poate fi privita ca rezultatul unui sir de decizii din multimea deciziilor D = D0i = Dni.

Fie sistemul S cu multimea starilor X. Presupunem ca trecerea sistemului S dintr-o stare in alta are loc numai in urma unei decizii.

Un vector reprezinta o solutie si un vector reprezinta o politica a sistemului S. Un vector este o solutie partiala si un vector , este o subpolitica a sistemului S. Printre politicile care determina evolutia sistemului S dintr-o stare initiala x0 intr-o stare finala xn poate exista o politica care optimizeaza functia obiectiv. Aceasta politica se numeste politica optima si solutia determinata de politica optima se numeste solutie optima.

Principiul optimalitatii are urmatoarea formulare:

Daca este o solutie optima atunci oricare solutie partiala a sa este optima.

Deci programarea dinamica se poate aplica problemelor pentru care optimul total implica optimul partial.

Analiza de luare a deciziilor incepand cu starea initiala x0, continuand cu starile x1, x2, … si terminand cu starea finala xn se numeste analiza prospectiva. Analiza de luare a deciziilor incepand cu starea finala n, continuand cu starile xn-1, xn-2, … si terminand cu starea initiala x0 se numeste analiza retrospectiva.

In analiza prospectiva, daca sistemul S se afla in starea xi-1 si se ia decizia di I D0i(xi–1) atunci S trece in starea xi, i = 1,, n. Aceasta evolutie poate fi descrisa prin relatiile:

xi = t0i(xi-1, di), di I D0i(xi-1), i = 1,,n

Fie u0i(xi, di) utilitatea trecerii sistemului S de la starea xi–1, la starea xi, i = 1,…,n. Utilitatea totala este functia f0n(u01,…,u0n) si reprezinta functia obiectiv. Consideram cazul aditiv f0n(u01,…,u0n) = u01 u0n si f0i(u0 n–i+1, …, u0n) = u­0 n-i+1 + f0i–1(u0 n–i+2, …, u0n), i=1,…,n, f00(u0 n+1) = 0. Tinand seama de relatiile xi = t0i(xi-1, di), i = 1,…,n, obtinem

Consideram problema de optimizare:

unde optimul este determinat in conditiile xj = t0j(xj-1, dj), dj ID0j(xj-1), j = n–i+1, …, n, i = 1, …, n.

Teorema 4.6

Pentru i = 1, …, n exista relatiile

(4.1)

unde si optimul se determina dupa toate deciziile dn-i+1 din D0 n-i+1(xn-i).

Ecuatiile (4.1) se numesc ecuatiile de recurenta ale programarii dinamice in analiza prospectiva.

In analiza retrospectiva, daca sistemul S se afla in starea xi si se ia decizia di I Dni(xi) atunci sistemul S trece in starea xi-1. Aceasta evolutie poate fi descrisa prin relatiile:

xi-1 = tni(xi, di), di I Dni(xi), i = 1, …, n

Fie uni(xi, di) utilitatea trecerii sistemului S de la starea xi la starea xi-1. Utilitatea totala este o functie fnn (un1, …, unn) si reprezinta functia obiectiv. Consideram cazul aditiv fnn (un1, …, unn) = un1 + … + unn si fni(un1, …, uni) = fni-1 (un1 + … + un i-1) + uni, i = 1, …, n, fn0 (un0) = 0. Tinand seama de relatiile xi-1 = tni (xi, di), i = 1, …, n, obtinem:

Consideram problema de optimizare:

unde optimul este determinat in conditiile xj-1 = tnj (xj, dj), dj I Dnj (xj), j = 1,…,i; i = 1,…,n

Teorema 4.7

Pentru i=1,…,n exista relatiile

, (4.2)

unde si optimul se ia dupa toti di din Dni(xi).

Ecuatiile (4.2) se numesc ecuatii de recurenta ale programarii dinamice in analiza retrospectiva.

Observatii

In relatiile de mai sus avem D0i = Dni si u0i (xi, di) = uni (xi, di), 1 i n, f0n = fnn. S-au facut notatii diferite cu scopul de a pune in evidenta analiza prospectiva respectiv retrospectiva.

Rezolvarea unei probleme cu metoda programarii dinamice consta in urmatoarele :

verificarea valabilitatii principiului de optimalitate;

stabilirea ecuatiilor de recurenta;

rezolvarea ecuatiilor de recurenta.

Probleme rezolvate

Problema PD1

Problema discreta a rucsacului.

O persoana are un rucsac care poate transporta o greutate maxima gr. Persoana are la dispozitie n obiecte nedivizibile (un obiect poate fi pus in rucsac numai in intregime) si se cunoaste pentru fiecare obiect i greutatea g(i) si beneficiul b(i) care se obtine in urma transportului sau la destinatie.Se cere sa se precizeze ce obiecte trebuie sa transporte persoana in asa fel incat beneficiul sa fie maxim. Se va avea in vedere si faptul ca pentru acelasi beneficiu persoana sa transporte o greutate mai mica.

Utilizam metoda retrospectiva (metoda inapoi) a programarii dinamice. Datele problemei sunt urmatoarele:

gr reprezinta greutatea maxima care poate fi transportata de rucsac;

o=(1, , n) reprezinta vectorul obiectelor nedivizibile;

g=(g(1), , g(n)) reprezinta vectorul greutatilor obiectelor;

b=(b(1), , b(n)) reprezinta vectorul beneficiilor obiectelor.

Punerea sau nu a obiectului i in rucsac reprezinta etapa i, i=1, , n. In program folosim si notatiile:

bm(j) reprezinta beneficiul maxim daca se transporta j unitati de greutate j=1, , gr, luand in calcul primele etape;

be(j) reprezinta beneficiul obtinut pentru j unitati de greutate la etapa i;

sm(j) reprezinta multimea obiectelor corespunzatoare beneficiului bm(j)

se(j) reprezinta multimea obiectelor corespunzatoare beneficiului be(j).

Rezulta ca:

bm(g(1))=b(1), sm(g(1))=, bm(j)=0, sm(j)= Ø, jI

bm(j+g(i))=max,

sm(j+g(i))=se(j),

jI, iI

bt reprezinta beneficiul total;

gt reprezinta greutatea totala.

Algoritmul este prezentat in continuare:

PROGRAM PDR;

BEGIN

READ gr, n, (g(i), b(i), i:=1 TO n);

FOR j := 1 TO gr DO

bm(j):=0; sm(j):=

ENDFOR;

bm(g(1)):=b(1); sm(g(1)):=;

FOR i:=2 TO n DO

be:=bm; se:=sm;

IF be(g(i))<b(i)

THEN bm(g(i)):=b(i); sm(g(i)):=;

ENDIF;

FOR j:=1 TO gr-g(i) DO

IF be(j)≠0

THEN IF be(j+g(i))<be(j)+b(i)

THEN bm(j+g(i)):=be(j)+b(i);

sm(j+g(i)):=se(j)

ENDIF

ENDFOR

ENDFOR

bt:=bm(1); gt:=1;

FOR j:=2 TO gr DO

IF bm(j)>bt

THEN bt:=bm(j); gt:=j;

ENDIF;

ENDFOR;

WRITE bt, gt, sm(gt);

END.

Problema PD2

Problema distantei si drumului minim intre oricare doua noduri ale unei retele orientate G = (N, A, b).

Fie digraful G = (N, A) cu N = multimea nodurilor si A = multimea arcelor. Consideram functia valoare b : A R. Aceasta functie poate fi functia lungime sau functia cost. Digraful G = (N, A) pe care s-a definit functia valoare b se numeste retea orientata si se noteaza G = (N, A, b).

Vom nota cu Dijk un drum, in digraful G = (N, A), de la nodul i la nodul j si cu Dij = multimea acestor drumuri. Valoarea unui drum Dijk = (a1, … , aq), notata b(Dijk), este b(Dijk) = b(a1) + … + b(aq). Un drum Dijp cu valoarea b(Dijp) = min se numeste drum de valoare minima sau drum minim. Valoarea b(Dijp) a drumului minim Dijp se numeste distanta de la nodul i la nodul j si o notam dij.

Exista doua probleme cu dificultati privind notiunile de drum minim si distanta. Prima, poate sa nu existe drum de la nodul i la nodul j si a doua, poate exista drum Dijk cu valoare arbitrar de mica. Prima problema poate fi rezolvata daca consideram b(Dijp) = si dij = . A doua problema provine din posibilitatea existentei circuitelor cu valoare negativa in reteaua orientata G = (N, A, b). De exemplu, reteaua din figura 4.11 contine circuitul D = (2, 3, 4, 2) cu valoarea b(D

Figura 4.11

Drumurile D15k , k = 0, 1, …, sunt urmatoarele:

k

D15k

b (D15k)

D150 = (1, 2, 3, 5)

-1

D151 = (1, D

-2

D152 = (1, D , D

-3

. . .

. . .

In continuare, vom presupune ca reteaua G = (N, A, b) nu contine circuite cu valoare negativa.

Problema distantei si drumului minim intre oricare doua noduri ale unei retele orientate G = (N, A, b) consta in determinarea unui drum minim Dijp de la nodul i la nodul j si a distantei dij = b(Dijp) pentru toate nodurile i, j din N, in ipoteza ca reteaua orientata G = (N, A, b) nu contine circuite cu valoare negativa.

Pentru problemele de drum minim intr-o retea orientata G = (N, A, b) principiul optimalitatii este urmatorul:

Daca Dijp este un drum minim de la nodul i la nodul j, atunci oricare subdrum Dklp al sau este un drum minim de la nodul k la nodul l.

Intr-adevar, daca Dklp nu este drum minim, atunci exista un alt drum D klp cu valoarea b(D klp) < b(Dklp). Fie D ijp­ = Dikp D klp Dljp. Rezulta b (D ijp) = b(Dikp) + b(D klp) + b(Dljp) < b(Dikp) + b(Dklp) + b(Dljp) = b(Dijp). Aceasta relatie contrazice faptul ca Dijp este un drum minim de la nodul i la nodul j. Deci Dklp este drum minim de la nodul k la nodul l.

Conform principiului optimalitatii, drumul minim Dijp = (i, …, k, …, j) se poate exprima Dijp = Dikp Dkjp cu Dikp, Dkjp drumuri minime de la nodul i la nodul k si respectiv de la nodul k la nodul j. Aceasta exprimare conduce la urmatoarele ecuatii de recurenta:

Aceste ecuatii pot fi rezolvate cu algoritmul Floyd – Warshall.

Consideram reteaua orientata G = (N, A, b) reprezentata prin matricea valoare adiacenta B = (bij) nxn, i, j I N cu

Algoritmul Floyd – Warshall determina matricea distantelor D = (dij)nxn si matricea predecesor P = (pij)nxn.

PROGRAM FLOYD – WARSHALL

BEGIN

FOR i : = 1 TO n DO

FOR j := 1 TO n DO

dij := bij;

IF i j AND dij <

THEN piJ := i

ELSE pij := 0

ENDIF

ENDFOR;

ENDFOR;

FOR k := 1 TO n DO

FOR i := 1 TO n DO

FOR j := 1 TO n DO

IF dik + dkj < dij THEN

dij:= dik + dkj; pij:= pkj; END;

ENDIF;

ENDFOR;

ENDFOR;

ENDFOR

END.

Un drum minim Dijp de la nodul i la nodul j se determina cu algoritmul urmator:

PROGRAM DRUM;

BEGIN

k := n; xk := j;

WHILE xk i DO

XK-1:=;

k := k-1;

ENDWHILE;

END.

Drumul minim este Dijp = (xk, xk+1, …, xn-1, xn) = (i, xk+1, …, xn-1, j).

Propozitia

Algoritmul Floyd – Warshall determina matricea distantelor D si matricea predecesor P ale retelei orientate G = (N, A, b) cu b : A R si cu proprietatea ca oricare circuit are valoarea b(

Demonstratie

Fie D0, P0 matricele definite in liniile de la (3) la (11) si Dk, Pk matricele calculate in liniile de la (12) la (19) la iteratia k. Prin inductie dupa k aratam ca Dk = (dkij) este matricea valorilor drumurilor minime de la i la j avand nodurile interioare din . Pentru k = 0 avem D0 = B si afirmatia este evident adevarata. Presupunem afirmatia adevarata pentru k–1. Liniile (15), (16) la iteratia k sunt echivalente cu . Din ipoteza inductiva si principiul optimalitatii drumului minim rezulta ca este matricea valorilor drumurilor minime de la i la j avand nodurile interioare din . Deoarece oricare circuit are valoarea b( 0 si in conformitate cu cele precizate mai sus rezulta ca D = Dn este matricea distantelor. De asemenea, din modul cum se determina pij rezulta ca P = Pn este matricea predecesor cu ajutorul careia se determina drumurile minime Dijp.



Propozitia 4.2

Algoritmul Floyd – Warshall are complexitatea O (n3).

Demonstratie

Evident.   

Codul sursa al programului este:

#include<stdio.h>

const int inf=1000;

void AfisMat(int a[20][20], int n)

void FloydWarshall(int n, int b[20][20], int d[20][20], int p[20][20])

for(k=1;k<=n;k++)

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

if(d[i][k]+d[k][j]<d[i][j])

void drum(int p[20][20], int n, int i, int j)

printf('Drumul de la %d la %d este ',i,j);

for(i=k;i<=n;i++)

printf('%d ',x[i]);

printf('n');

void main()

printf('Numarul de muchii: ');

scanf('%d',&m);

for(i=1;i<=m;i++)

FloydWarshall(n, b, d, p);

printf('Matricea drumurilor: n');

AfisMat(d, n);

printf('Matricea de precedenta: n');

AfisMat(p, n);

printf('Intre ce vf vreti sa vedeti dr minim?n');

printf('i=');

scanf('%d', &i);

printf('j=');

scanf('%d',&j);

drum(p, n, i, j);

Problema PD3

Se da un sir de n matrice A1, A2, …, An, matricea Ai avand dimensiunile di x di+1, pentru i = . Se stie ca, pentru a inmulti doua matrice A si B de dimensiuni n * p respectiv, p * r sunt necesare n*p*r inmultiri elementare. Tinand cont ca, inmultirea matricelor este asociativa, dar nu este comutativa, sa se determine modul in care cele n matrice pot fi inmultite astfel incat numarul de inmultiri elementare sa fie minim.

Fie Mij costul produsului matricelor Ai, ,Aj reprezentand numarul de inmultiri elementare necesare. In mod clar, Mii = 0 pentru orice i iar M1n este costul produsului sirului de matrice A1An.

Demonstrarea principiului optimalitatii:

Fiecare mod de parantezare a unei secvente de matrice poate fi reprezentat printr-un arbore binar (infixat), unde frunzele sunt matricele iar nodurile interioare sunt produsele intermediare.

Fie T arborele corespunzator modului optim de parantezare a secventei de matrice AiAj. T are un subarbore stang L si un subarbore drept R. L corespunde produsului B Ai Ak, iar R produsului C = Ak+1 Aj unde i k j-1.

Costul corespunzator lui T este:

Cost(T)= Cost(R) + Cost(L) + Cost(B C)

Pentru ca Principiul Optimalitatii sa fie respectat este necesar sa aratam ca L este arborele asociat parantezarii optime a sirului Ai … Ak si R este arborele asociat parantezarii optime a sirului Ak+1 … Aj. Vom face demonstratia pentru L prin reducere la absurd. Daca L nu este optim inseamna ca exista un arbore L’ mai bun pentru produsul secventei de matrice Ai … Ak. Cost(L') < Cost(L). Fie T’ arborele care il are pe L subarbore stang si pe R subarbore drept.

Cost(T') = Cost(L') + Cost(R) + Cost(B C) < Cost(L) + Cost(R) + Cost(B C) = Cost(T)

Rezulta ca Cost(T') < Cost(T) ceea ce contrazice presupunerea ca T este arborele corespunzator modului optim de parantezare a secventei de matrice AiAj. Prin urmare, L este arborele asociat parantezarii optime a sirului Ai … Ak.

Deducerea formulei de recurenta:

Mij = Cost(T) = Cost(L) + Cost(R) + Cost(B C

=Mik + Mk+1,j + didk+1dj+1.

Intrucat valoare lui k nu este cunoscuta si Mij se doreste a fi minimul posibil, relatia devine:

Mij = min

Exemplu

Fie matricele: A1 (3x5), A2 (5x7), A3 (7x3) si A4 (3x4). Intre paranteze sunt specificate dimensiunile fiecarei matrice. Prin urmare, d1 = 3, d2 = 5, d3 = 7, d4 = 3, d5 = 4.

Valorile Mij se calculeaza dupa cum urmeaza:

M11=0

M22=0

M33=0

M44=0

M12=105

M23=105

M34=84

M13=150
k=1

M24=165
k=3

M14=186
k=3

Pentru fiecare Mij este pastrat k-ul pentru care valoarea lui Mij este minima.

Parantezarea optima este: (A1(A2 A3))A4.

Algoritmul care calculeaza costul minim al produsului sirului de matrice A1,,An este prezentat in pseudocod mai jos. In triunghiul superior sunt pastrate costurile iar in triunghiul inferior k-urile pentru care se obtin valorile minime. Daca Mij este costul minim atunci Mji este k-ul pentru care s-a obtinut Mij-ul.

PROGRAM NR_INMULTIRI

BEGIN

FOR i : = 1 TO n DO Aii = 0;

FOR l : = 1 TO n–1 DO

FOR i := 1 TO n–1 DO

j := i+l;

a[i,j] :=

FOR k := i to j-1 DO

m := ai,k + ak+1,j + dimi * dimk+1 * dj+1;

IF ai,j > m THEN

ai,j := m;

aj,i := k;

ENDIF;

ENDFOR;

ENDFOR;

ENDFOR;

RETURN a1,n;

END.

Pornind de la informatiile pastrate in matricea M se poatea afisa parantezarea optima a sirului de matrice A1,…An.

SUBPROGRAM PARANTEZARE(i, j

BEGIN

IF i = j THEN

WRITE ’A’,i

ELSE

WRITE ’(’;

PARANTEZARE(i, Mji

WRITE ’*’;

PARANTEZARE(Mji + 1, j

WRITE ’)’;

END;

ENDIF;

END.

Textul sursa al programului este:

#include<stdio.h>

#include<limits.h>

void nr_inmultiri(int m[100][100], int d[100], int n)

}

}

printf('nr minim de inm: %d', m[1][n]);

void parantezare(int m[100][100], int i, int j)

void main()

nr_inmultiri(m, d, n);

parantezare(m,1,n);

Problema PD4

Se dau doua siruri de numere intregi de m respectiv n elemente. Sa se determine cel mai lung subsir comun al celor doua siruri.

Fiind dat un sir x1, x2…xm, un subsir este un sir z1, … zk pentru care exista sirul de indici i1 < … < ik astfel incat j < k. Problema cere gasirea celui mai lung subsir comun a doua siruri x1, x2…xm si y1, y2…yn.

Exemplu

Pentru sirurile:

X=(1,6,5,2,3,6,6,2,9,4,10,1,3,8,5,1,9,7)

Y=(6,1,5,6,5,5,4,3,4,5,2,4)

o solutie posibila este: Z=(1,5,6,4,3,5)

Fie Xk x1 x2 xk) prefixul lui X de lungime k si Yh y1 y2 yh) prefixul lui Y de lungime h. Notam cu L(Xk,Yh) lungimea celui mai lung subsir comun al lui Xk Yh

Ca si la problema precedenta vom utiliza o matrice L in care Lij va fi lungimea celui mai lung subsir comun al sirurilor Xi si Yj.

Relatia de recurenta care va sta la baza constructiei matricei este:

Li0 = 0 i =

L0j = 0 j =

Daca Xk+1 = Yh+1 atunci L(Xk+1,Yh+1) = 1 + L(Xk,Yh).

Daca Xk+1 Yh+1 atunci L(Xk+1,Yh+1) = max(L(Xk,Yh+1), L(Xk+1,Yh)).

Algoritmul in pseudocod care descrie formulele de mai sus este:

PROGRAM SUBSIR

BEGIN

FOR i : = 1 TO n DO Li0 = 0;

FOR j : = 1 TO m DO L0j = 0;

FOR i : = 1 TO n DO

FOR j := 1 TO m DO

IF Xi = Yj THEN

Lij = 1 + Li-1,j-1;

ELSE

IF Li-1,j > Li,j-1 THEN

Li,j = Li-1,j

ELSE

Li,j = Li,j-1

ENDIF;

ENDIF;

ENDFOR;

ENDFOR;

END.

Afisarea subsirului comun obtinut se face prin:

SUBPROGRAM AFISARE

BEGIN

i = n; j = m; k = 1;

WHILE Lij <> 0 DO

IF Xi = Yj THEN

Zk = Xi;

i = i – 1; j = j – 1; k = k + 1;

ELSE

IF Li-1,j > Li,j-1 THEN

i = i – 1;

ELSE

j = j – 1;

ENDIF;

ENDIF;

ENDWHILE;

WRITE Z;

END.

Textul sursa al programului este:

#include<stdio.h>

void afisare(int a[20], int n)

void subsir(int a[20][20], int x[20],int y[20],int n,int m)

void afisare_subsir(int a[20][20], int x[20], int y[20], int n, int m)

else

if(a[i][j]==a[i-1][j])

i--;

else

j--;

printf('Sirul comun de lungime maxima este: ');

for(i=k;i>=1;i--)

printf('%d ',z[i]);

printf('n');

void main()

printf('m=');

scanf('%d',&m);

for(i=1;i<=m;i++)

printf('Primul sir: ');

afisare(x,n);

printf('Al doilea sir: ');

afisare(y,m);

subsir(a, x, y, n, m);

afisare_subsir(a, x, y, n, m);






Politica de confidentialitate



DISTRIBUIE DOCUMENTUL

Comentarii


Vizualizari: 1139
Importanta: rank

Comenteaza documentul:

Te rugam sa te autentifici sau sa iti faci cont pentru a putea comenta

Creaza cont nou

Termeni si conditii de utilizare | Contact
© SCRIGROUP 2021 . All rights reserved

Distribuie URL

Adauga cod HTML in site