nova blog

Prof. Dr. Alex Rodríguez Villalobos

NP-completo

Santa Claus lo tiene crudo

Alex

Si alguna vez os habéis preguntado cómo se lo monta Santa Claus (papá Noel para los españoles) para poder repartir los regalos a todos los niños/as la noche de Navidad, aquí teneis algunas pistas: Dejando de lado cómo visitar todas las chimeneas de una misma ciudad, y también dejando de lado su capacidad de carga; Santa Claus debe visitar en una noche todas las ciudades del planeta (supongamos que al menos hay un niño bueno y que cree en Santa Claus en cada ciudad). Eso supone visitar al menos una vez cada ciudad partiendo de su querido hogar (allá por […]

El mayor problema del mundo

Alex

En la web de Princeton sobre el Problema de Viajante de Comercio, se reta a la comunidad científica a resolver el mayor problema TSP conocido hasta la fecha con 1.904.711 ciudades de todo el mundo. El mejor resultado (a fecha de esta noticia) ha sido encontrado por Keld Helsgaun usando una variante de su algoritmo heurístico LKH. Su resultado de longitud total 7,516,353,779 fue encontrado el 23 de diciembre de 2003. Anteriormente, los mejores resultados encontrados fueron el de Helsgaun (16 Sept. 2003) con un valor de 7,517,285,610 y el de Hung Dinh Nguyen, Ikuo Yoshihara, Kunihito Yamamori, and Moritoshi […]