DAA - Metodo goloso

Tra tutti gli approcci algoritmici, l'approccio più semplice e diretto è il metodo Greedy. In questo approccio, la decisione viene presa sulla base delle informazioni attualmente disponibili senza preoccuparsi degli effetti della decisione corrente in futuro.

Gli algoritmi avidi costruiscono una soluzione parte per parte, scegliendo la parte successiva in modo tale da dare un vantaggio immediato. Questo approccio non riconsidera mai le scelte prese in precedenza. Questo approccio viene utilizzato principalmente per risolvere i problemi di ottimizzazione. Il metodo Greedy è facile da implementare e abbastanza efficiente nella maggior parte dei casi. Quindi, possiamo dire che l'algoritmo Greedy è un paradigma algoritmico basato sull'euristica che segue la scelta ottimale locale in ogni fase con la speranza di trovare una soluzione ottimale globale.

In molti problemi, non produce una soluzione ottimale sebbene dia una soluzione approssimativa (quasi ottimale) in un tempo ragionevole.

Componenti di Greedy Algorithm

Gli algoritmi Greedy hanno i seguenti cinque componenti:

  • A candidate set - Una soluzione viene creata da questo set.

  • A selection function - Utilizzato per scegliere il miglior candidato da aggiungere alla soluzione.

  • A feasibility function - Usato per determinare se un candidato può essere utilizzato per contribuire alla soluzione.

  • An objective function - Utilizzato per assegnare un valore a una soluzione o una soluzione parziale.

  • A solution function - Usato per indicare se è stata raggiunta una soluzione completa.

Aree di applicazione

L'approccio avido viene utilizzato per risolvere molti problemi, ad esempio

  • Trovare il percorso più breve tra due vertici utilizzando l'algoritmo di Dijkstra.

  • Trovare lo spanning tree minimo in un grafico usando l'algoritmo di Prim / Kruskal, ecc.

Dove l'approccio avido fallisce

In molti problemi, l'algoritmo Greedy non riesce a trovare una soluzione ottimale, inoltre può produrre una soluzione peggiore. Problemi come il venditore ambulante e lo zaino non possono essere risolti utilizzando questo approccio.