Glosario

Seleccione una de las palabras clave de la izquierda ...

Gráficos y RedesEl problema del vendedor ambulante

Tiempo de leer: ~20 min
Esta página ha sido traducida automáticamente y puede contener errores. ¡Póngase en contacto si desea ayudarnos a revisar las traducciones!

Pensemos, una vez más, en redes y mapas. Imagine que un servicio de entrega tiene que visitar ${tsn} diferentes ciudades para distribuir parcelas. Podemos pensar en estas ciudades como los vértices en un gráfico. Si todas las ciudades están conectadas por carreteras, este es un , entonces hay ${tsn} × ( ${tsn} - 1)2 = ${tsn*(tsn-1)/2} bordes en total.

El camión de reparto tiene que visitar todas las ciudades, en cualquier orden. En el problema de los puentes de Königsberg, queríamos encontrar caminos que recorrieran exactamente cada borde . Ahora queremos encontrar caminos que visiten cada vértice exactamente una vez. Estos caminos se llaman ciclos hamiltonianos .

Existen innumerables posibilidades diferentes para los ciclos hamiltonianos en gráficos completos. De hecho, podemos elegir cualquier vértice como vértice inicial y luego elegir cualquiera de las ciudades restantes en cualquier orden:

Diagram coming soon…

Diagram Coming Soon…

En un gráfico con ${tsn1} ciudades, cada ciclo de Hamilton también debe contener ${tsn1} ciudades Ahora,

    Esto significa que, en total, hay ${tsnPaths(tsn1)} posibles caminos. Una abreviatura de este producto es ${tsn1} ! o ${tsn1} Factorial

    Podrías imaginar que tal vez no sea posible viajar directamente entre dos ciudades, sin pasar por otra ciudad. En ese caso, ya no tenemos un gráfico completo, y encontrar el número de ciclos hamiltonianos, si es que existen, se vuelve mucho más difícil.

    Hasta ahora hemos ignorado el hecho de que algunas ciudades podrían estar más separadas que otras. Sin embargo, en la vida real, esta es una consideración muy importante: no solo queremos encontrar un camino, sino que queremos encontrar el más corto. Esto se llama el problema del vendedor ambulante . Tiene que resolverse no solo en el transporte y la logística, sino también al colocar transistores en microchips, para hacer computadoras más rápidas o al analizar la estructura del ADN .

    Un método simple sería probar todos los caminos posibles, encontrar la longitud de cada uno y luego elegir el más corto. Sin embargo, acabamos de demostrar eso, incluso con solo ${tsn2} ciudades hay ${tsn2} ! = ${factorial(tsn2)} posibles caminos. Una vez que tenga cientos o miles de vértices, probar todos los caminos posibles se vuelve imposible, incluso utilizando computadoras potentes.

    Desafortunadamente, no existe un algoritmo más eficiente para resolver el problema del vendedor ambulante. En cambio, los matemáticos y los informáticos han desarrollado varios algoritmos que encuentran buenas soluciones, incluso si no son la mejor. Estos algoritmos, que solo dan soluciones aproximadas, se denominan heurísticas .

    Intente reorganizar las ciudades en este mapa y observe cómo cambia el camino más corto entre ellas. Puede eliminar ciudades al tocarlas, y puede agregar ciudades haciendo clic en cualquier parte del mapa (hasta 8):

    El algoritmo codicioso (o algoritmo vecino más cercano) es muy simple: comienzas en una ciudad aleatoria y te mueves consecutivamente a la ciudad más cercana que no has visitado antes. Una vez que haya visitado todas las ciudades, se detiene.

    Animación próximamente ...

    Puede mostrar que, en promedio, las rutas encontradas utilizando el algoritmo codicioso son un 25% más largas que la ruta más corta posible.

    El algoritmo 2-Opt comienza con una ruta aleatoria posible. Luego, elige repetidamente dos bordes y los intercambia si eso reduciría la longitud del camino. Te detienes cuando no puedes reducir más la longitud intercambiando cualquier par de bordes.

    Animación próximamente ...

    Resulta que, mucho antes de que existieran las computadoras, la naturaleza había encontrado una manera inteligente de encontrar caminos óptimos entre diferentes lugares: en colonias de hormigas.

    Las hormigas quieren encontrar las rutas más cortas posibles entre su nido y las posibles fuentes de alimento. Pueden comunicarse entre sí a través de sustancias químicas que dejan a lo largo de su rastro y que otras hormigas pueden seguir.

    • La colonia de hormigas envía muchos exploradores que inicialmente viajan en direcciones aleatorias. Una vez que encuentran comida, regresan, dejando un rastro de feromona. * Otras hormigas tienden a seguir un rastro cuando encuentran uno, lo que los lleva a la comida. En su viaje de regreso depositan más feromona, lo que refuerza el camino. * Con el tiempo, la feromona se evapora. Cuanto más largo es un camino, más tiempo le toma a las hormigas recorrerlo, por lo que la feromona tiene más tiempo para evaporarse. Los caminos cortos, por otro lado, pueden reforzarse más rápidamente, por lo que su fuerza aumenta más rápido.

    Diagrama próximamente ...

    Los algoritmos del Sistema de colonia de hormigas (ACS) intentan replicar este comportamiento en las computadoras, utilizando muchas hormigas "virtuales". Pueden encontrar rápidamente muy buenas soluciones para el problema del vendedor ambulante.

    Una propiedad particularmente útil de los algoritmos ACS es que pueden ejecutarse continuamente y adaptarse en tiempo real a los cambios en el gráfico. Estos cambios podrían ser causados por accidentes automovilísticos y cierres de carreteras en redes de calles, o por picos de tráfico a servidores web en redes de computadoras.

    El problema del vendedor ambulante es NP-hard , lo que significa que es muy difícil de resolver con computadoras (al menos para un gran número de ciudades).

    Encontrar un algoritmo rápido y exacto tendría serias implicaciones en el campo de la informática: significaría que existen algoritmos rápidos para todos los problemas NP-difíciles. También haría inútil la mayor parte de la seguridad de Internet, lo que se basa en el hecho de que se cree que ciertos problemas son muy difíciles para las computadoras.

    Encontrar un algoritmo rápido para resolver el problema del vendedor ambulante también resolvería uno de los problemas abiertos más famosos en matemáticas e informática, el problema P vs NP . Es uno de los siete problemas del Premio del Milenio , cada uno con un premio de $ 1 millón.