El algoritmo del vecino más próximo fue uno de los primeros algoritmos utilizados para resolver de forma aproximada el problema del viajante de comercio . En ese problema, el viajante comienza en una ciudad al azar y visita repetidamente la ciudad más cercana hasta que ha visitado todas. El algoritmo produce rápidamente un recorrido corto, pero por lo general no es el óptimo.
Estos son los pasos del algoritmo:
La secuencia de los vértices visitados es la salida del algoritmo.
El algoritmo del vecino más próximo es fácil de implementar y se ejecuta rápidamente, pero a veces puede pasar por alto rutas más cortas que son fáciles de detectar con la percepción humana, debido a su naturaleza "codiciosa". Como guía general, si las últimas etapas del recorrido son comparables en longitud a las primeras etapas, entonces el recorrido es razonable; si son mucho más largas, entonces es probable que existan recorridos mucho mejores. Otra comprobación es utilizar un algoritmo como el algoritmo de límite inferior para estimar si este recorrido es lo suficientemente bueno.
En el peor de los casos, el algoritmo da como resultado un recorrido mucho más largo que el recorrido óptimo. Para ser precisos, para cada constante r existe una instancia del problema del viajante tal que la longitud del recorrido calculado por el algoritmo del vecino más cercano es mayor que r veces la longitud del recorrido óptimo. Además, para cada número de ciudades existe una asignación de distancias entre las ciudades para las cuales la heurística del vecino más cercano produce el único peor recorrido posible. (Si el algoritmo se aplica en cada vértice como vértice de inicio, el mejor camino encontrado será mejor que al menos N/2-1 otros recorridos, donde N es el número de vértices). [1]
Es posible que el algoritmo del vecino más cercano no encuentre ningún recorrido factible, incluso cuando exista alguno.