Metoda greedy

Metoda greedy

Se aplica problemelor in care se da o multime A continand n date (de orice natura si structura) de intrare cerandu-se sa se determine o submultime B (B A) care sa indeplineasca anumite conditii pentru a fi acceptata. Cum, in general, exista mai multe astfel de submultimi (numite solutii posibile) se mai da si un criteriu conform caruia dintre aceste submultimi sa alegem una singura (numita solutie optima) ca rezultat final. Foarte multe probleme de cautare se inscriu in acest tip.

Mentionam ca, in general, solutiile posibile au urmatoarele proprietati:

- se presupune ca Æ este solutie posibila;

- daca B este solutie posibilati C B atunci si C este solutie posibila;

Vom da in continuare o varianta a tehnicii greedy (denumire care in traducere inseamnna lacomie, inghitire) in care se porneste de la multimea vida. Apoi se alege pe rand, intr-un anumit fel, un element din A neales inca. Daca adaugarea lui la solutia partial anterior construita conduce la o solutie posibila, atunci se adauga, altfel se alege un nou element. Tot acest procedeu se repeta pentru toate elementele din A. Dam in continuare in pseudocod o procedura:

procedure GREEDY (n,A,B)

B:=Æ

for i=1,n do

call ALEGE (A,i,x);

call POSIBIL (B,x,cod);

if cod=1 then

call ADAUG (B,x);

endif;

endfor;

return;

end procedure

Despre procedurile apelate din GREEDY precizam urmatoarele:

procedura ALEGE furnizeaza in x un element din A a_jI si interschimba a_i cu a_j; daca la fiecare pas se cerceteaza a_i atunci procedura se simplifica;

procedura POSIBIL verifica daca elementul x poate fi adaugat sau nu multimii partiale construita pana la pasul curent furnizand o valoare booleana cod cu semnificatia:   

cod = 1, daca B U , este solutie posibila

cod = 0, altfel

procedura ADAUG inlocuieste pe B cu BÈ

Obs. Procedurile de mai sus nu sunt necesare intotdeauna, acest fapt depinzand de complexitatea problemei. Oricum trebuie retinut cadrul de rezolvare al acestui tip de problema.

Problema rezolvata

Se da o multime de valori reale X=. Se cere submultimea YÌX astfel ca å y /yIY, sa fie maxima.

Evident ca problema este foarte simpla (in Y trebuie introduse elementele strict pozitive din X; evitam sa mai construim procedurile ALEGE, POSIBIL, ADAUG) si vom da rezolvarea ei in pseudocod:

procedure SUMA (n,X,Y,k)

integer n,X(n),Y(n),k

k:=0;

for i=1,n do

if x(i) > 0 then k:=k+1;

y(k):=x(i)

endif;

endfor;

return;

end procedure

Probleme propuse

Se dau n siruri S₁,S₂,,S_n ordonate crescator, de lungimi L₁,L₂, ,L_n. Sa se obtina un sir S de lungime L₁+L₂++L_n cu toate elementele celor n siruri ordonate crescator (problema de interclasare).

Indicatie: Vom interclasa succesiv cate doua siruri in final obtinand sirul ordonat crescator. Complexitatea interclasarii a doua siruri A si B de lungimi a si b depinde direct proportional de a+b (pentru ca se fac a+b deplasari de elemente). Se pune problema gasirii ordinii optime in care trebuie efectuate aceste interclasari astfel ca numarul total de deplasari sa fie minim.

Vom da un exemplu pentru a lamuri mai bine lucrurile:

fie 3 siruri de lungimi (90,40,10). Interclasam sirul S₁ cu S₂ apoi sirul rezultat cu S₃; putem nota acest lucru formal prin (S₁+S₂)+S₃. Se obtin (90+40) + (130+10)=270 deplasari. Daca vom interclasa sirurile in ordinea (S₂+S₃)+S₁ vom obtine (40+10)+ (50+90)=190 de deplasari. De aici concluzia ca intotdeauna vom interclasa sirurile de lungimi minime din sirurile ramase.

Gasiti tripletele de numere pitagorice din N_n x N_n x N_n (prin N_n notat multimea ). Incercati optimizarea timpului de executie a programului.

Fie multimea m-combinarilor luate din n elemente si fie k<m un numar natural. Sa se dea un algoritm si apoi sa se scrie un program C astfel incat sa se determine o submultime de m-combinari cu proprietatea ca oricare doua m-combinari au cel mult k elemente comune.

Sa se determine multimile interior stabile (MIS) ale unui graf oarecare dat prin matricea sa de adiacenta.