Cuprins:
Definiție - Ce înseamnă Greedy Algorithm?
Un algoritm lacom este o strategie algoritmică care face cea mai bună alegere optimă la fiecare etapă mică, cu scopul ca acest lucru să conducă în cele din urmă la o soluție optimă la nivel global. Aceasta înseamnă că algoritmul alege cea mai bună soluție în acest moment, fără a ține cont de consecințe. Alege cea mai bună producție imediată, dar nu ia în considerare imaginea de ansamblu, de aceea este considerată lacomă.
Techopedia explică Algoritmul Greedy
Un algoritm lacom funcționează prin alegerea celui mai bun răspuns posibil în fiecare etapă și apoi trecerea la următorul pas până când ajunge la final, fără a ține cont de soluția generală. Spera doar că calea pe care o parcurge este cea optimă la nivel global, dar, așa cum a fost dovedit din nou, această metodă nu vine adesea cu o soluție optimă la nivel global. De fapt, este complet posibil ca cele mai optime soluții pe termen scurt să conducă la cel mai prost rezultat global posibil.
Gândiți-vă la aceasta ca luând o mulțime de comenzi rapide într-o afacere de fabricație: pe termen scurt sunt economisite cantități mari în costul de fabricație, dar acest lucru duce la scăderea, deoarece calitatea este compromisă, ceea ce duce la întoarcerea produselor și la vânzări scăzute pe măsură ce clienții fac cunoștință cu Produs „ieftin”. Dar acest lucru nu este întotdeauna cazul, există o mulțime de aplicații în care algoritmul lacom funcționează cel mai bine pentru a găsi sau aproxima soluția optimă la nivel global, cum ar fi construirea unui arbore Huffman sau un arbore de învățare a deciziilor.
De exemplu: luați calea cu cea mai mare sumă totală. Un algoritm lacom ar lua calea albastră, ca urmare a nevazului, mai degrabă decât calea portocalie, care produce cea mai mare sumă.
Componente:
- Un set de date candidat care are nevoie de o soluție
- O funcție de selecție care alege cel mai bun contribuitor la soluția finală
- O funcție de fezabilitate care ajută funcția de selecție, determinând dacă un candidat poate fi contribuitor la soluție
- Funcție obiectivă care atribuie o valoare unei soluții parțiale
- O funcție de soluție care indică faptul că soluția optimă a fost descoperită
