Un problema de optimización es aquel en el cual se necesita elegir en algún sentido la mejor decisión posible de todas las que se encuentran disponibles. Hay situaciones en las cuales la mejor decisión posible es fácil de encontrar, principalmente debido a que las opciones disponibles son pocas. Invito al lector a que piense en un problema de su vida que haya solucionado con facilidad, y seguramente en su memoria encontrará varios ejemplos. Sin embargo, existen muchos otros problemas en el mundo real en donde la cantidad de decisiones posibles a tomar son casi infinitas, y con esto nos referimos a que son tantas que analizarlas una por una sería una tarea ardua que a una persona normal le tomaría muchos años, y quizás no le alcanzaría la vida entera para llevarla a cabo. Pero por fortuna el ser humano ha ideado un aparato capaz de facilitarle esa tan tediosa tarea: la computadora. Es ahí donde la computación entra en juego para hacer de los problemas de optimización una de sus tantas ramas de investigación y aplicaciones.

Vayamos a un ejemplo: supongamos que eres una de esas personas que te encanta viajar por el mundo, y quieres recorrer todas las ciudades de un país X determinado, por mencionar uno en particular, Francia. Imagina que además, tienes 30 días de tiempo para recorrerlo, y un presupuesto limitado para tus gastos durante ese viaje. Por lo tanto, en ese caso te has planteado la posibilidad de rentar un auto, y visitar todas las ciudades de Francia (pongamos como ejemplo, las 20 ciudades más importantes) una vez sola, sin pasar dos veces por la misma ciudad en ningún momento de ese recorrido, y gastando la menor cantidad posible de presupuesto (dado que no cuentas con todo el dinero del mundo para alcanzar ese objetivo).

Analicemos la situación. Imagina que ya tienes las 20 ciudades francesas que quieres recorrer, marcadas en tu mapa. ¿ Por cuál de ellas comenzamos el recorrido ? Supongamos que empezamos en la capital, París. En ese caso, debemos visitar todas las ciudades, sin pasar dos veces por la misma, y al finalizar el recorrido volver a París (1). La dificultad de esto reside en que hay muchísimas maneras de llevar a cabo ese recorrido, y para cada una de las opciones posibles, tendríamos que estudiar cuánto nos costaría en combustible, para quedarnos con la opción más barata de todas ellas. Claramente estamos frente a un problema de optimización. ¿ Cuántos caminos posibles tenemos exactamente ? ¿ Podemos contarlos todos de alguna manera ? Para eso vamos a tener que recurrir un poco a las matemáticas.

Cada camino posible es un ordenamiento de las 20 ciudades, es decir, si todas las ciudades estuvieran numeradas del 1 al 20, una opción posible sería recorrerlas en el orden numérico en el que fueron elegidas (primero visito la ciudad 1, luego voy a la 2, después a la 3, etcétera). Pero esa no es la única opción posible. Podría ir de la 1 a la 3, y de la 3 a la número 20, y desde ahí visitar la número 8, y así sucesivamente hasta quedarme sin ciudades por visitar y retornar a la ciudad número 1 desde la cual comencé el viaje. Un camino posible para este viaje es lo que en matemáticas se conoce con el nombre de permutación. Una permutación es en este caso, un ordenamiento posible de los números del 1 al 20, sin repetir ninguno (a excepción de la ciudad origen a la cual se retorna al final). Según nos dicen las matemáticas, la cantidad de permutaciones (o caminos) posibles para 20 ciudades es igual a 20! (factorial de 20) (2), que equivale a 2,43 x 1018 caminos posibles. En pocas palabras, es un 2 con 18 ceros a la derecha, lo cual representa un número gigantesco de posibilidades. Si estás organizando tus vacaciones, no sería muy sano tener que analizar uno por uno todos esos miles de millones de itinerarios de viaje posibles, simplemente morirás de viejo al intentarlo.

Este problema en el mundo informático se conoce con el nombre de Problema del viajante de comercio (en inglés, Travelling Salesman Problem o TSP). Es un problema de optimización combinatoria muy interesante en este ámbito, ya que se lo considera muy difícil de resolver, incluso para una computadora. Esto se debe precisamente a la infinidad de itinerarios viables que se tienen para recorrer un número N de ciudades, cantidad que crece en forma disparatada a medida que la cantidad de ciudades a visitar aumenta. Recién vimos que en el caso de 20 ciudades, el número de recorridos posibles es astronómico. Es tan enorme que a una computadora le podría tomar días o meses el encontrar el mejor camino posible.

Las aplicaciones reales que tiene el Problema del viajante de comercio son muchas, a pesar de que en este artículo hemos mencionado solamente una (el caso particular de un turista que desea dar la vuelta por Francia gastando la menor cantidad posible de combustible). Sin embargo, podríamos pensar que las ciudades a recorrer son solamente contenedores de basura, y que el turista es un camión recolector, que debe pasar por todos los contenedores de basura para vaciarlos todos, procurando economizar el combustible consumido. O podríamos pensar que los contenedores son direcciones de diferentes hogares, y el camión de la basura es en realidad la camioneta con la cuál se deben repartir los paquetes de correo a los diferentes hogares, los cuáles serán visitados una sola vez en el trayecto por parte del cartero. Aún cambiando los ejemplos, el problema de optimización subyacente es siempre el mismo. Todos estos ejemplos son como familias que pertenecen al mismo problema. Se trata de encontrar una ruta óptima que conecte una cantidad de puntos o lugares determinados, sin pasar más de una vez por el mismo lugar, y minimizando la distancia recorrida en total.

Para muchos esto puede parecer muy obvio, pero ¿ Quién diría que un turista, un cartero, y un recolector de basura estarían resolviendo en el fondo el mismo problema ?

 

Notas al márgen


(1) – A lo largo del artículo se insiste mucho en la idea de “volver a la ciudad desde la cual se inició el viaje”. Bien podría no retornarse a esa ciudad, y finalizar el viaje en la última ciudad visitada de todas. Sin embargo, vamos a suponer durante todo el post que al final del recorrido hay que volver a la ciudad de inicio sí o sí. Al fin y al cabo, son sólo suposiciones, y el viaje es ficticio 🙂

(2) – El factorial es una función matemática. Para quienes no recuerdan, o no conocen lo que es el factorial de un número entero, pueden consultar en la web. Lo importante es quedarnos con la idea de que el factorial de 20 en este caso no es más que la cantidad de formas posibles de ordenar los números del 1 al 20.

Espero que haya sido de tu agrado este post, y que los diferentes ejemplos e ideas expresadas en el mismo se hayan entendido. Por cualquier duda, consulta, aporte o crítica, puedes dejar un comentario al final de la página.

Suscríbete al Newsletter de Carbasoft:

 

Si te gustó esta entrada del blog, puedes darle a Compartir a esta página de Carbasoft en Facebook: