СКРЫТОЕ ЧИСЛО КОММИВОЯЖЁРА ЗАГНАНО В УГОЛ

Использование ИИ заявлено. В «Заявлении об использовании ИИ» авторы указывают, что применяли ИИ-инструмент GPT-5.6 Sol Pro при подготовке статьи, что проверили и подтвердили все результаты и что несут полную ответственность за её содержание. Их код доступен по запросу.

Задача коммивояжёра — найти кратчайший маршрут, который посещает каждую точку множества по одному разу и возвращается в начало. Теперь сделаем точки случайными: бросим n точек равномерно в квадрат со стороной 1 и спросим, какова длина кратчайшего маршрута.

В 1959 году Бирдвуд, Халтон и Хаммерсли доказали поразительный ответ. С ростом n длина лучшего маршрута почти наверное становится равной β√n, где β — универсальная постоянная, одна и та же для любого случайного разброса. Они также показали, что 0,625 ≤ β ≤ 0,9212.

Спустя более шестидесяти пяти лет β никто не знает. Формулы нет. Масштабные компьютерные эксперименты дают около 0,7124, но эксперимент — не доказательство. До сих пор лучшими доказанными оценками были 0,6277 ≤ β ≤ 0,90367. Такие постоянные важны в логистике, где с их помощью оценивают длину маршрутов доставки, не вычисляя их, — поэтому новый результат пришёл из бизнес-школы Маккомбса Техасского университета в Остине, от Чжолуня Дуна и Цзюньюй Цао.

Новая вилка

В статье доказано:

0,6421 ≤ β ≤ 0,8810

а с помощью случайной выборки показано, что 0,6536 ≤ β ≤ 0,8749 с вероятностью не менее 1 − 2 × 10⁻⁴. Эта вероятность относится к случайности компьютерной выборки, а не к самому β, который является фиксированным числом.

Снизу: отрезать длинные рёбра

Чтобы доказать, что любой маршрут должен быть длинным, авторы смотрят, что произойдёт, если удалить все рёбра маршрута длиннее некоторой длины 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 по-прежнему лежит глубоко внутри неё. Более мелкие сетки, более точные оценки площадей перекрывающихся кругов и более длинные блоки могли бы сузить её ещё сильнее. Чтобы закрыть оставшийся зазор, пишут авторы, «могут потребоваться новые методы».