El problema del viajante es un clásico de las matemáticas y la teoría de la computación: consiste en encontrar la ruta óptima para visitar varias ciudades, recorriendo la menor distancia posible, sin repetir el paso por ninguna de ellas.
El problema del viajante, versión chunga de 1.000 puntos
(Universidad de Princeton)
Es de esas rarezas matemáticas que a veces aparecen como por sorpresa: se sabe cómo resolverlo, pero en la práctica no se puede llevar a cabo muchas veces si en la ruta hay demasiados puntos: el tiempo de cálculo necesario sería inmenso. Es lo que se conoce como un problema NP-completo.
El vídeo muestra un ejemplo de un jugador humano intentando resolver el problema en la práctica, con un escenario en el que hay que desplazar una nave parecida a la de Asteroides pasando por todos los puntos rojos. Forma parte de The Physical Travelling Salesman Problem Competition, un concurso organizado por la Universidad de Essex. En esta variante del clásico, los escenarios están simplificados –en cuanto a número de puntos– pero hay más factores que controlar, como los giros y la aceleración de la nave.
Lo más interesante es que al concurso pueden presentarse tanto humanos como bots –software especializado– que compiten en tiempo real para lograr el objetivo en el menor tiempo posible. Eso implica, por un lado, resolver el problema de forma óptima y procurar que se pueda llevar a cabo con los movimientos y ajustes de la simulación física de la nave, algo que puede tener interesantes aplicaciones en inteligencia artificial y robótica.
En el concurso hay clasificaciones separadas para humanos y para bots, pero también para humanos contra bots. Aunque hay software muy bien diseñado que supera a los jugadores de carne y hueso, de momento un austríaco apodado Slash encabeza la lista. ¡Todavía hay esperanza!
