Metoda programarii dinamice

Metoda programarii dinamice

Aceasta metoda este aplicabila problemelor de optim in care solutia poate fi privita ca rezultatul unui sir de decizii d₁, . . . ,d_n. Fiecare decizie depinde de deciziile deja luate si nu este unic determinata (spre deosebire de tehnica greedy unde fiecare decizie care se ia trebuie sa fie unica). Totodata este necesar sa fie satisfacuta una din variantele principiului optimalitatii pentru a putea fi aplicata aceasta metoda.

Vom formaliza acest principiu al optimalitatii:

fie d₁,,d_n un sir optim de decizii (SOD) care transforma starea s_o in starea s_n, trecand prin starile intermediare s₁, . . . ,s_n-1; vom nota acest fapt prin (d₁,d_n) este SOD pentru perechea de stari (s_o,s_n);

grafic procesul este descris ca in figura urmatoare:

d₁ d₂ d_n

*----->*---->*------>* . . . *------>*

s_o s₁ s₂ s_n-1 s_n

Vom da acum mai multe variante ale principiului optimalitatii:

daca (d₁,d_n) este SOD pentru (s_o,s_n) atunci (d₂,d_n) este SOD pentru (s₁,s_n);

daca (d₁,d_n) este SOD pentru (s_o,s_n) atunci i din avem

a) (d₁,d_i) este SOD pentru (s_o,s_i) SAU

b) (d_i+1,d_n) este SOD pentru (s_i,s_n).

3) daca (d₁,d_n) este SOD pentru (s_o,s_n) atunci i din avem

a) (d₁,d_i) este SOD pentru (s_o,s_i) SI

b) (d_i+1,d_n) este SOD pentru (s_i,s_n).

Ultima varianta este cea mai generala si mai completa. Odata verificat o forma a principiului optimalitatii, metoda programarii dinamice consta in a scrie relatiile de recurenta si apoi de a le rezolva. In general relatiile de recurenta sunt de 2 tipuri :

fiecare decizie d_i depinde de d_i+1,,d_n - relatii de recurenta inainte, deciziile vor fi luate in ordinea d_n, d_n-1, . . . ,d₁;

fiecare decizie d_i depinde de d₁, . . . ,d_i-1 - relatii de recurenta inapoi, deciziile vor fi luate in ordinea d₁, d₂, . . . , d_n.

Problema rezolvata

Fie G=(X,Γ) un 1-graf orientat caruia ii atasam matricea costurilor, (fiecare arc (i,j)IΓ este etichetat cu o valoare reala strict pozitiva). Se pune problema gasirii drumului de valoare minim (DVM) intre oricare 2 varfuri i si j.

Rezolvare

Verificam prima varianta a principiului optimalitatii:

- fie i, i₁, i₂, . . . , i_m, j DVM intre i si j atunci evident    ca i₁, . . . , i_m, j este DVM intre i₁ si

j;

- notam prin L(i,k) lungimea DVM dintre i si k, kIX;

- notam deasemenea d_kj valoarea arcului (k,j);

- ecuatiile de recurenta sunt:

L(i,j) = min

(k,j)I

#include<stdio.h>

#include<values.h>

#define nn 10

int d[nn+1][nn+1],i,j,n;

int L(int i,int j)

return m;

}

void citestematrice(void)

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

for(j=1;j<=n;j++) if (d[i][j]= = ‑1) d[i][j]=MAXINT;

void citeste(void)

void afiseaza(int val)

void main(void)

Probleme propuse

Se da o matrice A=(a_ij), i=1,,n; j=1,,m cu elementele din multimea . Doua elemente din A a_ij si a_kl se numesc 4-vecine daca ½i-k½ ½j-l½

Notam cu S_o, S₁ si S₂ submultimile formate din elementele matricii egale cu 0, 1 respectiv 2. Submultimea S₁ se imparte in grupuri astfel: a_ij si a_kl fac parte din acelasi grup daca sunt 4-vecine sau daca a_pq I S₁ : a_ij si a_pq sunt 4-vecine iar a_pk si a_kl sunt din acelasi grup. Un element a_kl I S_o il vom numi spion al grupului G I S₁ dac a_ij I G a.i. a_kl si a_ij s² fie vecine. Un spion este perfect dac are toti vecinii din G.

Se cere:

a) cel mai numeros grup ( S₁) care are un singur spion (daca exista).

b) toate grupurile care au cel putin doi spioni perfecti.

Se da o matrice cu elemente care au valori din , care reprezinta un teren cu drumuri si obstacole . In acest teren se afla un tanc si o tinta. Acest tanc poate primi comenzi pentru rotirea tevii (cu 90^o in ambele sensuri), pentru deplasare (in directia tevii cu o linie sau cu o coloana) sau pentru tragere (in directia tevii pentru a nimeri tinta) in cazul in care intre tanc si tinta nu exista nici un obstacol. Considerand ca deplasarea nu se poate efectua prin obstacole, se cere cel mai scurt drum necesar tancului pentru a putea distruge tinta si sirul comenzilor efectuate in cazul in care exist un astfel de drum.

Se d o matrice cu elemente din , reprezentand o padure cu capcane (0) si carari (1). In aceasta padure se afla o vulpe (2) si mai multi lupi (3). Fiecare lup incearca sa se apropie de vulpe fara a sti unde se afla capcanele, iar in cazul in care cade intr-o capcana, moare. Vulpea incearca sa se indeparteze de cel mai apropiat lup, avand insa posibilitatea sa descopere si capcanele si sa le ocoleasca. Atat vulpea cat si lupii ii pot modifica pozitia doar cu o linie sau cu o coloana in fiecare moment. Sa se spuna daca vulpea reuseste sa scape de lupi.

Se considera un teren dreptunghiular sub forma unei matrici A de m linii si n coloane. Elementele a_ij ale matricii contin cotele (inaltimile) diferitelor portiuni astfel obtinute. Se presupune ca o bila se gaseste pe o portiune (i_o,j_o) avand cota a(i_o,j_o).

Se cere un program care sa precizeze toate traseele (incepand cu (i_o,j_o) ) posibile pe care le poate urma bila spre a iesi din teren, stiind ca bila se poate deplasa in orice portiune de teren 4-invecinat cu o cota strict inferioara cotei terenului pe care se gaseste bila.

Se cere un program care rezolva problema labirintului (nerecursiv).

O matrice de m linii si n coloane reprezinta un labirint daca:

a(i,j) = o    - semnificand culoar;

a(i,j) = 1    - semnificand zid.

Un traseu de iesire pornind de la o portiune (i_o,j_o) trebuie sa fie o succesiune de perechi (i_o, j_o), (i₁, j₁) . . . (i_k, j_k) astfel incat 2 perechi invecinate sa fie 4-vecine si a(i_p,j_p)=0

p=0, . . . ,k.