Interesante

Algoritmos, optimización y el problema del vendedor ambulante

Algoritmos, optimización y el problema del vendedor ambulante

Este es el quinto artículo de una serie de siete partes sobre algoritmos y computación, que explora cómo usamos números binarios simples para impulsar nuestro mundo. El primer artículo, Cómo funcionan los algoritmos en el mundo en el que vivimos, se puede encontrar aquí.

El trabajo esencial de un informático teórico es encontrar algoritmos eficientes para problemas y el más difícil de estos problemas no es solo académico; están en el centro de algunos de los escenarios del mundo real más desafiantes que se desarrollan todos los días. El más crítico de ellos es el problema de la optimización: ¿cómo encontramos el mejor solución a un problema cuando tenemos un número aparentemente infinito de posibles soluciones?

RELACIONADO: EL NUEVO ALGORITMO PERMITE A LOS AUTÓNOMOS CAMBIAR DE CARRIL MÁS COMO HUMANOS

Por ahora, lo mejor que podemos hacer es adoptar un enfoque heurístico y encontrar unasuficientemente bueno solución, pero estamos creando un nivel incalculable de ineficiencias que se acumulan con el tiempo y agotan nuestros recursos finitos que podrían utilizarse mejor en otros lugares. A esto lo llamamos el Problema del vendedor ambulante y no es un eufemismo decir que la solución a este problema podría ahorrarle a nuestra economía billones de dólares.

El problema del vendedor ambulante, la complejidad del tiempo exponencial y más

El problema del vendedor ambulante se describe así: una empresa requiere que uno de sus vendedores ambulantes visite cada ciudad en una lista de norte ciudades, donde se conocen las distancias entre una ciudad y todas las demás ciudades de la lista. Cada ciudad solo se puede visitar una vez y el vendedor termina en la ciudad de la que partió. ¿Cuál es el camino más corto que puede tomar para lograr esto?

El algoritmo más eficiente que conocemos para este problema se ejecuta en tiempo exponencial, que es bastante brutal como hemos visto. Sin embargo, a diferencia del cifrado RSA, en el caso del problema del vendedor ambulante no hay aritmética modular o convertir la factorización en un período de búsqueda, como lo hace el algoritmo de Shor. El problema del vendedor ambulante es un problema de decisión, y no conocemos atajos que nos ayuden complejidad de tiempo exponencial.

Solo para reforzar por qué esta es una situación terrible, usemos un ejemplo muy común de cuán loco complejidad de tiempo exponencial puede conseguir. Digamos que puedes doblar una hoja de papel una y otra vez tantas veces como quieras y eso siempre tendrá la longitud necesaria para hacer el doblez. Tomando una medida del ancho de la pila de "hojas" en el producto final donde el papel doblado está creciendo en longitud lejos de nosotros, esto es lo que puede esperar:

* 0 pliegues: 1/250 de pulgada de espesor.
* 10 pliegues: ~ 2.05 pulgadas de espesor.
* 25 pliegues: ~ 1 milla de espesor.
* 43 pliegues: La superficie de la luna.
* 52 pliegues: Dentro del sol.
* 57 pliegues: Pasando Ultima Thule
* 67 pliegues: La luz tarda 1,5 años en viajar de un extremo al otro.
* 82 pliegues: Tan ancho como la Vía Láctea.
* 93 pliegues: A una distancia de proyección astronómica del agujero negro supermasivo en el centro de Messier 87.
* 101 pliegues: No estoy seguro de qué hay ahí porque está más allá del universo observable.

Y eso es con el mejor algoritmo que tenemos ahora. Cada una de esas "hojas" en esa pila es una ruta que el vendedor podría tomar cuya longitud al final tendríamos que comparar y medir con todas las otras longitudes de ruta y cada pliegue equivale a agregar una ciudad adicional a la lista de ciudades que necesita visitar. Si cometimos un error al intentar resolver el problema del vendedor ambulante comprobando todas las soluciones posibles para encontrar la mejor, estamos viendo complejidad del tiempo factorial. Usando nuestro 128 bits número de nuestro ejemplo de cifrado RSA, que era 2128, mientras que 101 pliegues son solo 2101, 35! golpes pasados ​​2128 por al menos un factor de 100. Simplemente empeora con cada incremento adicional en su entrada, y esto es lo que hace que el problema del vendedor ambulante sea tan importante y también tan desesperante.

El problema de los algoritmos de optimización

No sabemos cómo encontrar la respuesta correcta al problema del vendedor ambulante porque para encontrar la mejor respuesta necesita una forma de descartar todas las otras respuestas y no tenemos idea de cómo hacerlo sin verificar todas las posibilidades o mantener un registro de la ruta más corta encontrada hasta ahora y comenzar de nuevo una vez que nuestra ruta actual exceda ese número. Eso es lo mejor que tenemos, y eso solo reduce las cosas complejidad de tiempo exponencial, así que como solución, no es una gran solución en absoluto.

El problema del vendedor ambulante es especial por muchas razones, pero la más importante es porque es un problema de optimización y los problemas de optimización surgen en todas partes en la vida diaria. En lo que respecta a los tamaños de entrada, 101 no es muy grande en absoluto. En el mundo real, hay muchos pueblos o ciudades pequeñas en un solo estado de EE. UU. Que, en teoría, podrían ser parte del área de entrega de un gran distribuidor comercial. Descubrir la ruta más corta entre todas las paradas que sus camiones necesitan para hacer a varios clientes en el día a día ahorraría una cantidad incalculable de dinero en mano de obra y costos de combustible.

Si compra piezas del extranjero para su fábrica, ¿qué ruta y combinación de métodos de entrega le costará la menor cantidad de dinero? ¿Qué configuración de pliegues de proteínas es la que puede vencer al cáncer? Encontrar un algoritmo que pueda resolver el problema del vendedor ambulante en algo cercano a tiempo polinomial cambiaría todo y lo haría de la noche a la mañana.

Sin embargo, parte del problema es que debido a la naturaleza del problema en sí, ni siquiera sabemos si una solución en tiempo polinomial es matemáticamente posible. Esto se debe a la forma en que clasificamos los problemas y el problema del viajante pertenece a una clasificación muy especial en ese sistema, una que plantea uno de los mayores desafíos en matemáticas e informática, con implicaciones de gran alcance para el mundo real.

El sexto artículo de nuestra serie sobre algoritmos y computación, P vs. NP, NP-Complete y el algoritmo para todo, se puede encontrar aquí.


Ver el vídeo: Simple Traveling Salesman Algorithm Python (Enero 2022).