Algoritmo del vecino más cercano

El algoritmo del vecino más cercano fue uno de los primeros algoritmos utilizados para resolver de forma aproximada el problema del viajante . En este problema, el viajante parte de una ciudad al azar y visita repetidamente la ciudad más cercana hasta haberla visitado todas. El algoritmo genera rápidamente un recorrido corto, pero generalmente no el óptimo.

Estos son los pasos del algoritmo:

1. Inicializa todos los vértices como no visitados.
2. Seleccione un vértice arbitrario y establézcalo como el vértice actual u . Marque u como visitado.
3. Encuentra la arista más corta que conecta el vértice actual u con un vértice no visitado v .
4. Establece v como el vértice actual u . Marca v como visitado.
5. Si se han visitado todos los vértices del dominio, finalice el proceso. De lo contrario, pase al paso 3.

La secuencia de los vértices visitados es el resultado del algoritmo.

El algoritmo del vecino más cercano es fácil de implementar y se ejecuta rápidamente, pero debido a su naturaleza "voraz", a veces puede pasar por alto rutas más cortas que resultan fácilmente perceptibles para un observador humano. Como regla general, si las últimas etapas del recorrido tienen una longitud comparable a las primeras, entonces el recorrido es razonable; si son mucho mayores, es probable que existan recorridos mucho mejores. Otra forma de comprobarlo es utilizar un algoritmo como el de límite inferior para estimar si este recorrido es suficientemente bueno.

En el peor de los casos, el algoritmo produce un recorrido mucho más largo que el ó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 ellas para la cual la heurística del vecino más cercano produce el único peor recorrido posible. (Si el algoritmo se aplica a 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). ^{[ 1 ]}

Es posible que el algoritmo del vecino más cercano no encuentre ningún recorrido factible, incluso cuando exista alguno.

• Algoritmo de Christofides

• G. Gutin, A. Yeo y A. Zverovitch, Vecindarios exponenciales y análisis de dominación para el TSP, en El problema del viajante y sus variaciones, G. Gutin y AP Punnen (eds.), Kluwer (2002) y Springer (2007).
• G. Gutin, A. Yeo y A. Zverovich, El problema del viajante no debería ser codicioso: análisis de dominación de heurísticas de tipo codicioso para el TSP . Discrete Applied Mathematics 117 (2002), 81–86.
• J. Bang-Jensen, G. Gutin y A. Yeo, Cuando falla el algoritmo voraz . Optimización discreta 1 (2004), 121–127.
• G. Bendall y F. Margot, Resistencia de tipo voraz de problemas combinatorios , Optimización discreta 3 (2006), 288–298.