Un problema di ottimizzazione è un tipo di problema in cui l’obiettivo è trovare la migliore soluzione possibile tra un insieme di soluzioni ammissibili.
- ogni soluzione ammissibile (ovvero che soddisfa tutte le condizioni imposte dal problema) ha un valore associato chiamato costo o beneficio.
- l’obiettivo può essere minimizzarlo o massimizzarlo: ci sono quindi problemi di minimizzazione e problemi di massimizzazione
problema di copertura tramite nodi
Dato un grafo indiretto , una sua copertura tramite nodi è un sottoinsieme dei suoi nodi tale che tutti gli archi di hanno almeno un estremo in .
ipotesi greedy (errata)
Una strategia greedy potrebbe essere questa:
- finché ci sono archi non coperti, inserisci in il nodo che copre il massimo numero di archi ancora scoperti
Questa soluzione non trova la copertura ottimale. Per esempio, dato questo grafo :
L’algoritmo sceglie come primo nodo (che copre 4 archi). Dopodiché, tutti i nodi restanti coprono lo stesso numero di archi (2) e l’algoritmo dovrà quindi sceglierne uno per coppia. Il sottoinsieme avrà quindi 5 nodi.
La soluzione ottimale ha però solo 4 nodi:
Si può dimostrare che questo algoritmo sbaglia di massimo nodi. (non ottimale, si vuole trovare un’euristica che sbagli massimo di una costante)
