Metoda Greedy

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 mulţime A cu n elemente şi se cere să se determine o submulţime a sa(B) care satisface anumite restricţii. Această submulţime se numeşte soluţie posibilă. Se cere să se determine o soluţie posibilă care fie să maximizeze fie să minimizeze o anumită funcţie obiectiv dată. Această soluţie posibilă se numeşte soluţie optimă. Metoda Greedy lucrează în paşi astfel: 1. se iniţializează mulţimea soluţiilor (B) la mulţimea vidă (B=) 2. se alege un anumit element x A 3. se verifică dacă elementul ales poate fi adăugat la mulţimea soluţiilor, dacă da atunci va fi adăugat (B=B{x}) 4. procedeul continuă astfel, repetitiv, până când au fost determinate toate elementele din mulţimea soluţiilor Observaţie. Metoda Greedy nu caută să determine toate soluţiile 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 soluţia optimă. 2. Probleme pentru care metoda Greedy determină soluţia optimă 2.1 Determinarea arborelui parţial de cost minim Se dă un graf G. Se cere determinarea arborelui parţial de cost minim Algoritmul de rezolvare pe care îl folosim se bazează pe tehnica Greedy: 1. La început nu avem un arbore (avem mai mulţi arbori, fiecare dintre aceştia fiind format dintr-un singur nod), sortăm muchiile în ordine crescătoare a costurilor 2. Se alege o muchie x (muchiile se aleg de la cea mai mică la cea mai mare) 3. Verificăm dacă muchia poate fi adăugată (dacă nu se produc cicluri) 4. Continuăm până când avem n-1 muchii (n = numărul de noduri) 2.2 Problema rucsacului Se dă un rucsac de volum V şi mai multe obiecte de greutăţi G1, G2,…, Gn ce au volumele V1, V2,…, Vn. Se cere să se încarce rucsacul la greutatea maximă utilizând câte un obiect din fiecare tip. Se observă că cea mai bună metodă de încărcare a rucsacului ar fi să introducem obiectele în ordine descrescătoare a densităţii acestora. Deci vom calcula densităţile obiectelor 1=G1/V1, 2=G2/V2, …,n=Gn/Vn şi vom sorta obiectele în ordine descrescătoare a densităţii. Acestea fiind realizate aplicăm metoda Greedy: 1. La început volumul obiectelor adăugate Vo=0 2. Se alege un obiect (în ordine descrescătoare a densităţii) 3. Verificăm dacă putem adăuga obiectul ( dacă prin adăugare nu se depăşeşte volumul admis) 4. Repetăm până când s-au terminat obiectele sau s-a atins volumul dorit 3. Probleme pentru care metoda Greedy nu determină soluţia optimă 3.1 Problema determinării 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 următor. 3. Repetăm până când se ajunge în nodul destinaţie Pentru exemplele următoare metoda găseşte drumul optim între 1 şi 4 ca fiind 1 2 3 4, În acest caz soluţia este corectă. Dar în cazul de mai jos metoda dă greş. Descarca toata lectia