English
عربى
中文
Deutsch
Español
Français
हिन्दी
Hrvatski
Italiano
日本語
Português
Română
Русский
Svenska
Türkçe
Tiếng ViệtGráficos y RedesEl problema del vendedor ambulante
Pensemos, una vez más, en redes y mapas. Imagine que un servicio de entrega tiene que visitar
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
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
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
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
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