Algoritmo del vecino más cercano
estos son los pasos del algoritmo:
- inicializar todos los vértices como no visitados.
- seleccione un vértice arbitrario, establézcalo como el vértice actual u. marque u como visitado.
- encuentre el borde más corto que conecta el vértice u actual y un vértice V no visitado.
- establezca v como el vértice u actual.marque v como visitado.
- si se visitan todos los vértices del dominio, entonces termina. De lo contrario, vaya 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 perder rutas más cortas que se notan fácilmente con la visió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 mayores, entonces es probable que existan tours 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 resulta en 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 vendedor ambulante tal que la longitud del recorrido calculado por el algoritmo vecino más cercano es mayor que r veces La longitud 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 vecina más cercana produce el peor tour posible único., (Si el algoritmo se aplica en cada vértice como el vértice inicial, el mejor camino encontrado será mejor que al menos N / 2-1 otros tours, donde N es el número de vértices.)
el algoritmo vecino más cercano puede no encontrar un recorrido factible en absoluto, incluso cuando existe uno.