Metoda Greedy

Fiind una dintre cele mai directe tehnici de proiectare a algoritmilor, metoda Greedy este folosită de cele mai multe ori pentru probleme de optimizare. Metoda iese în evidență prin faptul că este soluția optimă este construită pas cu pas. Astfel, la fiecare pas pe care îl parcurge algoritmul, este selectat ca fiind soluție elementul care pare cel mai potrivit la acel moment, având în vedere construirea unei soluții optime generale.

Metoda se aplică problemelor pentru care se dă o mulţime A cu n elemente şi pentru care trebuie determinată o submulţime a sa, S cu m elemente, care îndeplinesc anumite condiţii.

Principiul metodei Greedy:

• se iniţializează mulţimea soluţiilor S cu mulţimea vidă, S=Ø
• la fiecare pas se alege un anumit element x∈A (cel mai promiţător element la momentul respectiv) care poate conduce la o soluţie optimă
• se verifică dacă elementul ales poate fi adăugat la mulţimea soluţiilor: – dacă da, atunci va fi adăugat şi mulţimea soluţiilor devine S=S∪{x} – un element introdus în mulţimea S nu va mai putea fi eliminat – dacă nu, el nu se mai testează ulterior
• procedeul continuă, până când au fost determinate toate elementele din mulţimea soluţiilor

De asemenea, ai putea dori...

Lasă un răspuns

Acest sit folosește Akismet pentru a reduce spamul. Află cum sunt procesate datele comentariilor tale.