Беда в том, что по мере добавления новых городов число возможных маршрутов стремительно растет, и перебор всех возможных вариантов становится практически невозможным, даже на компьютере. Разве нет более быстрого способа выбрать лучшее решение? Неужели не найдется какого-нибудь очередного Эйлера или Гаусса или Ньютона, который придумал бы хитроумную стратегию определения кратчайшего маршрута? Нельзя ли, например, каждый раз просто выбирать следующим город, ближайший к тому, в котором оказался коммивояжер? Эта методика называется алгоритмом ближайшего соседа. Во многих случаях она дает весьма хорошие маршруты, всего на 25 процентов длиннее оптимального. Однако совсем не трудно построить такую сеть, в которой этот алгоритм выдает не самый короткий, а самый длинный маршрут объезда городов.

Уже были разработаны алгоритмы, гарантированно выдающие для любой сети маршруты, длина которых превышает длину оптимального маршрута не более чем на 50 процентов. Но я-то хочу получить хитрый шорткат, который позволит находить без утомительных поисков самый лучший маршрут. Эта задача настолько измучила математиков, что многие пришли к убеждению, что такого шортката просто не существует. Доказательство невозможности существования этого шортката даже стало предметом одной из семи «Задач тысячелетия», величайших нерешенных математических задач, список которых был составлен в начале XXI века[125]. Математик, который сумеет доказать, что шортката к решению задачи коммивояжера не существует, получит в награду миллион долларов.

Что такое шорткат?

Что такое шорткат?

Чтобы выиграть миллионный приз, важно, собственно говоря, определить, что именно с точки зрения математики можно считать в этом контексте шорткатом. Математически различие длинного пути и шортката выражается в том, что первый приходит к решению за экспоненциальное время, а второй – всего лишь за полиномиальное. Что я имею в виду?

Рис. 10.2. Конфигурация девяти плиток, в которой узоры соседних квадратов согласуются

Эта задача сводится к нахождению алгоритмического метода, работающего не только для одной конкретной головоломки, но и для головоломок с любыми вариантами условий и размеров. Вопрос в том, как изменяется время работы алгоритма в зависимости от размера заданной ему задачи. Например, предположим, что у меня есть набор из 9 плиток, и на всех этих плитках есть разные узоры. Я хочу расположить эти плитки квадратом 3 × 3 так, чтобы узоры в смежных квадратах согласовывались друг с другом.

Сколько существует вариантов раскладки таких плиток? Для левого верхнего угла существует 9 возможностей: я могу положить туда любую из девяти плиток. У этой плитки есть 4 возможные ориентации. Всего получается 9 × 4 = 36 вариантов. Плитка, которая займет следующий квадрат, может быть любой из 8 оставшихся; у нее тоже есть 4 возможных варианта ориентации. Таким образом, суммарное число вариантов заполнения всего квадрата получается равным