El algoritmo del vecino más cercano fue uno de los primeros algoritmos utilizados para resolver aproximadamente el problema del viajante . En ese problema, el vendedor comienza en una ciudad aleatoria y visita repetidamente la ciudad más cercana hasta haber visitado todas. El algoritmo produce rápidamente un recorrido corto, pero normalmente no 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 cercano es fácil de implementar y se ejecuta rápidamente, pero a veces puede pasar por alto rutas más cortas que se notan fácilmente con el conocimiento humano, debido a su naturaleza "codiciosa". Como guía general, si las últimas etapas del recorrido son comparables en duración a las primeras etapas, entonces el recorrido es razonable; si son mucho mayores, entonces es probable que existan recorridos mucho mejores. Otra comprobación es utilizar un algoritmo como el 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 duración del recorrido calculada por el algoritmo vecino más cercano es mayor que r veces la duración del recorrido óptimo. Además, para cada número de ciudades hay una asignación de distancias entre las ciudades para las cuales la heurística del vecino más cercano produce el peor recorrido posible. (Si el algoritmo se aplica en cada vértice como vértice inicial, el mejor camino encontrado será mejor que al menos N/2-1 otros recorridos, donde N es el número de vértices) .
Es posible que el algoritmo del vecino más cercano no encuentre ningún recorrido factible, incluso cuando exista uno.