Programarea dinamica este o metoda care descompune o problema in mai multe subprobleme si prin rezolvarea lor si combinarea rezultatelor se obtine un rezultat final. Subproblemele nu sunt independente (cum sunt la metoda Divide et impera). Prin urmare, vom rezolva subproblemele o singura data si retinem rezultatele intr-o structura de date suplimentara.
Am ales sa fac un tutorial despre PD pentru ca multi considera a fi o metoda grea fata de celelalte.
Se iau in considerare urmatorii pasi cand vine vorba despre programarea dinamica:
- Se cauta subproblemele problemei
- Se alege o structura de date care poate sa retina informatiile din subprobleme
- Se foloseste o relatie de recurenta
- Pentru a determina solutia finala, se rezolva relatia de recurenta in mod "bottom-up"
(Ce-i mai sus e inspirat din Programarea in limbajul C/C++ pentru liceu, volumul II. O carte buna, o recomand. Are cateva greseli care s-ar putea sa va duca in eroare, dar daca esti atent nu apar probleme)
Cum prin teorie nu poti intelege informatica am sa prezint doua probleme care sa va lumineze si sa va indrume in magia programarii dinamice.
Clasica problema de determinarea celui de-al n-lea termen al sirului Fibonacci.
Relatia de recurenta care sta la baza determinarii celui de-al n-lea termen al sirului Fibonacci este:
fib(x) = { 1, x<=2
{ fib(x-1) + fib(x-2), x>2
Daca am rezolva recursiv ar fi foarte ineficient.
int fib(int n)
{
if(x<=2) return 1;
return fib(n-1)+fib(n-2);
}
Schema apelurilor recursive e in forma de arbore binar si ca sa calculezi fib(4) fib(2) trebuie calculat de 2 ori, fib(1) de 3 ori si fib(0) de 2 ori. Foarte ineficient. In schimb, folosind un vector si metoda programarii dinamice, lucrurile devin mai frumoase:
int fib(int n)
{
int A[50]; //structura de date despre care povesteam unde retinem solutiile
if(n<=2) return 1;
A[0]=A[1]=0;
for(int i=2; i<n; ++i)
{
A[i]=A[i-1]+A[i-2];
}
return A[n-1];
}
ATENTIE, NU ARE LEGATURA CU PROGRAMAREA DINAMICA! E DOAR PENTRU CEI CARE DORESC SA INVETE MAI MULT!
Pentru cei ce doresc sa invete mai mult, se poate optimiza algoritmul folosind matricea.
A=(0 1)
(1 1)
Termenul (2; 2) din matricea An-1 este al n-lea termen fibonacci. Pentru a optimiza inmultirile faci o ridicare la putere in timp logaritmic si...gata!
Lacusta
Prima mea problema legata de programarea dinamica.
Problema se poate gasi aici: http://varena.ro/problema/lacusta
Pentru a retine solutiile subproblemelor (determinarea sumei minime care se poate obtine pronin din coltul din stanga sus pana la fiecare element A[j] al matricei) vom construi o matrice B cu m linii si n coloane, cu semnificatia ca B[j] reprezinta suma minima care se poate obtine din coltul stanga-sus pana la elementul A[j].
Solutia problemei date este min(B[m-1][j]) (unde j=0,1,,2,3,...,n-2) + A[m-1][n-1]
Relatia de recurenta:
B[0][0] = A[0][0]
B[0] = unsigned(-1), unde 0<i<n
B[1][0] = unsigned(-1)
B[1][j] = A[0][0] + A[0][j] + A[1][j], unde 0<j<n
B[j] = A[j + A[i-1][j] + min(B[i-1][k]), unde 0<=k<n
Pentru a ajunge in A[j am facut un pas de pe A[i-1][j], iar pentru A[i-1][j] am facut un salt
A[i-1][km] de pe care se face saltul este ales astfel incat B[i-1][km] = min(B[i-1][k]), unde 0<=k<n
Se gasi o problema in momentu' in care calculezi matricea B. Sunt sanse ca elementul minim de pe coloana i-1 sa se gaseasca pe coloana j de unde faci pasu'. Ca sa evitam calculam min1 si min2, doua valori minime de pe linia i-1.
#include <fstream>
#define NMAX 101
using namespace std;
ifstream in("lacusta.in");
ofstream out("lacusta.out");
int main()
{
unsigned A[NMAX][NMAX], B[NMAX][NMAX], m, n, min1, min2, jmin;
in>>m>>n;
for(int i=0; i<m; ++i)
{
for(int j=0; j<n; ++j)
{
in>>A[i][j];
}
}
B[1][0]=unsigned(-1);
for(int i=1; i<n; ++i)
{
B[1][i]=A[0][0]+A[0][i]+A[1][i];
}
for(int i=1; i<m-1; ++i)
{
if(B[i][0]<=B[i][1])
{
min1=B[i][0];
min2=B[i][1];
jmin=0;
}
else
{
min1=B[i][1];
min2=B[i][0];
jmin=1;
}
for(int j=2; j<n; ++j)
{
if(B[i][j]<min1)
{
min2=min1;
min1=B[i][j];
jmin=j;
}
else
{
if(B[i][j]<min2)
{
min2=B[i][j];
}
}
}
for(int j=0; j<n; ++j)
{
if(j!=jmin)
{
B[i+1][j]=min1+A[i][j]+A[i+1][j];
}
else
{
B[i+1][j]=min2+A[i][j]+A[i+1][j];
}
}
}
min1=B[m-1][0];
for(int j=1; j<n; ++j)
{
if(B[m-1][j]<min1)
{
min1=B[m-1][j];
}
}
out<<min1+A[m-1][n-1]<<'\n';
return 0;
}
Poate fi optimizata sursa. Cu mult. Nu este nevoie de o matrice B cu m*n elemente, ci doar de o matrice B cu 2*n elemente.
O optimizare si mai buna: poti rezolva problema cu o matrice simpla de n*n elemente.
Mai mult decat atat, elementele sunt <= 255. Altceva despre care trebuie sa tineti cont.
Puteti incerca sa vedeti daca puteti optimiza sursa pe site-ul infoarena: http://www.infoarena.ro/problema/lacusta
