El Sr. Lego no paraba de agitarse inquieto en su asiento, como esperando algo. Así llevaba ya un buen rato cuando me decidí a preguntarle si tenía algún problema o podía ayudarlo en alguna cosa.
Nada, nada -me respondío inquieto- cosas mías.
Con esas traté de meterme de nuevo en el código en el que estaba trabajando, pero los movimientos casi espasmódicos del Sr. Lego empezaban a ponerme nervioso. ¿Seguro que no le pasa nada Sr. Lego?
Al hacerle la pregunta volvió su cara y pude ver una mirada suplicante: Es que... esto no termina...
Me levanté y vi como estaba ejecutando un programa. Por lo menos llevaba una hora en ejecución.
Es que estoy tratando de resolver un problema para ganar un concurso que he encontrado en esta página.
El concurso consistía en encontrar la solución al conocido problema TSP (Traveling Salesman Problem). El problema consiste en una serie de ciudades que un viajante de comercio tiene que recorrer. El recurrido tiene que cumplir tres requisitos, que el número de kilómetros recorridos sea el mínimo posible, que el viajante no pase dos veces por la misma ciudad y que el viajante regrese a la ciudad de inicio.
¿Cómo está tratando de resolverlo Sr. Lego? -pregunté.
Estoy tratando de hacer una búsqueda en el espacio de estado del problema con las técnicas de búsqueda de las que hablamos hace algún tiempo.
Verá Sr. Lego, no creo que aquellas técnicas de búsqueda le sean muy útiles en este problema concreto, que pertenece a una clase de problemas que en Ciencias de la Computación se denomina "intratable", o más técnicamente, NP-Dificil.
NP-¿qué? -se extrañó el Sr. Lego.
Verá, hay problemas que son tan complejos que son computacionalmente irresolubles. Por mucho tiempo que dejara su ordenador funcionando jamás encontraría la respuesta, o en el mejor de los casos, tardaría miles o millones de años. Recuerde que ya lo comentamos el día que hablamos de la búsqueda en árboles.
