Strutture dati - Algoritmi avidi

Un algoritmo è progettato per ottenere una soluzione ottimale per un dato problema. Nell'approccio dell'algoritmo avido, le decisioni vengono prese dal dominio della soluzione dato. Essendo avido, viene scelta la soluzione più vicina che sembra fornire una soluzione ottimale.

Gli algoritmi avidi cercano di trovare una soluzione ottimale localizzata, che alla fine può portare a soluzioni ottimizzate a livello globale. Tuttavia, gli algoritmi generalmente avidi non forniscono soluzioni ottimizzate a livello globale.

Conteggio delle monete

Questo problema è contare fino a un valore desiderato scegliendo il minor numero di monete possibili e l'approccio avido costringe l'algoritmo a scegliere la moneta più grande possibile. Se ci vengono fornite monete da ₹ 1, 2, 5 e 10 e ci viene chiesto di contare ₹ 18, la procedura avida sarà:

  • 1 - Seleziona una moneta da ₹ 10, il conteggio rimanente è 8

  • 2 - Quindi seleziona una moneta da ₹ 5, il conteggio rimanente è 3

  • 3 - Quindi seleziona una moneta da ₹ 2, il conteggio rimanente è 1

  • 4 - E infine, la selezione di una moneta da ₹ 1 risolve il problema

Tuttavia, sembra che funzioni bene, per questo conteggio dobbiamo scegliere solo 4 monete. Ma se modifichiamo leggermente il problema, lo stesso approccio potrebbe non essere in grado di produrre lo stesso risultato ottimale.

Per il sistema valutario, dove abbiamo monete del valore 1, 7, 10, contare le monete per il valore 18 sarà assolutamente ottimale, ma per contare come 15, potrebbe utilizzare più monete del necessario. Ad esempio, l'approccio avido utilizzerà 10 + 1 + 1 + 1 + 1 + 1, per un totale di 6 monete. Considerando che lo stesso problema potrebbe essere risolto utilizzando solo 3 monete (7 + 7 + 1)

Quindi, possiamo concludere che l'approccio avido sceglie una soluzione ottimizzata immediata e potrebbe fallire laddove l'ottimizzazione globale è una delle principali preoccupazioni.

Esempi

La maggior parte degli algoritmi di rete utilizza l'approccio avido. Ecco un elenco di alcuni di loro:

  • Problema del commesso viaggiatore
  • Algoritmo Minimal Spanning Tree di Prim
  • Algoritmo Minimal Spanning Tree di Kruskal
  • Algoritmo Minimal Spanning Tree di Dijkstra
  • Grafico - Colorazione mappa
  • Grafico - Copertura vertice
  • Problema dello zaino
  • Problema di pianificazione del lavoro

Ci sono molti problemi simili che utilizzano l'approccio avido per trovare una soluzione ottimale.