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


METODE DE ELABORARE A ALGORITMILOR.PROGRAMARE DINAMICA.

c

+ Font mai mare | - Font mai mic







DOCUMENTE SIMILARE

Trimite pe Messenger
Introducere in limbajul C
Modifica informatia ultimului nod din lista
PROGRAMARE IN C
Operatori relationali si logici
Pointeri si tablouri
Tablouri de caractere
TIPURI DE DATE
Instructiuni si blocuri
Struct (inregistrarea)
Siruri de caractere

Metode de elaborare a algoritmilor.Programare dinamica.

Metoda Programarii dinamice se poate considera ca o imbunatatire a tehnicii Greedy. In cazul metodei Greedy, alegerea unui element se face pe baza unui criteriu de admisibilitate, insa la Programarea dinamica, acest criteriu este cel al optimalitatii; folosind-se de un criteriu mai puternic, rezultatul final oferit de metoda programarii dinamice este intotdeauna optimul global.

Ca si metoda Divide et impera, programarea dinamica presupune impartirea problemei in subprobleme, rezolvarea si combinarea solutiilor acestora pentru a obtine rezultatul final. In situatia in care subproblemele obtinute prin descompunere contin subprobleme comune, este preferabila aplicarea metodei Programarii dinamice.

O particularitate a metodei consta in construirea si utilizarea unor tabele cu informatii. Tabelele sunt construite prin completarea unui element folosind elemente completate anterior. Denumirea metodei provine din maniera de completare dinamica a tabelei de informatii intermediare.

Metoda programarii dinamice se caracterizeaza prin principiile fundamentale:

-          sunt evitate calculele repetate ale aceluiasi subcaz, rezultatele intermediare obtinute fiind memorate

-          solutia este construita in maniera bottom-up (de jos in sus): pornind de la solutiile celor mai mici subprobleme, prin combinarea acestora se va ajunge treptat la solutia globala

-          problema abordata respecta principiul optimalitatii

Programarea dinamica este o metoda de rezolvare a problemelor de optimizare pentru care solutia este rezultatul unui sir de decizii optime. Problema de optimizare rezolvabila prin metoda programarii dinamice este formulata astfel:

Fie un sistem care se poate afla intr-una din starile:

S0, S1,  S2 , …, Sn-1, Sn

si fie sirul de decizii

D1,  D2 , …, Dn-1, Dn

prin care sistemul este trecut prin starile date:

Problema verifica unul dintre principiile optimalitatii:

Varianta 1: Daca sirul de decizii D1,  D2 , …, Dn-1, Dn duce sistemul din starea initiala S0 in starea finala Sn in mod optim, atunci:

, secventa de decizii Dk , …, Dn-1, Dn duce sistemul din starea Sk-1 in starea finala Sn in mod optim.

Varianta 2: Daca sirul de decizii D1,  D2 , …, Dn-1, Dn duce sistemul din starea initiala S0 in starea finala Sn in mod optim, atunci:

, secventa de decizii D1 , …, Dk-1, Dk duce sistemul din starea initiala S0 in starea Sk in mod optim.

In functie de varianta principiului optimalitatii identificata din analiza problemei, metoda de abordare a poate fi:

Metoda inainte – aplicata in cazul verificarii principiului optimalitatii in forma 1.

Metoda inapoi – aplicata in cazul verificarii principiului optimalitatii in forma 2.

Esenta celor doua variante (inainte sau inapoi) este aceiasi si consta in identificarea si rezolvarea relatiilor de recurenta referitoare la criteriul de optimizat sau la valoarea ce se calculeaza.

Metoda inainte opereaza in urmatoarele 4 faze:

1.            prin relatiile de recurenta se vor calcula optimele corespunzatoare starilor indepartate de starea finala in functie de optimele corespunzatoare starilor apropiate de starea finala (practic in aceasta faza se completeaza tabela de informatii intermediare)

2.            se determina deciziile care leaga optimele determinate in faza anterioara

3.            se afla optimul total

4.            se determina solutia problemei reprezentata de un sir de decizii constituit prin compunerea deciziilor de la etapa 2, in mod directe, de la inceput spre sfarsit (inainte)

Metoda inapoi este duala metodei descrise anterior si opereaza in urmatoarele 4 faze:

1.            prin relatiile de recurenta se vor calcula optimele corespunzatoare starilor apropiate  de starea finala in functie de optimele corespunzatoare starilor departate de starea finala

2.            se determina deciziile care leaga optimele determinate in faza anterioara

3.            se afla optimul total

4.            se determina solutia problemei reprezentata de un sir de decizii constituit prin compunerea deciziilor de la etapa 2, in mod invers, de la sfarsit spre inceput (inapoi)

Desi pare o metoda generala de rezolvare a problemelor de optim, aplicabilitatea programarii dinamice este restransa doar la acele probleme pentru care se poate demonstra principiul optimalitatii.

Problema 1 Subsir crescator de lungime maxima (metoda inainte)

Se da  o multime (sir) neordonata de elemente.

Se cere determinarea lui B, , sir ordonat crescator, de lungime maxima.

Exemplu: in sirul 7 1 4 2 5 3, cel mai lung subsir crescator este 1,2,3

Rezolvarea naiva a acestei probleme ar aceea prin care se vor determina toate subsirurile crescatoare urmand ca ulterior sa se extraga acela care are lungime maxima. Rezolvarea aceasta este corecta, insa neeficienta prin necesitatea de a construi si retine toate subsirurile lui sirului dat.

O solutie ingenioasa are fi sa se calculeze si sa se retina intr-o tabela doar lungimile tuturor subsirurilor crescatoare, fara a le genera si pe acestea.

In exemplul anterior, subsirurile crescatoare si lungimile acestora sunt:

Subsirul

Lungimea

7

1 2 3

4 5

2 3

5

3

1

3

2

2

1

1

Se poate observa ca daca subsirul 3 are lungime 1, subsirul care il contine are lungimea mai mare cu 1, respectiv 2 (1+1) si subsirul maximal 1 2 3  are lungime 3 (2+1).

Astfel: Daca subsirul 1 2 3 este subsirul optimal crescator de lungime maxima (3), care incepe cu 1,  atunci:

2 3 este subsirul optimal crescator de lungime maxima (2) care incepe cu 2 si

3 este subsirul optimal crescator de lungime maxima (1) care incepe cu 3

Generalizand, daca  este subsirul optimal crescator de lungime n care incepe cu : atunci:

       -  este subsirul optimal optimal de lungime n-1 care incepe cu i2

       -  este optimal de lungime n-2  care incepe cu i3

       - …..

       -  este subsirul optimal de lungime maxima care incepe cu ik,

Prin reformularea observatiilor anterioare se identifica principiul optimalitatii in varianta 1, fapt pentru care se va aplica metoda inainte:

Etapa_1&2: se vor calcula pe baza relatiilor de recurenta, pentru fiecare element al sirului initial  lungimea celui mai mare subsir crescator care se poate forma incepand de la el.

Notam L(k) lungimea celui mai mare subsir crescator care se poate forma incepand elementul de pe pozitia k din sirul dat. Relatia de recurenta este urmatoarea:

L(k):=} si k }

Algoritm Determinare_Lungimi este:

   L(n)=1

Pentru k=n-1 la 1 cu pas -1

       L(k)=1

       Cauta  i>k astfel incat  si

        Daca s-a gasit (i) atunci

                   L(k)=L(i)+1

       SfDaca

SfPentru

SfAlgoritm

Etapa3: Se determina maximul din tabela lungimilor L. Fie acesta L(imax). In acest caz:

-          L(imax) – reprezinta lungimea subsirului crescator de lungime maxima (lungimea solutiei)

-          imax – reprezinta indicele din sirul initial de la care incepe subsirul solutie

Etapa4: Se determina solutia problemei (subsirul crescator de lungime maxima), prin construire, pornind de la elementul de pe pozitia imax pana la elementul de pe pozitia n, retinandu-se doar elementele care verifica relatia de ordine.

Problema 2: Problema Robotului (metoda inapoi)



Se da o tabla impartita in m linii si n coloane:

Fiecare casuta a tablei contine obiecte de valori diferite (numere naturale):  .

Un robot situat in casuta de start  va traversa tabla pentru a ajunge la casuta finala  realizand doar miscarile posibile:

-          la dreapta cu o casuta: ()

-          in jos cu o casuta: ()

si colecteaza obiectele din casutele traversate.

Sa se determine secventa de miscari (drumul) a robotului astfel incat suma valorilor colectate la iesire sa fie maxima.

 

Exemplu:

Pentru urmatorul caz:

2

0

7

1

4

0

3

0

0

5

1

0

2

4

1

2

Solutia imediata este parcurgerea casutelor: (1,1)-(2,1)-(2,2)-(3,2)-(4,2)-(4,3)-(4,4), robotul colecteaza obiecte de valoare totala: 18 reprezentand suma maxima a sumelor colectate prin parcurgerea oricaror drumuri de la casuta initiala la casuta finala.

Se observa ca suma maxima cu care ajunge robotul in casuta finala poate fi obtinuta fie prin mutarea anterioara de pe coloana din stanga (n-1), fie prin mutarea anterioara din celula de pe linia (m-1). Astfel, daca suma finala a valorilor este maxima, atunci prin scaderea valorii comune continuta in , inseamna ca si drumurile partiale efectuate pana in celula sau  sunt de suma maxima partiala.

Generalizand:

-          Daca in celula  robotul a ajuns cu transport maxim de la celula initiala , efectuand ultima mutare dreapta (robotul ajunge in celula  din celula ) atunci in celula  robotul a ajuns cu suma maxima posibila de la  la .

-          Daca in celula  robotul a ajuns cu transport maxim de la celula initiala , efectuand ultima mutare jos (robotul ajunge in celula  din celula ) atunci in celula  robotul a ajuns cu suma maxima posibila de la  la .

Observatie: Ultima formulare este chiar Principiul optimalitatii exprimat in varianta 2:

Daca secventa de celule parcurse de la celula : (1,1) la celula (m,n) este de transport maxim:  , …,,,, … ,

Atunci , secventa de celule parcurse de la (1,1) la (,) este de transport maxim: , …,,,

Din observatiile anterioare, se poate deduce o relatie de recurenta prin care pot fi determinate sumele maxime cu care robotul poate ajunge in oricare celula a tablei A:

,  si

Pe baza relatiei de recurenta se va construi o tabela suplimentara care retine valorile sumelor maxime pe care le poate colecta robotul pana in fiecare celula a tablei initiale:

Algoritm DeterminareSumeMaxime este:

     S(0,1):=0

     S(1,0):=0

     Pentru i de la 1 la m

                 Pentru j de la 1 la n

                             Daca  S(i-1,j)> S(i,j-1) atunci

                                         S(i,j):= S(i-1,j)+ ai,j

                             Altfel

                                         S(i,j):= S(i,j-1)+ ai,j

                             SfDaca

                 SfPentru

     SfPentru

SfAlgoritm

Se constata ca ultima valoare determinata,  reprezinta chiar suma maxima a drumului complet al robotului, iar solutia problemei–vectorul format din casutele (i,j) traversate cu transport maxim, poate fi determinata printr-o parcurgerea inversa a matricei S :

            Algoritm RefacereDrum este:

Vector(1)Ü (m,n)  // Retine casuta  finala (m,n)

Fie  i=m, j=n, k=2

Cattimp ((i,j)≠(1,1))

Daca  >  atunci

                        Vector(k)Ü (i-1,j) //Retine casuta (i-1,j),

i=i-1

k=k+1

Altfel

                        Vector(k)Ü (i,j-1) //Retine casuta (i,j-1)

                        j=j-1

k=k+1

SfDaca

SfCattimp

  //Vectorul de casute parcurs invers este solutia problemei.

            Pentru i de la k la 1 cu pas -1

                        Tipareste Vector(i)

            SfPentru

SfAlgoritm

Observatie: Tehnica descrisa pentru rezolvarea problemei robotului este Programarea dinamica, varianta metodei inapoi.

Probleme:

  1. Scrieti un program de rezolvare a problemei robotului.
  2. Scrieti programul de rezolvare a problemei 1: Subsir crescator de lungime maxima.
  3. Scrieti un program care determina cel mai lung subsir comun al doua siruri date.

 


BIBLIOGRAFIE:

  1. Liviu Negrescu, Limbajele C si C++ pentru incepatori Vol. I (p.1 si 2) - Limbajul C , Editura Albastra, Cluj-Napoca,  2002.
  2. Brian Kernighan, Dennis Ritchie, The C Programming Language, Second Edition, Prentice Hall, 1988.
  3. Bazil Parv, Alexandru Vancea, Fundamentele limbajelor de programare, Editura Albastra, Cluj Napoca, 1996.
  4. Knuth, Donald E., Arta programarii calculatoarelor: Algoritmi fundamentali. vol.1 , Editura Teora, Bucuresti, 1999.
  5. Doina Logofatu, Algoritmi fundamentali in C++. Aplicatii, Editura Polirom, Iasi, 2007.
  6. Frentiu M, Parv B., Elaborarea programelor. Metode si tehnici moderne, Editura PROMEDIA, Cluj-Napoca, 1994.
  7. Petrovici V., Goicea F., Programare in limbajul C, Editura Tehnica, Bucuresti, 1993.

DISTRIBUIE DOCUMENTUL

Comentarii


Vizualizari: 1122
Importanta: rank

Comenteaza documentul:

Te rugam sa te autentifici sau sa iti faci cont pentru a putea comenta

Creaza cont nou

Distribuie URL

Adauga cod HTML in site



Termeni si conditii de utilizare | Contact
© SCRIGROUP 2019. All rights reserved