EL NÚMERO OCULTO DEL VIAJANTE, ACORRALADO
Uso de IA declarado. En una «Declaración de uso de IA», los autores indican que usaron la herramienta de IA GPT-5.6 Sol Pro para preparar el artículo, que revisaron y verificaron todos los resultados y que asumen toda la responsabilidad de su contenido. Su código está disponible bajo petición.
El problema del viajante pide el recorrido más corto que visita una vez cada punto de un conjunto y vuelve al inicio. Ahora, hagamos que los puntos sean aleatorios: se lanzan n puntos de manera uniforme en un cuadrado de lado 1 y se pregunta cuánto mide el recorrido más corto.
En 1959, Beardwood, Halton y Hammersley demostraron una respuesta sorprendente. A medida que n crece, la longitud del mejor recorrido pasa a ser casi con seguridad igual a β√n, donde β es una constante universal, la misma para cualquier dispersión aleatoria. También mostraron que 0,625 ≤ β ≤ 0,9212.
Más de sesenta y cinco años después, nadie conoce β. No hay fórmula. Grandes experimentos por ordenador la sitúan en torno a 0,7124, pero un experimento no es una demostración. Hasta ahora, las mejores cotas demostradas eran 0,6277 ≤ β ≤ 0,90367. Estas constantes importan en logística, donde se usan para estimar la longitud de las rutas de reparto sin calcularlas, y por eso el nuevo resultado procede de la McCombs School of Business de la Universidad de Texas en Austin, firmado por Zhuolun Dong y Junyu Cao.
La nueva horquilla
El artículo demuestra:
0,6421 ≤ β ≤ 0,8810
y, mediante muestreo aleatorio, muestra que 0,6536 ≤ β ≤ 0,8749 con una probabilidad de al menos 1 − 2 × 10⁻⁴. Esa probabilidad se refiere al azar del muestreo por ordenador, no a β en sí, que es un número fijo.
Por abajo: cortar las aristas largas
Para demostrar que todo recorrido debe ser largo, los autores observan qué ocurre si se eliminan todas las aristas de un recorrido más largas que cierta longitud r. El recorrido se rompe en trozos de camino, y cada trozo permanece dentro de un grupo de puntos situados a menos de r unos de otros. Cuantos más caminos necesita un grupo para quedar cubierto, más aristas largas tenía que tener el recorrido. Sumando esto para todos los valores posibles de r se obtiene la longitud del recorrido:
ℓ(H) = ∫₀^∞ N_H(r) dr,
donde N_H(r) cuenta las aristas más largas que r.
Los puntos aislados y los extremos de los caminos dan el antiguo término 5/8 = 0,625, exactamente la cota de 1959. El nuevo ingrediente es una serie de correcciones procedentes de pequeños grupos de 3, 4 y 5 puntos, cada una de ellas una integral sobre las posiciones posibles de los puntos. Estas integrales no pueden calcularse con exactitud, así que los autores dividen sus dominios en cubos diminutos y acotan cada cubo por abajo, redondeando cada número irracional en la dirección desfavorable para que el resultado sea una cota auténtica:
β ≥ 0,625 + 0,01113528859 + 0,005040573276 + 0,001015487669 > 0,6421.
Por arriba: zigzag en bloques de cinco
Una cota superior solo necesita un buen recorrido. La receta clásica corta el cuadrado en franjas horizontales y las barre en zigzag, de izquierda a derecha y luego de derecha a izquierda. La novedad: dentro de cada franja, los puntos se toman en bloques de cinco, y cada bloque se visita en el mejor de sus 24 órdenes posibles.
La longitud esperada de un bloque es una integral de once dimensiones: cinco separaciones horizontales entre puntos y seis alturas. Los autores la acotan numéricamente sobre una rejilla fina, de nuevo con números racionales redondeados en la dirección segura, y obtienen β < 0,8810.
La distancia que queda
La horquilla se ha estrechado de una anchura de unos 0,28 a unos 0,24, pero el valor empírico de 0,7124 sigue estando muy dentro de ella. Rejillas más finas, estimaciones más precisas de las áreas de discos superpuestos y bloques más largos podrían ajustarla aún más. Cerrar la distancia que queda, escriben los autores, «puede requerir técnicas nuevas».