Metoda Greedy

Definiție :

Metoda Greedy presupune că problemele care urmează să fie rezolvate au următoarea structură:   * se dă o mulțime A={a1,a2,a3…an } formată din n elemente.                                                      *  se cere să determinăm o submulțime B ( unde B se include în A ) care                                      îndeplinește anumite condiții pentru a fi acceptată ca soluție .

Particularități :

Metoda Greedy nu încearcă să determine toate soluțiile posibile și să o stabilească ulterior pe cea optimală, comparînd soluțiile.Ea alege pe rînd cîte un element ca ulterior să-l adauge în mulțimea de soluții. De aici și vine denumirea de (Greedy) – ceea ce se traduce ( lacom = nesățios )

Domeniu de utilizare :

Algoritmii greedy (greedy = lacom) sunt in general simpli si sunt folositi la probleme de optimizare, cum ar fi: sa se gaseasca cea mai buna ordine de executare a unor lucrari pe calculator, sa se gaseasca cel mai scurt drum intr-un graf etc. In cele mai multe situatii de acest fel avem:

  • multime de candidati (lucrari de executat, varfuri ale grafului etc).

  • o functie care verifica daca o anumita multime de candidati constituie o solutie posibila.

  • o functie care verifica daca o multime de candidati este fezabila, adica daca este posibil sa completam aceasta multime astfel incat sa obtinem o solutie posibila, nu neaparat optima, a problemei

  • o functie de selectie care indica la orice moment care este cel mai promitator dintre candidatii inca nefolositi.

  • o functie obiectiv care da valoarea unei solutii (timpul necesar executarii tuturor lucrarilor intr-o anumita ordine, lungimea drumului pe care l-am gasit etc); aceasta este functia pe care urmarim sa o optimizam (minimizam/maximizam).

    Exemplu și aplicație :

    Un exemplu simplu de algoritm greedy este algoritmul folosit pentru rezolvarea urmatoarei probleme. Sa presupunem ca dorim sa dam restul unui client, folosind un numar cat mai mic de monezi. In acest caz, elementele problemei sunt:

    • candidatii: multimea initiala de monezi de 1, 5, si 25 unitati, in care presupunem ca din fiecare tip de moneda avem o cantitate nelimitata

    • solutie posibila: valoarea totala a unei astfel de multimi de monezi selectate trebuie sa fie exact valoarea pe care trebuie sa o dam ca rest

    • multime fezabila: valoarea totala a unei astfel de multimi de monezi selectate nu este mai mare decat valoarea pe care trebuie sa o dam ca rest

    • functia de selectie: se alege cea mai mare moneda din multimea de candidati ramasa

    • functia obiectiv: numarul de monezi folosite in solutie; se doreste minimizarea acestui numar.

sch

Utilizarea metodei în alte țări
În alte țări, tehnica Greedy este utilizată cu rolul de a construi soluția optimă pas cu pas, la fiecare pas fiind selectat în soluție elementul care pare optim la momentul respectiv. Problemele la care este aplicată metoda respectivă sunt probleme de optimizare, majoritatea constînd în determinarea unei submulţimi B a unei mulţimi A cu n elemente care să îndeplinească anumite condiţii pentru a fi acceptată.

 

Problema MGreedy

 

Verifica Cunostinetele

Test

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s