Recorrido óptimo de exploración (TSP) #51
Description
Descripción
Cuando el jugador tiene que visitar varios puntos del mapa (refugios, zonas de recursos, etc.), necesitamos calcular el camino más corto que recorra todos los objetivos una única vez y vuelva al punto de origen. Esta tarea consiste en implementar una versión heurística del Travelling Salesman Problem (TSP) para recorridos óptimos.
Criterios de aceptación:
-
El grafo puede ser dirigido o no dirigido.
-
Se ingresan n destinos y se calcula una ruta de recorrido que minimice la distancia total recorrida.
-
El algoritmo puede ser exacto (para n < 10) o usar una heurística como nearest neighbor para mayor escala.