Programare Dinamica

Extras din referat Cum descarc?

Programarea dinamica face parte dintr-o categorie de metode matematice numite metode de scufundare.O problema de programare dinamica contine subprobleme comune (care nu sunt independente) din a caror rezolvare si combinare se obtine solutia unei (sub)probleme mai mari.Deci rezolvarea unei (sub)probleme se poate face doar dupa solutionarea (sub)problemelor, care alcatuiesc problema respectiva.Spunem ca programarea dinamica actioneaza de jos in sus,prelucrand si combinand subcazuri mici,obtinand astfel solutia pentru subcazuri tot mai mari.
Totodata programarea dinamica evita rezolvarea de mai multor ori a aceleiasi subprobleme(rezolvandu-se doar problemele independente ),prin memorarea rezultatelor partiale.
Sa presupunem ca avem de rezolvat urmatoarea problema :
Sa se calculeze valoarea C(n,k)(combinari de n luate cate k). 
Folosim functia recursiva :
function comb(n,k;integer):integer;
begin 
if (k=0)or (k=n)then comb:=1
else comb:=comb(n-1,k-1)+comb(n-1,k)
end;
Din punct de vedere al timpului de executie aceasta metoda este ineficienta ,deoarece sunt calculate se mai multe ori aceleasi valori .
Vom elimina acest dezavantaj prin evitarea recursivitatii,pastrand intr-un tabel rezultatele intermediare si luandu-le de acolo ori de cate ori este necesar.Argumentele functiei ne sugereaza forma tabelului(folosindu-le ca indice de linie,respectiv coloana),iar formula ne precizeza modul de completare al tabelului:
1, I=jUj=0
C(I,j)= 
C(I-1,j-1)+c(I-1,j) 0<j<I
Pentru exemplul precedent avem:
Function comb(n,k;integer):integer;
Var i,j:integer;
c:array[0..20,0..20]of integer;
begin 
for i:=0 to n do
begin c[i,0]:=1;
c[i,1]:=1;
for j:=1 to i-1 do
c[i,j]:=c[i-1,j-1]+c[i-1,j];
end;
comb:=c[n,k];
end;
Orice algoritm de programare dinamica poate fi descris prin urmatorii pasi:
1)Caracterizarea structurii unei solutii optime:se defineste un vector,o matrice ,...,in care fiecare componenta va contine o solutie optima a unei subprobleme. 
2)Definirea recursiva a valorii unei solutii optime .Totodata se defineste valoarea celei mai mici subprobleme(celor mai mici subprobleme).
Ex: c[i,0]:=1;
c[i,1]:=1;
3)Calcularea de jos in sus a valorii unei solutii optime ,tinand seama de definirea recursiva a acestei valori.
4)Daca pe langa valoare se mai doreste afisarea solutiei care a generat rezultatul optim ,atunci se construieste de sus in jos solutia propriu-zisa.


Fisiere in arhiva (1):

  • Programare Dinamica.DOC

Imagini din acest proiect Cum descarc?

Promoție: 1+1 gratis

După plată vei primi prin email un cod de download pentru a descărca gratis oricare alt referat de pe site.Vezi detalii.


Descarcă aceast referat cu doar 4 € (1+1 gratis)

Simplu și rapid în doar 2 pași: completezi adresa de email și plătești. După descărcarea primului referat vei primi prin email un alt cod pentru a descărca orice alt referat.

1. Numele, Prenumele si adresa de email:

Pe adresa de email specificata vei primi link-ul de descarcare. Daca nu gasesti email-ul, verifica si directoarele spam, junk sau toate mesajele.

2. Alege modalitatea de plata preferata:


* La pretul afisat se adauga 19% TVA, platibil in momentul achitarii abonamentului / incarcarii cartelei.

Hopa sus!