0_metoda_greedy.doc
TRANSCRIPT
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