Ce este un algoritm greedy și în ce cazuri este aplicat?

Algoritmul greedy este o abordare pentru rezolvarea problemelor de optimizare, care la fiecare pas alege cea mai bună soluție locală (varianta cea mai avantajoasă din punctul de vedere al momentului actual), sperând că această secvență de soluții locale optime va duce la o soluție globală optimă. Nu ia în considerare posibilele consecințe ale alegerii curente asupra pașilor viitori.

Caracteristici:

• Simplitate: De obicei mai ușor de implementat decât programarea dinamică sau alte metode de optimizare.
• Viteză: Are adesea o complexitate computațională mai mică.
• Garanția de optimalitate: Nu garantează întotdeauna găsirea soluției globale optime. Garanția este valabilă doar pentru anumite clase de probleme.

Se aplică în probleme în care s-a demonstrat că alegerea local optimă la fiecare pas duce la o soluție globală optimă. Exemple:

• Problema selecției activităților: Alegerea celui mai mare număr de activități care nu se suprapun în timp.
• Problema rucsacului (cu fracționarea obiectelor): Când obiectele pot fi împărțite. Dacă nu, este o problemă de programare dinamică.
• Algoritmul lui Prim și Kruskal: Pentru găsirea arborelui acoperitor minim într-un graf.
• Algoritmul lui Dijkstra: Pentru găsirea celui mai scurt drum într-un graf cu greutăți nenegative.
• Codificarea Huffman: Pentru construirea unui cod prefix optim.

Exemplu de pseudocod pentru algoritmul de selecție a activităților:

Funcție SelecteazăActivitățile(activități):
  Sortează activitățile după timpul de finalizare
  activități_selectate = listă goală
  ultimul_timp_finalizare = 0

  Pentru fiecare activitate în activități:
    Dacă activitate.ora_de_început >= ultimul_timp_finalizare:
      Adaugă activitatea la activitățile_selectate
      ultimul_timp_finalizare = activitate.ora_de_finalizare

  Returnează activitățile_selectate

Este important să verifici dacă algoritmul greedy este aplicabil pentru o anumită problemă, deoarece altfel poate oferi o soluție suboptimă.