Algoritmo de vecino más cercano

El algoritmo del vecino más cercano fue uno de los primeros algoritmos utilizados para resolver aproximadamente el problema del viajante de comercio. En ese problema, el vendedor comienza en una ciudad al azar y visita repetidamente la ciudad más cercana hasta que haya visitado todas. El algoritmo produce rápidamente un recorrido corto, pero por lo general no es el óptimo.

Algoritmo

Estos son los pasos del algoritmo:

1. Iniciar todos los vértices como invisibles.
2. Seleccione un vértice arbitrario, establecerlo como el vértice actual u. Mark u como visitado.
3. Descubre el borde más corto que conecta el vértice actual u y un vértice invisible v.
4. Set v como el vértice actual u. Mark v como visitado.
5. Si todos los vértices en el dominio son visitados, entonces terminan. Else, ve al paso 3.

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 la percepción humana, debido a su "codicioso" naturaleza. 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 verificación es usar 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 que es mucho más largo que el recorrido óptimo. Para ser precisos, para cada constante r hay una instancia del problema del viajante de comercio tal que la duración del viaje calculada por el algoritmo del vecino más cercano es mayor que r veces el 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 único peor recorrido posible. (Si el algoritmo se aplica en cada vértice como vértice inicial, la mejor ruta encontrada 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 si existe.