Sisteme de asistarea a deciziilor în organizarea fabricației - metoda Greedy

1. Descriere

Metoda Greedy este una din cele mai directe tehnici de proiectare a algoritmilor care se aplică la o varietate largă de probleme.In general,aceasta metoda se aplica problemelor de optimizare.Specificul acestei metode consta in faptul ca se construieste solutia optima pas cu pas,la fiecare pas fiind selectat(sau "inghitit") in solutie elementul care pare "cel mai bun"la momentul respectiv,in speranta ca va duce la solutie optima globala.

2. Prezentare

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. Multimea B este vida la inceput

2. Se alege un element din A care pare a fi solutia optima la pasul i

3. Se verifică dacă elementul ales poate fi adăugat la mulţimea soluţiilor, dacă da atunci va fi adăugat

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ă.Acest lucru duce la eficienta algorimilor Greedy,insa nu conduc in mod necesar la o solutie optima si nici nu este posibila formularea unui criteriu general conform caruia sa putem stabili excat daca metoda Greedy rezolva sau nu o anumita problema de optimizare.Acest motiv duce la insotirea fiecarei rezolvari prin metoda Greedy a unei demonstratii matematice(in general prin inductie).

3. Algoritmul general pentru Greedy

Cazul I

B = multimea vida

for (i=0; i<n; i++)

{

x = alege( A);

if (posibil( B ,x))

* adauga elementul x la multimea B;

}

Cazul II

B = multimea vida

prelucreaza(A, v)

for (i=0; i<n; i++)

{

x = v[i];

if (posibil( B ,x))

* adauga elementul x la multimea B;

}