No suelo ver mucho la tele, pero el otro día un anuncio me llamó la atención. Aparece un grupo de amigos en un coche (el cual se pretende anunciar), uno de ellos luciendo una escayola en el brazo. El grupo llega a la conclusión de que la fractura es culpa del karma, por la mala vida que llevaba el muchacho, en especial en lo relativo a las mujeres. Por lo tanto, debería compensar sus malas acciones visitando a todas las mujeres a las que ha hecho daño para pedirles perdón. El conductor muestra en la pantalla del coche una lista (bastante extensa) de afectadas. El de la escayola pregunta si tendrán suficiente gasolina para verlas a todas, a lo que el conductor responde, sin pensárselo ni un momento, con un sí muy rotundo. ¡Ese tío es un crack! - me refiero al conductor, no al de la escayola-.
Asumamos que el conductor conoce perfectamente cuál es el consumo de su coche. Entonces solo necesita saber la longitud de la ruta a seguir. Por supuesto, la ruta debe visitar a todas las víctimas de nuestro ligón, y como el conductor es un tipo listo, utilizará el trayecto más corto posible. A pesar de la facilidad para el cálculo de nuestro protagonista, este problema es bastante complicado y bastante interesante. Lo llamaremos el problema del ligón (aunque los matemáticos y los expertos en computación le dan un nombre más aburrido, el problema del viajante).
El problema del ligón consiste en diseñar la ruta por carretera que pase por las casas de todas las chicas a las que tiene que pedir perdón recorriendo la menor distancia posible.
Podemos probar a resolverlo por fuerza bruta. Si solo hay dos chicas, hay dos posibles rutas (con la misma longitud), AB y BA. Con tres chicas tenemos seis rutas: ABC, ACB, BAC, BCA, CAB y CBA. En general, si hay que visitar a \(N\) chicas, el número de trayectos cuya longitud hay que calcular es \(N!\). El factorial es una función que crece MUY MUY rápido. Con tan solo 15 chicas (un número muy razonable para nuestro ligón), hay más de un billón (español, es decir, 1012) rutas, por lo que calcular su longitud es un verdadero suplicio, incluso usando un ordenador.
Afortunadamente, hay algoritmos que permiten resolver el problema del ligón de manera más eficiente que usar la simple fuerza bruta. Actualmente, no se conoce ningún algoritmo que requiera menos de \(2^N\) operaciones. Es un gran avance, con 15 chicas solo hay que calcular 33000 rutas, que no es demasiado. Pero aun así, al aumentar el número de chicas tendremos problemas (computacionales, me refiero; los personales ya se dan por supuestos), ya que el número de trayectorias aumenta exponencialmente.
Los problemas que se considera que se pueden resolver de forma eficiente son aquéllos que requieren, como máximo, un número polinomial de operaciones \(N^k\). Este tipo de problemas se denomina \(P\). Los problemas interesantes son aquéllos en los que se puede comprobar una solución con un número polinómico de operaciones, los problemas \(NP\). Nuestro problema del ligón es un problema \(NP\), de hecho es un problema \(NP-\text{completo}\), lo que significa que cualquier problema \(NP\) se puede convertir en el problema del ligón.
Antes he dicho que no se conoce ningún algoritmo polinomial para el problema del ligón. Pero la pregunta realmente interesante es: ¿es posible que exista una solución con un número de operaciones polinómico? Date cuenta que eso significaría que las clases de problemas \(P\) y \(NP\) son iguales. Y la respuesta es que no lo sabemos. De hecho, el instituto Clay de Matemáticas lo considera uno de los problemas del milenio, y ofrece un millón de dólares a quien sea capaz de ofrecer una demostración.
Nota para tiquismiquis: Por supuesto, el conductor siempre podría contentarse con encontrar una ruta sub-óptima compatible con su depósito de gasolina. En ese caso sí que se pueden encontrar algoritmos aproximados que operan en un número de operaciones decente, y además los humanos somos bastante buenos a la hora de encontrar soluciones aproximadas. Pero eso no hubiera dado juego para una entrada ;)
No hay comentarios:
Publicar un comentario