Algoritmo del vicino più vicino
Questi sono i passaggi dell’algoritmo:
- Inizializza tutti i vertici come non visitati.
- Seleziona un vertice arbitrario, impostalo come vertice corrente u. Segna u come visitato.
- Trova il bordo più corto che collega il vertice u corrente e un vertice v non visitato.
- Imposta v come vertice u corrente.Segna v come visitato.
- Se vengono visitati tutti i vertici del dominio, quindi terminare. Altrimenti, vai al punto 3.
La sequenza dei vertici visitati è l’output dell’algoritmo.,
L’algoritmo neighbour è facile da implementare ed esegue rapidamente, ma a volte può perdere percorsi più brevi che sono facilmente notabili con l’intuizione umana, a causa della sua natura “avida”. Come guida generale, se le ultime tappe del tour sono paragonabili in lunghezza alle prime fasi, allora il tour è ragionevole; se sono molto più grandi, allora è probabile che esistano tour molto migliori. Un altro controllo consiste nell’utilizzare un algoritmo come l’algoritmo lower bound per stimare se questo tour è abbastanza buono.,
Nel peggiore dei casi, l’algoritmo si traduce in un tour molto più lungo del tour ottimale. Per essere precisi, per ogni costante r esiste un’istanza del problema del commesso viaggiatore tale che la lunghezza del tour calcolata dall’algoritmo neighbour neighbour è maggiore di r volte la lunghezza del tour ottimale. Inoltre, per ogni numero di città c’è un’assegnazione delle distanze tra le città per le quali l’euristica del vicino più vicino produce il peggior tour possibile., (Se l’algoritmo viene applicato su ogni vertice come vertice iniziale, il miglior percorso trovato sarà migliore di almeno N/2-1 altri tour, dove N è il numero di vertici.)
L’algoritmo del vicino più vicino potrebbe non trovare affatto un tour fattibile, anche quando ne esiste uno.