Magia matemática: resolución del problema del mago viajero [cerrado]

Cualquier mago que sepa que tiene poderes probablemente debería ser muy amigable con todos los que conoce. Nunca sabes a quién podrías haber insultado en el pasado, así que es aconsejable hacer las paces hasta que recuerdes más.

Después de ser amigable con todos los que conoces (al menos con los pocos que se acercan a ti) y, en general, tratar de ganar un buen karma, es posible que un mago de la naturaleza se te acerque. Él educadamente pregunta por qué sigues saltando 10 pies en el aire, porque está molestando a las ardillas listadas. Si no se preparan para el invierno, morirán de hambre.

Explicas tu deseo de un camino entre todos los pueblos al mago de la naturaleza. Empieza a garabatear un mapa y algunos números, pero tú niegas con la cabeza. Explicas que no sabes por qué, pero estás bastante seguro de que no puedes usar las matemáticas. Levanta una ceja y pregunta, "¿todo matemáticas?" Te encoges de hombros y mencionas que crees que probablemente sea una tarea lo suficientemente difícil como para permitir un enfoque matemático. Crees que estaría bien si hiciéramos un poco de trampa y usáramos el compás y la regla que tienes convenientemente a mano para cuadrar el círculo si ayudara como parte de la solución, pero eso es todo el engaño que puedes permitir. Por desgracia, has olvidado cómo cuadrar el círculo, por lo que puede que no sea tan útil como trampa.

¡El mago de la naturaleza aplaude y sonríe! "¡La naturaleza hace todo tipo de cosas asombrosas sin matemáticas!" exclama. Conjura un poco de magia y las hormigas brotan de varios hormigueros. ¡Él explica el problema a las hormigas y les da una misión para encontrar el camino más corto para ti!

Le agradeces al mago por sus esfuerzos y te dice que esperes unas horas a que las hormigas exploren la tierra y encuentren el mejor camino. Él deambula mientras reflexionas sobre cuántos intervalos de siete segundos te llevará mantener los pies fuera de este suelo infestado de hormigas durante unas horas.

Las hormigas son asombrosamente buenas para encontrar caminos en espacios euclidianos. De hecho, son tan buenos que a menudo emulamos su enfoque basado en feromonas en nuestros algoritmos de optimización; ¡funcionan así de bien!

Acabo de jugar con una cuerda y se me ocurrió esto. No tengo ni idea de lo bien que funciona en todos los casos. Parece funcionar bien para el caso de ejemplo que tuve. Si alguien sabe donde puedo encontrar más información sobre este tipo de cosas me encantaría escuchar en los comentarios.

Con eso fuera del camino con el espectáculo:

Usando un mapa (entra en la tienda de mapas local, el aldeano se escapa, toma el mapa) encuentra todos los pueblos que necesita visitar.

Coloque un imperdible, un lazo o un gancho en cada aldea. (Utilicé imperdibles ya que tenía algunos a mano)

Pase un trozo de cuerda a lo largo de los caminos o caminos entre cada pueblo. Ate cada extremo al pasador de seguridad / lazo / gancho.

Agregue una etiqueta a cada pin con el nombre del pueblo. La razón de esto quedará clara.

Tu mapa debería tener algo como esto encima:

Ahora toma el camino más largo. Sosténgalo de modo que los dos pasadores de seguridad en cada extremo estén nivelados.

Sacuda la malla, luego tome el lazo colgante más bajo, levántelo y sosténgalo de modo que las clavijas en ambos extremos estén niveladas con las clavijas del primer lazo.

Repite esta operación hasta que te quede el número mínimo de hilos.

Desengancha las cuerdas que sujetas por encima de la línea de la malla. Esto fue un poco complicado mantenerlos a todos desenredados.

Ahora deberías quedarte con una sola línea de imperdibles que unen cada ciudad.

Las desventajas de este método:
lleva bastante tiempo configurarlo.
Necesitas robar un mapa.
Es muy fácil terminar con la malla en un nudo completo.
No estoy convencido de que siempre le dará la respuesta correcta. (Pero parece cerca)

Debería usar una variación de un Algoritmo Genético . Esta es una técnica que imita los caminos evolutivos naturales para resolver problemas que de otro modo serían extremadamente difíciles.

Digamos que hay cuatro pueblos, cada uno con tres caminos de diferente longitud entre ellos.

La primera vez que el asistente elegirá al azar: AB1 -> BC2 -> CD3 -> DA1

La próxima vez que elija diferentes rutas: AB2 -> BD3 -> DC1 -> CA2

Y la tercera vez: AC3 -> CD2 -> DB3 -> BA1

Ahora saca todas sus notas, y cuánto tiempo le tomó tomar cada camino, y comienza a combinar y mezclar las mejores rutas. Descarta los que tardan demasiado y solo conserva y mezcla los patrones que fueron relativamente más rápidos. Luego comienza de nuevo desde el paso 1, pero con sus nuevos patrones mixtos, y repite todo esto varias veces.

Eventualmente, tendrá un conjunto de caminos muy buenos; no necesariamente serán óptimos, pero estarán cerca.

Un algoritmo simple que uso para un número relativamente pequeño de paradas es este:

1. Encuentre la distancia de cada pueblo a cada otro pueblo.
2. Tome el pueblo cuya distancia más corta a otro sea el más grande del grupo - designe esto como pueblo 1.
3. Seleccione su ruta más corta al siguiente pueblo - designe este pueblo 2.
4. Desde la ciudad 2, seleccione la ruta a la ciudad no visitada más cercana.
5. Repita el paso 4 según sea necesario

Esto no da la respuesta óptima , pero da una buena. Si el número de pueblos es menor (digamos <10), entonces a veces es obvio cómo acortar la ruta.

Resulta que mi enfoque de desarrollo propio es una variante del enfoque del árbol de expansión mínimo .