Algoritmo del vicino più prossimo

L' algoritmo del vicino più prossimo è stato uno dei primi algoritmi ideati per risolvere in modo approssimato il problema del commesso viaggiatore. In tale problema, il commesso viaggiatore parte da una città casuale e visita ripetutamente la città più vicina fino a quando non le ha visitate tutte. L'algoritmo produce rapidamente un percorso breve, ma di solito non quello ottimale.

L'algoritmo rientra nella classe degli algoritmi di ricerca approssimata per strutture dati a grafo. Nel caso pessimo rientra nella classe di complessità ${\displaystyle \Theta (N^{2})}$ mentre la sua classe di complessità in spazio è ${\displaystyle \Theta (N)}$.

Algoritmo

Passi dell'algoritmo (dato un grafo):

1. Inizializzare tutti i vertici come non visitati.
2. Selezionare un vertice arbitrario ${\displaystyle u}$ , impostarlo come vertice corrente e contrassegnare ${\displaystyle u}$  come visitato.
3. Trovare l'arco più corto che collega il vertice corrente u a un vertice non visitato ${\displaystyle v}$ .
4. Impostare ${\displaystyle v}$  come vertice corrente ${\displaystyle u}$  e contrassegnare v come visitato.
5. Se tutti i vertici del dominio vengono visitati, terminare. Altrimenti, andare al passo 3.

L'output dell'algoritmo è dato come sequenza dei vertici visitati.

L'algoritmo del vicino più prossimo è facile da implementare e di veloce esecuzione, ma a volte può tralasciare percorsi più brevi, facilmente individuabili con l'intuito umano, a causa della sua natura "avida". In generale, se le ultime tappe del percorso sono di lunghezza paragonabile a quelle iniziali, allora esso è accettabile; se sono molto più lunghe, è probabile che esistano percorsi molto migliori. Un altro controllo da fare consiste nell'utilizzare un metodo come l'algoritmo del limite inferiore per stimare se questo percorso è sufficientemente buono.

Nel caso peggiore, l'algoritmo produce un percorso molto più lungo di quello ottimale. Per essere precisi, per ogni costante ${\displaystyle r}$  esiste un'istanza del problema del commesso viaggiatore tale che la lunghezza del percorso calcolato dall'algoritmo del vicino più prossimo è maggiore di ${\displaystyle r}$  volte la lunghezza del percorso ottimale. Inoltre, per ogni numero di città esiste un'assegnazione di distanze tra le città per cui l'euristica del vicino più prossimo produce l'unico percorso peggiore possibile: se l'algoritmo viene applicato su ogni vertice come vertice di partenza, il percorso migliore trovato sarà migliore di almeno ${\displaystyle N/2-1}$  altri percorsi, dove ${\displaystyle N}$  è il numero di vertici.^[1]

L'algoritmo del vicino più prossimo potrebbe non essere capace di trovare alcun percorso valido, anche se in realtà ne esiste uno.

Note

1. ^ Gregory Gutin, Anders Yeo e Alexey Zverovich, Traveling salesman should not be greedy: domination analysis of greedy-type heuristics for the TSP, in Discrete Applied Mathematics, vol. 117, n. 1, 15 marzo 2002, pp. 81–86, DOI:10.1016/S0166-218X(01)00195-0. URL consultato l'8 agosto 2025.

Riferimenti bibliografici

• G. Gutin, A. Yeo and A. Zverovitch, Exponential Neighborhoods and Domination Analysis for the TSP, in The Traveling Salesman Problem and Its Variations, G. Gutin and A.P. Punnen (eds.), Kluwer (2002) and Springer (2007).
• J. Bang-Jensen, G. Gutin e A. Yeo, When the greedy algorithm fails. Discrete Optimization 1 (2004), 121–127.
• G. Bendall e F. Margot, Greedy Type Resistance of Combinatorial Problems, Discrete Optimization 3 (2006), 288–298.