0_metoda_greedy.doc

Metoda Greedy

Prof. Negrilescu Nicolae

Colegiul National Vlaicu Voda

Curtea de Arges

Metoda Greedy

Metoda Greedy este una din cele mai directe tehnici de proiectare a algoritmilor care se aplic la o varietate larg de probleme.

1. Descrierea metodei

Se d o mulime A cu n elemente i se cere s se determine o submulime a sa(B) care satisface anumite restricii. Aceast submulime se numete soluie posibil. Se cere s se determine o soluie posibil care fie s maximizeze fie s minimizeze o anumit funcie obiectiv dat. Aceast soluie posibil se numete soluie optim.

Metoda Greedy lucreaz n pai astfel:

1. se iniializeaz mulimea soluiilor (B) la mulimea vid (B=()

2. se alege un anumit element x( A

3. se verific dac elementul ales poate fi adugat la mulimea soluiilor, dac da atunci va fi adugat (B=B({x})4. procedeul continu astfel, repetitiv, pn cnd au fost determinate toate elementele din mulimea soluiilor

Observaie. Metoda Greedy nu caut s determine toate soluiile posibile ( care ar putea fi prea numeroase) i apoi s aleag din ele pe cea optim, ci caut s introduc direct un element x n soluia optim.

2. Probleme pentru care metoda Greedy determin soluia optim

2.1 Determinarea arborelui parial de cost minim

Se d un graf G. Se cere determinarea arborelui parial de cost minim

Algoritmul de rezolvare pe care l folosim se bazeaz pe tehnica Greedy:

1. La nceput nu avem un arbore (avem mai muli arbori, fiecare dintre acetia fiind format dintr-un singur nod), sortm muchiile n ordine cresctoare a costurilor

2. Se alege o muchie x (muchiile se aleg de la cea mai mic la cea mai mare)

3. Verificm dac muchia poate fi adugat (dac nu se produc cicluri)

4. Continum pn cnd avem n-1 muchii (n = numrul de noduri)

2.2 Problema rucsacului

Se 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.

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=G1/V1, (2=G2/V2, ,(n=Gn/Vn i vom sorta obiectele n ordine descresctoare a densitii. Acestea fiind realizate aplicm metoda Greedy:

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

3. Probleme pentru care metoda Greedy nu determin soluia optim

3.1 Problema determinrii drumului minim

Se d un graf G i se cere s se determine drumul minim ntre dou noduri ale sale.

Metoda Greedy se poate aplica astfel:

1. Pornim din nodul de start x.

2. Alegem cel mai scurt drum spre nodul urmtor.

3. Repetm pn cnd se ajunge n nodul destinaie

Pentru exemplele urmtoare metoda gsete drumul optim ntre 1 i 4 ca fiind

1 2 3 4,

n acest caz soluia este corect.

Dar n cazul de mai jos metoda d gre.

3.2 Problema plii unei sume cu bancnote(monezi) de valoare dat

S se efectueze plata unei sume S utiliznd un numr minim de monezi. Valorile monezilor se cunosc.

Metoda Greedy se poate aplica astfel:

1. Fie suma care a mai rmas de pltit X=S

2. Se alege moneda de valoare maxim Mi (astfel nct Mi