Scrigroup - Documente si articole

Username / Parola inexistente      

Home Documente Upload Resurse Alte limbi doc  
AccessAdobe photoshopAlgoritmiAutocadBaze de dateCC sharp
CalculatoareCorel drawDot netExcelFox proFrontpageHardware
HtmlInternetJavaLinuxMatlabMs dosPascal
PhpPower pointRetele calculatoareSqlTutorialsWebdesignWindows
WordXml


Metoda greedy

c



+ Font mai mare | - Font mai mic



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 ajI si interschimba ai cu aj; daca la fiecare pas se cerceteaza ai 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 S1,S2,,Sn ordonate crescator, de lungimi L1,L2, ,Ln. Sa se obtina un sir S de lungime L1+L2++Ln 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 S1 cu S2 apoi sirul rezultat cu S3; putem nota acest lucru formal prin (S1+S2)+S3. Se obtin (90+40) + (130+10)=270 deplasari. Daca vom interclasa sirurile in ordinea (S2+S3)+S1 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 Nn x Nn x Nn (prin Nn 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.





Politica de confidentialitate | Termeni si conditii de utilizare



DISTRIBUIE DOCUMENTUL

Comentarii


Vizualizari: 714
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 2024 . All rights reserved