Scrigroup - Documente si articole

Username / Parola inexistente      

Home Documente Upload Resurse Alte limbi doc  

CATEGORII DOCUMENTE





AccessAdobe photoshopAlgoritmiAutocadBaze de dateCC sharp
CalculatoareCorel drawDot netExcelFox proFrontpageHardware
HtmlInternetJavaLinuxMatlabMs dosPascal
PhpPower pointRetele calculatoareSqlTutorialsWebdesignWindows
WordXml


Metoda „programarii dinamice”

algoritmi

+ Font mai mare | - Font mai mic







DOCUMENTE SIMILARE

Trimite pe Messenger
Utilizarea teoriei NP-completitudinii in abordarea algoritmilor euristici
F# programming - Introducing Functional Programming
ATESTAT – ALGORITMI
PROIECT ASDN - Dispozitiv de comanda pentru doua lifturi alaturate
SCHEMELE LOGICE - Structuri fundamentale ale algoritmilor
Proiect la Informatica - Algoritmi fundamentali cu vectori
Tehnici de programare
Shell-ul ca limbaj de programare
Utilizarea mediului ActiveHDL pentru proiectarea, simularea si implementarea structurilor de calculatoare numerice
Grafuri - Parcurgerea DF a grafurilor neorientate

Metoda „programarii dinamice”

            Metoda programarii dinamice, asa cum ii arata si numele, permite determinarea unei solutii pentru o problema data, in urma unui sir de decizii si prelucrari ce se conditioneaza reciproc, realizand o „dinamica’ continua a procesului de cautare a solutiei.



Ordinul de complexitate al unui astfel de algoritm este conditionat de modul de organizare a datelor initiale, a rezultatelor intermediare si de modalitatea de regasire a rezultatelor intermediare, obtinute anterior momentului unei noi prelucrari a acestora.

Problema. Notiunea de algoritm, asa cum a fost prezentata, presupune ca entitati distincte, existenta unui set de date de intrare si a unei metode de transformare succesiva a acestora, in vederea obtinerii unui set coerent de date de iesire ca rezultat al tuturor prelucrarilor. Abordarea celor trei elemente ca un sistem presupune existenta unor interconditionari intre acestea. Ca metoda de elaborare a algoritmilor de rezolvare a unor clase de probleme, programarea dinamica presupune identificarea acestor corelatii, privind problema initiala ca un sistem de miniprobleme care se conditioneaza reciproc.

Solutie. Pentru o problema data, fie S0 starea sistemului format din datele de intrare si de lucru (intermediare), precum si din corelatiile care exista intre acestea. O decizie d1 de prelucrare a datelor orientata in directia obtinerii unei solutii optime pentru problema produce o “prelucrare” a starii S0 determinand transformarea acesteia intr-o noua stare S1. Suntem in acest moment pusi in fata uneia sau mai multor probleme similare cu cea initiala si care - printr-o noua decizie (comuna) de prelucrare -  conduc la o noua stare. Schimbarea starii sistemului va continua pana la obtinerea unei stari finale din care se deduce o solutie optima a problemei initiale.

            In general, fiecare noua decizie de transformare a starii sistemului depinde de deciziile luate anterior (acestea au generat starea curenta a sistemului) si nu este unic determinata ca in cazul metodei greedy, de exemplu.

            Fie d1, d2, , dn-1, dn   o secventa de decizii optime care determina trecerea succesiva a sistemului din starea initiala S0 in starea finala Sn, prin intermediul starilor S1, S2, , Sn-1.

            O modalitate naturala de abordare a problemei consta din luarea succesiva de decizii optime de prelucrare in ordinea d1, d2, , di-1, pornind de la starea initiala S0. Decizia urmatoare di, depinde de sirul de decizii optime deja luate d1, d2, , di-1. Spunem in acest caz ca se aplica metoda spre inapoi (sfarsitul sirului de decizii).

            Daca se poate stabili starea sistemului Sn din care s-ar deduce solutia optima a problemei, este de dorit sa se determine o decizie dn precum si o stare Sn-1 din care sa se ajunga in starea Sn in urma aplicarii deciziei dn. Intuitiv spus, se determina inversa unei decizi' si starea sistemului anterioara luarii acestei decizii. Fie secventa de decizii optime di+1, di+2, , dn care duc sistemul din starea Si in starea finala Sn .O noua decizie di care sa duca sistemul din starea Si-1 in starea Si va depinde de sirul de decizii di+1, di+2, , dn. Spunem in acest caz ca se aplica metoda spre inainte (inceputul sirului de decizii).

A treia modalitate de abordare sugereaza determinarea unei stari intermediare, Si , si a doua decizii optime di si di+1, avand doua subsiruri optime de decizii:

- di+2, di+3, , dn care duc sistemul din starea Si+1 in starea finala Sn prin intermediul starilor Si+1, Si+2, , Sn-1;

- d1, d2, , di-1, sir de decizii optime care determina trecerea sistemului din starea initiala S0 in starea Si-1, prin intermediul starilor S1, S2, , Sn-2. Spunem in acest caz ca se aplica metoda mixta (exploziva).

            Cele trei modalitati de abordare au la baza principiul optimalitatii. Daca d1, d2, , dn este un sir optim de decizii care determina trecerea sistemului din starea initiala S0 in starea finala Sn, atunci sunt adevarate urmatoarele afirmatii:

            - di+1, di+2, , dn este un  sir optim de decizii care determina trecerea sistemului din starea Si in starea finala Sn, ' i, 0£ i £n-1;

            - d1, d2, , di este un sir optim de decizii care determina trecerea sistemului din starea initiala S0 in starea Si, 'i, 1£ i £n;




            - di+1, di+2, , dn  si d1, d2, , di sunt siruri optime de decizii care determina trecerea sistemului din starea Si in starea finala Sn si respectiv din starea initiala S0 in starea Si, 'i, 1£ i £n.

            Principiul optimalitatii sugereaza stabilirea unor relatii de recurenta.

            In concluzie, rezolvarea unei probleme prin metoda programarii dinamice presupune identificarea unor caracteristici ale problemei care o fac rezolvabila prin aceasta metoda:

            - problema se poate descompune in subprobleme de acelasi tip cu aceasta;

            - subproblemele nu sunt distincte, se interconditioneaza reciproc (altfel s-ar putea aplica tehnica 'divide et impera', mult mai eficienta din punct de vedere al consumului de memorie);

            - necesitatea satisfacerii principiului optimalitatii, care implica stabilirea relatiei de recurenta prin care se exprima interconditionarea subproblemelor.

            In cele ce urmeaza, vom prezenta un exemplu de abordare a unor probleme prin metoda programarii dinamice. Sunt punctate caracteristicele importante ale metodei, chiar daca problema aleasa poate sa fie considerata drept necaracteristica.

 

Problema. Sa se determine termenul de rang k din sirul lui Fibonacci, pentru un numar natural k dat.

Intrare: k, de la tastatura.

Iesire: pe ecran, de forma: Termenul de rang k din sirul lui Fibonacci este v.

Solutie (metoda). In sirul lui Fibonacci, primii doi termeni sunt a0 = 1 si a1 = 1. Relatia de recurenta ak  = ak-1  + ak-2  , 'k>2, arata ca un termen se obtine ca suma ultimilor doi termeni anteriori lui.

            Vom folosi metoda „inapoi” plecand de la starea initiala u = 1, v = 1 (primii doi termeni), care reprezinta si starea din care se deduce solutia problemei pentru k = 1.

Decizia de trecere la o noua stare determina urmatoarele prelucrari:

- aplicarea relatiei de recurenta (calculul sumei s = u + v), care respecta principiul optimalittaii;

- obtinerea noii stari prin atribuirea valorilor u =  v si v =  s.

            Se obtine starea u = 1, v = 2.

            Aceasta este starea nou obtinuta (succesoare).

Sunt respectate caracteristicile problemelor care sunt rezolvabile prin metoda programarii dinamice:

            - solutia unei probleme este obtinuta din solutia problemei rezolvate anterior (se determina termenul de rang k din termenii de rang k-1 si k-2);

-          este satisfacut principiul optimalitatii (o solutie optima pentru problema anterioara conduce la solutia optima a problemei curente).

program termen_sir_Fibonacci;

var i,k : byte;

    u,v,s : word;

begin

   write ('k ');

   readln (k);

   u := 1;

   v := 1;

for i := 2 to k do

       begin

          s := u + v;

          u := v;

          v := s;

       end;

   writeln (' Termenul de rang ',k,' este',v);

   readln;

end.

Intrare:N = 10

Iesire:Termenul de rang 10 este 89.








Politica de confidentialitate

DISTRIBUIE DOCUMENTUL

Comentarii


Vizualizari: 620
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 2019 . All rights reserved

Distribuie URL

Adauga cod HTML in site