- Ruta
- Más corta encontrada
- Salida
| Método | Longitud | Sobre la más corta | Pasos |
|---|---|---|---|
| - | - | - | |
| - | - | - | |
| - | - | - | |
| - | - | - | |
| - | - | - |
Problema del viajante
Un viajante tiene que visitar cada ciudad una vez y volver a casa. ¿Qué orden hace el viaje más corto? La pregunta es fácil de plantear y, a medida que crece el número de ciudades, imposible de responder probando todos los órdenes: 30 ciudades ya permiten unas 4,4 × 10³⁰ rutas circulares. Reparte ciudades por un mapa o coloca las tuyas con un clic, y mira cómo reglas prácticas rápidas, mejoras ingeniosas y un método exacto construyen sus rutas paso a paso, y cuánto se acercan los rápidos. Elige cómo se distribuyen las ciudades y cuántas hay, elige un método y pulsa Resolver para ver cómo construye una ruta circular paso a paso, o Paso para avanzar de movimiento en movimiento. Haz clic en el mapa para añadir una ciudad o en una ciudad para quitarla. Comparar todos ejecuta cada método sobre las mismas ciudades y muestra cuánto se aleja cada uno de la ruta más corta encontrada. La ciudad roja es donde empieza el viaje.
Cómo funciona
- Elige una distribución y el número de ciudades, o haz clic en el mapa para colocar las tuyas y en una ciudad para quitarla.
- Elige un método y pulsa Resolver para verlo paso a paso, o Paso para avanzar de movimiento en movimiento.
- Pulsa Comparar todos para ejecutar cada método sobre las mismas ciudades y lee cuánto supera cada ruta a la más corta encontrada.
Por qué es difícil
Con n ciudades hay (n − 1)! / 2 rutas circulares distintas, porque da igual dónde empieces y en qué sentido recorras la ruta. Son 12 para 5 ciudades, 181.440 para 10 y unas 6 × 10¹⁶ para 20. No se conoce ningún método que encuentre el viaje más corto para cualquier mapa en un tiempo que crezca solo como una potencia de n: el problema es NP-difícil. El mejor método exacto de esta aplicación, la programación dinámica de Held–Karp de 1962, sigue necesitando unos n² · 2ⁿ pasos, así que aquí está limitado a 12 ciudades.
Buenas rutas, rápido
En la práctica, las rutas casi más cortas se encuentran rápido. El vecino más cercano va siempre a la ciudad no visitada más próxima y suele acabar alrededor de un 25 % por encima de la mejor ruta. La inserción más barata hace crecer un circuito y añade la ciudad que menos lo alarga. 2-opt toma cualquier ruta y va sustituyendo dos aristas por otras dos más cortas, lo que elimina todos los cruces y suele quedarse a un 5 % aproximadamente. El recocido simulado hace movimientos 2-opt aleatorios y, mientras sigue «caliente», acepta algunos que alargan la ruta, de modo que puede salir de callejones sin salida antes de asentarse.
Preguntas frecuentes
¿Hay una fórmula para la ruta más corta?
No. La ruta más corta depende de las posiciones exactas de todas las ciudades, y ningún método conocido la encuentra para cualquier mapa sin, en el peor caso, una cantidad de trabajo que crece exponencialmente. Para unos cientos o miles de ciudades, solucionadores exactos especializados como Concorde demuestran aun así rutas óptimas combinando la programación lineal con podas ingeniosas, y la mayor instancia resuelta de forma exacta hasta ahora tiene 85.900 puntos.
¿Por qué 2-opt elimina todos los cruces?
Si dos aristas de una ruta se cruzan, las cuatro ciudades que unen forman un cuadrilátero cuyas diagonales son esas dos aristas. Cambiarlas por dos lados opuestos del cuadrilátero siempre es más corto, por la desigualdad triangular, e invierte el tramo de ruta que queda entre ellas. 2-opt sigue haciendo esos intercambios hasta que ninguno ayuda, así que su ruta final nunca se cruza consigo misma.
¿Qué es la temperatura en el recocido simulado?
Controla lo dispuesto que está el método a aceptar un movimiento que alarga la ruta. Un movimiento que añade d a la longitud se acepta con probabilidad e^(−d/T). A una temperatura T alta casi todo vale, lo que permite a la ruta escapar de una disposición mala; a medida que T baja, el método se vuelve voraz y se asienta. El nombre viene de enfriar un metal lentamente para que sus átomos encuentren una disposición de baja energía.
¿Por qué el método exacto está limitado a 12 ciudades?
Held–Karp guarda el camino más corto para cada subconjunto de ciudades y cada posible última ciudad, es decir, unos n · 2ⁿ números, y calcula cada uno con n comparaciones. Para 12 ciudades son unos cientos de miles de pasos; para 25 ciudades serían miles de millones. Aun así es enormemente más rápido que probar las (n − 1)! / 2 rutas: para 12 ciudades serían casi 20 millones.
¿Se envía algo a un servidor?
No. Las ciudades y los cinco métodos se ejecutan en tu navegador. Las ciudades que colocas con un clic se quedan en el almacenamiento local de este navegador.
¿Listo para probarlo?
Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.
Ir al editor