En la década de 1950-1960, hubo interesantes contribuciones a la solución del problema del viajero, en donde los científicos George Dantzig, Delbert Ray Fulkerson y Selmer M. Johnson de la Corporación RAND en Santa Mónica, quienes expresaron el problema como Programación Lineal en Enteros.
proceso.com.mx
CIUDAD DE MÉXICO (proceso.com.mx).–La tecnología ha dado, después de muchos años, una serie de facilidades que sin duda han permitido avanzar en el conocimiento. Píénsese en Internet y todas las posibilidades que ha traído. Esta red de redes es probablemente tan importante como la invención de la rueda. Y es que gracias al cómputo moderno las distancias se han acortado, el acceso a la información se está volviendo cada vez más universal y las aplicaciones de las diferentes computadoras, ya sean de escritorio o portátiles (como lo son los teléfonos celulares), son cada vez más poderosas.
Seguramente más de un lector recordará, por ejemplo, la Guía Roji, que era un mapa de la Ciudad de México y que consultábamos cuando teníamos que ir a algún sitio que no nos era familiar. Hoy Google Maps o Waze no sólo nos dicen dónde se encuentra el lugar al que queremos ir sino que además, nos da las indicaciones en tiempo real, vía voz computarizada, para llevarnos a nuestro destino.
Curiosamente, a pesar de todos estos avances, hay problemas no resueltos y que de por sí, se consideran muy difíciles de resolver, tan es así que tienen incluso un nombre en la literatura especializada: problema NP-duros. Uno de los más emblemáticos es el problema del viajero, el cual busca responder a la siguiente pregunta: dada una lista de ciudades y las distancias entre cada par de ellas, ¿cuál es la ruta más corta posible que visita cada ciudad exactamente una vez y al finalizar regresa a la ciudad origen?
Este problema, no resuelto, ha sido atacado por muchos años y se tienen algunas soluciones parciales. Es un problema de optimización combinatoria y es muy mencionado en las ciencias de la computación. Fue planteado en 1930 por primera vez y las soluciones actuales usan ciertas heurísticas, es decir, ciertas reglas que comúnmente funcionan, en muchos casos. Sin embargo, no hay una solución definitiva y se duda que exista ésta.
¿Por qué este problema es tan importante? Porque puede abstraerse a una serie de problemas no resueltos, por ejemplo, en la secuenciación del ADN, en el tema de la planificación e incluso en algunos problemas en la fabricación de los circuitos lógicos.
Se desconoce el origen del problema del viajero pero ya se menciona el tema en 1832, aunque no hay ningún tratamiento matemático a la problemática. Fue el matemático irlandés W. R. Hamilton y su colega británico Thomas Kirkman, quienes definieran, en el siglo 19, de manera formal este problema. Y todo parece indicar que fuese en 1930 donde se popularizó lo suficiente este problema, destacándose en su posible tratamiento a Karl Menger, quien mostrara los problemas de las heurísticas y la dificultad de atacar el problema por fuerza bruta.
En la década de 1950-1960, hubo interesantes contribuciones a la solución del problema del viajero, en donde los científicos George Dantzig, Delbert Ray Fulkerson y Selmer M. Johnson de la Corporación RAND en Santa Mónica, quienes expresaron el problema como Programación Lineal en Enteros y desarrollaron el método de Planos Cortantes como una solución factible. Con este nuevo método, resolvieron una instancia con 49 ciudades, óptimamente, mediante la construcción de un recorrido y probando que no había un recorrido que pudiera ser más corto. Aún así, el problema se resiste para ser solucionado para cualquier número N de ciudades.
Fue en 2006 cuando Cook y otros, obtuvieron un recorrido óptimo para 85 mil 900 ciudades (cifra increíble), dado por un problema de diseño de microchip, y este es el récord de ciudades en donde se soluciona este problema adecuadamente. Para otras muchas instancias con millones de ciudades, la solución puede ser encontrada garantizando que la solución contiene un 2-3% del recorrido óptimo.
¿Pero qué tiene que ver esto con hacerse millonario programando computadoras? Mucho. Si usted programa computadoras y logra un algoritmo que resuelva finalmente el problema del agente viajero, entonces podría venderlo por mucho dinero a las empresas de mensajería y paquetería, porque seguramente la solución que usted hubiese encontrado podría optimizar el envío de bienes en las ciudades, haciendo que estas empresas ahorraran mucho dinero. Desde luego que el problema es lo suficientemente complejo como para pensar que se puede obtener el resultado final rápidamente, pero ¿quién nos dice que no hay alguien de los lectores que tiene una feliz idea y lo resuelve definitivamente?
Cargando ...
