Tehnici de elaborare a algoritmilor Metoda Greedy

Scopuri i Obiective S

studiez Metoda Greedy; S aflu schema general a unui algoritm bazat pe metoda greedy; S cercetez o problem rezolvat prin metoda greedy.

Metoda Greedy este una din cele mai directe tehnici de proiectare a algoritmilor care se aplica la o varietate larga de probleme.In general,aceasta metoda se aplica problemelor de optimizare.Specificul acestei metode consta in faptul ca se construieste solutia optima pas cu pas,la fiecare pas fiind selectat(sau inghitit) in solutie elementul care pare cel mai bunla momentul respectiv,in speranta ca va duce la solutie optima globala.Algoritmii greedy (greedy = lacom) sunt n general simpli i sunt folosii la probleme de optimizare, cum ar fi: s se gseasc cea mai buna ordine de executare a unor lucrri pe calculator, s se gseasc cel mai scurt drum ntr-un graf etc.

Schema general a unui algoritm bazat pe metoda Greedy:

While ExistaElemente do begin AlegeUnElement(x);IncludeElementul(x) end.

Nu tuturor problemelor li se pot aplica algoritmi de tip Greedy. Pentru problemele pentru care nu se cunosc algoritmi care necesit timp polinomial, se caut soluii, chiar dac nu optime, atunci apropiate de acestea, dar care au fost obinute n timp util. Multe din aceste soliii sunt obinute cu Greedy. Astfel de agoritmi se numesc algoritmi euristici

Problemele au urmtoarea structur :

- Se da o multime A={a1 a2, , an}- Se cere sa determinam o submultime B a multimii A, care indeplineste anumite conditii pentru a fi acceptata in calitate de solutie.

Se da o multime A cu n elemente si se cere sa se determine o submultime a sa(B) care satisface anumite restrictii. Aceasta submultime se numeste solutie posibila. Se cere sa se determine o solutie posibila care fie sa maximizeze fie sa minimizeze o anumita functie obiectiv data. Aceasta solutie posibila se numeste solutie optima. Metoda Greedy lucreaza in pasi astfel: 1. Multimea B este vida la inceput 2. Se alege un element din A care pare a fi solutia optima la pasul 1. 3. Se verifica daca elementul ales poate fi adaugat la multimea solutiilor, daca da atunci va fi adaugat 4. Procedeul continua astfel, repetitiv, pana cand au fost determinate toate elementele din multimea solutiilor

Problema rucsaculuiSe d un rucsac de volum V i mai multe obiecte de greuti G1, G2,, Gn ce au volumele V1, V2,, Vn. Se cere s se ncarce rucsacul la greutatea maxim utiliznd cte un obiect din fiecare tip. n=Gn/Vn i vom sorta obiectele n ordine descresctoare a densitii. Acestea fiind realizate aplicm metoda Greedy:2=G2/V2, ,1=G1/V1. Se observ c cea mai bun metod de ncrcare a rucsacului ar fi s introducem obiectele n ordine descresctoare a densitii acestora. Deci vom calcula densitile obiectelor 1. La nceput volumul obiectelor adugate Vo=0 2. Se alege un obiect (n ordine descresctoare a densitii) 3. Verificm dac putem aduga obiectul ( dac prin adugare nu se depete volumul admis) 4. Repetm pn cnd s-au terminat obiectele sau s-a atins volumul dorit .

Executat : Casian Anastasia, eleva clasei a XI-a B Coordonator : Snegur Tatiana