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
Stiva
Structuri elementare de date
Instructiunea do-while
Caractere
Controlling the Troops: SetWorkArmy, ChangeArmy
Pointeri si adrese
Iesirea formatata-printf
Tipul de date inregistrare (RECORD)
Gestiunea culorilor
Comaparatie pointeri

TERMENI importanti pentru acest document

Metoda programarii dinamice

Aceasta metoda este aplicabila problemelor de optim in care solutia poate fi privita ca rezultatul unui sir de decizii d1, . . . ,dn. 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 d1,,dn un sir optim de decizii (SOD) care transforma starea so in starea sn, trecand prin starile intermediare s1, . . . ,sn-1; vom nota acest fapt prin (d1,dn) este SOD pentru perechea de stari (so,sn);

grafic procesul este descris ca in figura urmatoare:

d1 d2 dn

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

so s1 s2 sn-1 sn

Vom da acum mai multe variante ale principiului optimalitatii:

daca (d1,dn) este SOD pentru (so,sn) atunci (d2,dn) este SOD pentru (s1,sn);

daca (d1,dn) este SOD pentru (so,sn) atunci i din avem

a) (d1,di) este SOD pentru (so,si) SAU

b) (di+1,dn) este SOD pentru (si,sn).

3) daca (d1,dn) este SOD pentru (so,sn) atunci i din avem

a) (d1,di) este SOD pentru (so,si) SI

b) (di+1,dn) este SOD pentru (si,sn).

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 di depinde de di+1,,dn - relatii de recurenta inainte, deciziile vor fi luate in ordinea dn, dn-1, . . . ,d1;

fiecare decizie di depinde de d1, . . . ,di-1 - relatii de recurenta inapoi, deciziile vor fi luate in ordinea d1, d2, . . . , dn.

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, i1, i2, . . . , im, j DVM intre i si j atunci evident    ca i1, . . . , im, j este DVM intre i1 si

j;

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

- notam deasemenea dkj 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=(aij), i=1,,n; j=1,,m cu elementele din multimea . Doua elemente din A aij si akl se numesc 4-vecine daca ½i-k½ ½j-l½

Notam cu So, S1 si S2 submultimile formate din elementele matricii egale cu 0, 1 respectiv 2. Submultimea S1 se imparte in grupuri astfel: aij si akl fac parte din acelasi grup daca sunt 4-vecine sau daca apq I S1 : aij si apq sunt 4-vecine iar apk si akl sunt din acelasi grup. Un element akl I So il vom numi spion al grupului G I S1 dac aij I G a.i. akl si aij s² fie vecine. Un spion este perfect dac are toti vecinii din G.

Se cere:

a) cel mai numeros grup ( S1) 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 90o 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 aij ale matricii contin cotele (inaltimile) diferitelor portiuni astfel obtinute. Se presupune ca o bila se gaseste pe o portiune (io,jo) avand cota a(io,jo).

Se cere un program care sa precizeze toate traseele (incepand cu (io,jo) ) 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 (io,jo) trebuie sa fie o succesiune de perechi (io, jo), (i1, j1) . . . (ik, jk) astfel incat 2 perechi invecinate sa fie 4-vecine si a(ip,jp)=0

p=0, . . . ,k.






Politica de confidentialitate



DISTRIBUIE DOCUMENTUL

Comentarii


Vizualizari: 547
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