O NÚMERO OCULTO DO CAIXEIRO-VIAJANTE, ENCURRALADO

Uso de IA declarado. Numa “Declaração de uso de IA”, os autores afirmam que usaram a ferramenta de IA GPT-5.6 Sol Pro na preparação do artigo, que revisaram e verificaram todos os resultados e que assumem total responsabilidade por seu conteúdo. Seu código está disponível mediante solicitação.

O problema do caixeiro-viajante pede o percurso mais curto que visita cada ponto de um conjunto uma única vez e volta ao início. Agora torne os pontos aleatórios: jogue n pontos uniformemente num quadrado de lado 1 e pergunte qual é o comprimento do percurso mais curto.

Em 1959, Beardwood, Halton e Hammersley provaram uma resposta surpreendente. À medida que n cresce, o comprimento do melhor percurso fica quase certamente igual a β√n, onde β é uma constante universal — a mesma para toda dispersão aleatória. Eles também mostraram que 0,625 ≤ β ≤ 0,9212.

Mais de sessenta e cinco anos depois, ninguém conhece β. Não existe fórmula. Grandes experimentos em computador a situam em cerca de 0,7124, mas um experimento não é uma prova. Até agora, os melhores limites provados eram 0,6277 ≤ β ≤ 0,90367. Essas constantes importam na logística, onde são usadas para estimar o comprimento de rotas de entrega sem calculá-las — por isso o novo resultado vem da McCombs School of Business da Universidade do Texas em Austin, assinado por Zhuolun Dong e Junyu Cao.

O novo intervalo

O artigo prova:

0,6421 ≤ β ≤ 0,8810

e, usando amostragem aleatória, mostra que 0,6536 ≤ β ≤ 0,8749 com probabilidade de pelo menos 1 − 2 × 10⁻⁴. Essa probabilidade diz respeito ao acaso da amostragem no computador, não ao próprio β, que é um número fixo.

Por baixo: cortar as arestas longas

Para provar que todo percurso tem de ser longo, os autores observam o que acontece quando se apagam todas as arestas de um percurso mais longas que um certo comprimento r. O percurso se quebra em pedaços de caminho, e cada pedaço fica dentro de um aglomerado de pontos que estão a menos de r uns dos outros. Quanto mais caminhos um aglomerado precisa para ser coberto, mais arestas longas o percurso devia ter. Somando isso sobre todos os valores possíveis de r, obtém-se o comprimento do percurso:

ℓ(H) = ∫₀^∞ N_H(r) dr,

onde N_H(r) conta as arestas mais longas que r.

Os pontos isolados e as extremidades dos caminhos dão o antigo termo 5/8 = 0,625 — exatamente o limite de 1959. O ingrediente novo é uma série de correções vindas de pequenos aglomerados de 3, 4 e 5 pontos, cada uma uma integral sobre as posições possíveis dos pontos. Essas integrais não podem ser calculadas exatamente, então os autores dividem seus domínios em cubos minúsculos e limitam cada cubo por baixo, com cada número irracional arredondado no sentido desfavorável, para que o resultado seja um limite genuíno:

β ≥ 0,625 + 0,01113528859 + 0,005040573276 + 0,001015487669 > 0,6421.

Por cima: zigue-zague em blocos de cinco

Um limite superior só precisa de um bom percurso. A receita clássica corta o quadrado em faixas horizontais e as percorre em zigue-zague, da esquerda para a direita, depois da direita para a esquerda. A novidade: dentro de cada faixa, os pontos são tomados em blocos de cinco, e cada bloco é visitado na melhor de suas 24 ordens possíveis.

O comprimento esperado de um bloco é uma integral em onze dimensões — cinco intervalos horizontais entre pontos e seis alturas. Os autores a limitam numericamente numa grade fina, de novo com números racionais arredondados no sentido seguro, e obtêm β < 0,8810.

A distância que resta

O intervalo se estreitou de uma largura de cerca de 0,28 para cerca de 0,24, mas o valor empírico 0,7124 continua bem dentro dele. Grades mais finas, estimativas mais precisas das áreas de discos sobrepostos e blocos mais longos poderiam apertá-lo ainda mais. Fechar a distância restante, escrevem os autores, “pode exigir novas técnicas”.