巡回セールスマンの隠れた数、追い詰められる

AIの使用を申告。 著者らは「AI使用の開示」のなかで、論文の準備にAIツールGPT-5.6 Sol Proを使ったこと、すべての結果を見直して検証したこと、内容に全面的な責任を負うことを述べている。コードは請求に応じて提供される。

巡回セールスマン問題は、点の集合のそれぞれの点を一度ずつ訪れて出発点に戻る、最短の巡回路を求める問題だ。ここで点をランダムにしてみよう。一辺1の正方形にn個の点を一様に投げ入れ、最短の巡回路がどれだけ長いかを問うのだ。

1959年、ビアドウッド(Beardwood)、ハルトン(Halton)、ハマーズリー(Hammersley)は、目を見張る答えを証明した。nが大きくなると、最良の巡回路の長さはほぼ確実にβ√nに等しくなる。ここでβは普遍定数で、どんなランダムなばらまき方でも同じだ。彼らはまた、0.625 ≤ β ≤ 0.9212であることも示した。

それから65年以上たっても、βの値は誰も知らない。公式はない。大規模な計算機実験では約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

上から:5個ずつのブロックでジグザグ

上限には、良い巡回路が一つあればよい。古典的な方法では、正方形を横長の帯に切り、左から右、右から左とジグザグにたどる。新しい工夫は、それぞれの帯のなかで点を5個ずつのブロックにまとめ、各ブロックを24通りの順序のうち最良のもので訪れることだ。

ブロックの長さの期待値は11次元の積分になる。点のあいだの5つの水平方向の間隔と、6つの高さだ。著者らはこれを細かい格子で数値的に評価し、ここでも有理数を安全な方向に丸めて、β < 0.8810を得た。

残るすき間

範囲の幅は約0.28から約0.24に狭まったが、経験的な値0.7124はまだその内側の奥深くにある。より細かい格子、重なり合う円の面積のより鋭い見積もり、より長いブロックを使えば、さらに狭められるかもしれない。残りの距離を詰めるには、と著者らは書いている。「新しい手法が必要になるかもしれない」。