Más

Métodos para resolver este simple problema de enrutamiento

Métodos para resolver este simple problema de enrutamiento


En mi clase de geografía del transporte, se nos pidió que hiciéramos una "mejor estimación" en la ruta que hace lo siguiente en este gráfico:

  1. Empieza en A
  2. Visita cada nodo
  3. Vuelve a A
  4. minimiza la distancia.

Escribí un programa que calculó todas las rutas de cinco pasos que comenzaron desde A, visité cada nodo y regresé a A. Luego calculé el costo de estas rutas.

¿Cómo resolverían esto otras personas?

Mi maestro nos dio una "pista" de que deberíamos leer sobre el algoritmo de Dijkstra, pero no pude ver cómo aplicar eso para resolver este problema en particular. Mi solución se desmoronaría bastante rápido a medida que aumentara la cantidad de pasos o nodos.


Les aconsejo que busquen, investiguen, el problema del viajante para algunas opciones.

Aquí hay un enlace a una forma de formular una solución. En resumen, este es un tema difícil de entender / comprender:

Soluciones TSP


En mi humilde opinión, "Dijkstra" no es una buena pista. Lo que está viendo es el llamado "problema del vendedor ambulante".

Dada una lista de ciudades y sus distancias por pares, la tarea es encontrar un recorrido lo más corto posible que visite cada ciudad exactamente una vez.

Dado que un enfoque de fuerza bruta funciona con O (n!), Alcanzan su límite bastante rápido (WP dice que 20 nodos ya es el límite).