際際滷

際際滷Share a Scribd company logo

Metoda programarii dinamice

Download as PPTX, PDF
L
Luminia Mihailov

progarmarii

1 of 8
Download to read offline
Metoda programrii dinamice
Metoda programrii dinamice Metoda programrii dinamice se poate folosi pentu problemele 樽n care trebuie s fie gsit soluia optim i care au urmtoarele caracteristice: Soluia optim se alege dintr-o mulime de soluii ,fiecare soluie poate s i se asocieze o valoare.Alegerea soluiei optime 樽nseamn alegerea soluiei care are valoarea optim Problema poate fii descompus 樽n subprobleme similare cu problema iniial ce respect principiul optimalitii. Subproblemele 樽n care se descompun problemele nu sunt independente Soluia este dat de un vector
Scop-identificarea problemelor care pot fii descompuse 樽n subprobleme similare care nu sunt independente i care respect principiul optimalitii,soluiilor put樽nd s li se asocieze o valoare,iar soluia optim determin樽ndu-se prin calcularea valorii optime. Metoda clasic de rezolvare a acestei probleme este de a calcula toate sumele care se pot forma respect樽nd restricia de deplasare 樽n triunghi i de a alege suma care are cea mai mare valoare.
Metoda programrii dinamice se bazeaz pe descompunerea unei probleme 樽n subprobleme similare problemei iniiale,care nu sunt independente,i construiete soluia rezolv樽nd fiecare subproblem,prin selectarea,dintr-o mulime de elemente,a elementelor care 樽ndeplinesc o anumit condiie. Pentru ca elementele care se selecteaz s aparin soluiei optime,la pasul k alegerea se face 樽n funcie de valoarea optim a unei funcii asociate soluiei i se bazeaz pe alegirile care s-au fcut p但n atunci
Etapele de rezolvare Pasul 1- se demonstreaz a problema are o substructur optim Pasul 2- se carecterizeaz structura unei soluii optime Pasul 3- se definete recursiv valoarea soluiiei optime Pasul 4- se calculeaz valoare soluiiei optime intr-o manier de jos 樽n sus Pasul 5- se construiete soluia optim din informaiile opinute prin calcularea valorii soluiiei optime
Implimentarea metodei programrii dinamice Pentru implimentare se folosesc urmtoarele subprograme: Subprogramul init( )-care iniializeaz variabilile de memorie i structurile de date folosite pentru construirea soluiei; Subprogramul p_dinamica( ) care calculeaz valoarea soluiei optime; Subprogramul afieaz ( ) care afieaz soluia problemei folosind informaiile obinute prin calcularea valorii soluiei optime
Strategia implimenarii medode programrii dinamice este urmtoarea: Pasul 1- se iniializeaz linia n a matricei sumelor maxime s cu elementele de pe linie n a matricei triunghiului a; Pasul2 - pentru urmtoarele linii ale matricei sumelor maxime 樽ncep樽nd cu linia n-1 p樽n la linia 1; Pasul3- se calculeaz suma maxim asfel,dac sum amaxima S(i+1,j)-de sub elementul curent din triunghi este mai mare dec樽t suma maxim S(i+1,j+1) de pe diagonala elementului curent ,atunci la elementul curent se adun suma S(i+1,j),la care direcia de deplasare este 1,astfel la elementul curent se adun suma S(i+1,j+1) i direcia de deplasare este 2.
Exemplu de program

More Related Content

Metoda programarii dinamice

  • 2. Metoda programrii dinamice Metoda programrii dinamice se poate folosi pentu problemele 樽n care trebuie s fie gsit soluia optim i care au urmtoarele caracteristice: Soluia optim se alege dintr-o mulime de soluii ,fiecare soluie poate s i se asocieze o valoare.Alegerea soluiei optime 樽nseamn alegerea soluiei care are valoarea optim Problema poate fii descompus 樽n subprobleme similare cu problema iniial ce respect principiul optimalitii. Subproblemele 樽n care se descompun problemele nu sunt independente Soluia este dat de un vector
  • 3. Scop-identificarea problemelor care pot fii descompuse 樽n subprobleme similare care nu sunt independente i care respect principiul optimalitii,soluiilor put樽nd s li se asocieze o valoare,iar soluia optim determin樽ndu-se prin calcularea valorii optime. Metoda clasic de rezolvare a acestei probleme este de a calcula toate sumele care se pot forma respect樽nd restricia de deplasare 樽n triunghi i de a alege suma care are cea mai mare valoare.
  • 4. Metoda programrii dinamice se bazeaz pe descompunerea unei probleme 樽n subprobleme similare problemei iniiale,care nu sunt independente,i construiete soluia rezolv樽nd fiecare subproblem,prin selectarea,dintr-o mulime de elemente,a elementelor care 樽ndeplinesc o anumit condiie. Pentru ca elementele care se selecteaz s aparin soluiei optime,la pasul k alegerea se face 樽n funcie de valoarea optim a unei funcii asociate soluiei i se bazeaz pe alegirile care s-au fcut p但n atunci
  • 5. Etapele de rezolvare Pasul 1- se demonstreaz a problema are o substructur optim Pasul 2- se carecterizeaz structura unei soluii optime Pasul 3- se definete recursiv valoarea soluiiei optime Pasul 4- se calculeaz valoare soluiiei optime intr-o manier de jos 樽n sus Pasul 5- se construiete soluia optim din informaiile opinute prin calcularea valorii soluiiei optime
  • 6. Implimentarea metodei programrii dinamice Pentru implimentare se folosesc urmtoarele subprograme: Subprogramul init( )-care iniializeaz variabilile de memorie i structurile de date folosite pentru construirea soluiei; Subprogramul p_dinamica( ) care calculeaz valoarea soluiei optime; Subprogramul afieaz ( ) care afieaz soluia problemei folosind informaiile obinute prin calcularea valorii soluiei optime
  • 7. Strategia implimenarii medode programrii dinamice este urmtoarea: Pasul 1- se iniializeaz linia n a matricei sumelor maxime s cu elementele de pe linie n a matricei triunghiului a; Pasul2 - pentru urmtoarele linii ale matricei sumelor maxime 樽ncep樽nd cu linia n-1 p樽n la linia 1; Pasul3- se calculeaz suma maxim asfel,dac sum amaxima S(i+1,j)-de sub elementul curent din triunghi este mai mare dec樽t suma maxim S(i+1,j+1) de pe diagonala elementului curent ,atunci la elementul curent se adun suma S(i+1,j),la care direcia de deplasare este 1,astfel la elementul curent se adun suma S(i+1,j+1) i direcia de deplasare este 2.