旅行商问题的隐藏常数被逼入更小的范围

已声明使用人工智能。 在“人工智能使用声明”中，作者表示他们在准备论文时使用了人工智能工具GPT-5.6 Sol Pro，审阅并核实了所有结果，并对论文内容承担全部责任。他们的代码可应要求提供。

旅行商问题要求找出一条最短回路，访问一组点中的每个点各一次，并回到起点。现在让这些点随机分布：把n个点均匀地撒进边长为1的正方形里，问最短回路有多长。

1959年，比尔德伍德（Beardwood）、霍尔顿（Halton）和哈默斯利（Hammersley）证明了一个惊人的答案。随着n增大，最佳回路的长度几乎必然等于β√n，其中β是一个普适常数——对每一种随机撒点都相同。他们还证明了0.625 ≤ β ≤ 0.9212。

六十五年多过去了，仍然没有人知道β。它没有公式。大规模计算机实验给出的值约为0.7124，但实验不是证明。在此之前，已证明的最佳界是0.6277 ≤ β ≤ 0.90367。这类常数在物流中很重要，人们用它们来估算配送路线的长度而无需实际计算——这也是为什么这项新成果来自得克萨斯大学奥斯汀分校的麦库姆斯商学院，作者是董卓伦（Zhuolun Dong）和曹君宇（Junyu Cao）。

新的区间

论文证明了：

0.6421 ≤ β ≤ 0.8810

并且利用随机抽样，以至少1 − 2 × 10⁻⁴的概率证明了0.6536 ≤ β ≤ 0.8749。这个概率涉及的是计算机抽样的随机性，而不是β本身——β是一个固定的数。

从下方：剪掉长边

为了证明每条回路都必须足够长，作者考察了删除回路中所有长于某个长度r的边会发生什么。回路断裂成若干段路径，每一段都停留在一个点簇之内，簇中的点彼此相距不超过r。一个点簇需要越多条路径才能覆盖，回路中就必然有越多条长边。把所有可能的r累加起来，就得到回路长度：

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

其中N_H(r)计数长于r的边。

孤立点和路径端点给出了原来的项5/8 = 0.625——恰好是1959年的界。新的成分是一系列来自3个、4个和5个点的小簇的修正项，每一项都是对这些点可能位置的积分。这些积分无法精确计算，因此作者把积分区域切成微小的立方体，并对每个立方体给出下界，所有无理数都朝不利方向取整，以确保结果是一个真正的界：

β ≥ 0.625 + 0.01113528859 + 0.005040573276 + 0.001015487669 > 0.6421。

从上方：以五个点为一组之字形穿行

上界只需要一条好的回路。经典做法是把正方形切成水平条带，并以之字形依次扫过，先从左到右，再从右到左。新的变化是：在每个条带内，点以五个为一组选取，每组按其24种可能顺序中最好的一种访问。

一组的期望长度是一个十一维积分——五个点之间的水平间距和六个高度。作者在精细网格上对其进行数值估界，同样用有理数并朝安全方向取整，得到β < 0.8810。

剩下的差距

区间宽度已从约0.28缩小到约0.24，但经验值0.7124仍远在区间之内。更细的网格、对重叠圆盘面积更精确的估计以及更长的分组，可能进一步收紧这个区间。作者写道，要缩小剩下的距离，“可能需要新的技术”。