El algoritmo del vecino más cercano es uno de los algoritmos heurísticos más simples para resolver el problema del viajante de comercio . Pertenece a la categoría de algoritmos "codiciosos" .
Formulado de la siguiente manera:
Los puntos de desvío del plan se incluyen secuencialmente en la ruta, y cada siguiente punto incluido debe ser el más cercano al último punto seleccionado entre todos los demás que aún no se incluyen en la ruta.
El algoritmo es fácil de implementar, rápido de ejecutar, pero, al igual que otros algoritmos "codiciosos", puede producir soluciones subóptimas. Uno de los criterios heurísticos para evaluar una solución es la regla: si la ruta recorrida en los últimos pasos del algoritmo es comparable a la ruta recorrida en los pasos iniciales, entonces la ruta encontrada puede considerarse condicionalmente aceptable; de lo contrario, soluciones más óptimas probablemente exista. Otra opción para evaluar la solución es usar el algoritmo de límite inferior .
Para cualquier número de ciudades mayor que tres, en el problema del vendedor ambulante, puede elegir tal arreglo de ciudades (el valor de las distancias entre los vértices del gráfico y la indicación del vértice inicial) que producirá el algoritmo del vecino más cercano la peor solución. [una]
Pasos del algoritmo:
A la salida tendremos una secuencia de vértices, una solución supuestamente óptima.