Уже были разработаны алгоритмы, гарантированно выдающие для любой сети маршруты, длина которых превышает длину оптимального маршрута не более чем на 50 процентов. Но я-то хочу получить хитрый шорткат, который позволит находить без утомительных поисков самый лучший маршрут. Эта задача настолько измучила математиков, что многие пришли к убеждению, что такого шортката просто не существует. Доказательство невозможности существования этого шортката даже стало предметом одной из семи «Задач тысячелетия», величайших нерешенных математических задач, список которых был составлен в начале XXI века [125]. Математик, который сумеет доказать, что шортката к решению задачи коммивояжера не существует, получит в награду миллион долларов.
Что такое шорткат?
Чтобы выиграть миллионный приз, важно, собственно говоря, определить, что именно с точки зрения математики можно считать в этом контексте шорткатом. Математически различие длинного пути и шортката выражается в том, что первый приходит к решению за экспоненциальное время, а второй – всего лишь за полиномиальное. Что я имею в виду?
Рис. 10.2. Конфигурация девяти плиток, в которой узоры соседних квадратов согласуются
Эта задача сводится к нахождению алгоритмического метода, работающего не только для одной конкретной головоломки, но и для головоломок с любыми вариантами условий и размеров. Вопрос в том, как изменяется время работы алгоритма в зависимости от размера заданной ему задачи. Например, предположим, что у меня есть набор из 9 плиток, и на всех этих плитках есть разные узоры. Я хочу расположить эти плитки квадратом 3 × 3 так, чтобы узоры в смежных квадратах согласовывались друг с другом.
Сколько существует вариантов раскладки таких плиток? Для левого верхнего угла существует 9 возможностей: я могу положить туда любую из девяти плиток. У этой плитки есть 4 возможные ориентации. Всего получается 9 × 4 = 36 вариантов. Плитка, которая займет следующий квадрат, может быть любой из 8 оставшихся; у нее тоже есть 4 возможных варианта ориентации. Таким образом, суммарное число вариантов заполнения всего квадрата получается равным
9! × 49,
где 9! обозначает произведение 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1, которое называют «9 факториал». Если компьютер может проверять по 100 миллионов вариантов в секунду, перебор всех этих возможностей займет у него чуть больше 15 минут. Не так уж и плохо. Но посмотрите, как быстро это время увеличивается с ростом числа плиток. Возьмем 16 плиток, которые нужно уложить в квадрат 4 × 4. Из рассуждений, аналогичных приведенным выше, следует, что число возможных комбинаций равно
16! × 416
Это увеличивает время, необходимое для перебора всех этих вариантов, до 28,5 миллиона лет. Если же перейти к простому квадрату 5 × 5, оно превысит возраст Вселенной, составляющий всего-навсего 13,8 миллиарда лет.
Число возможных конфигураций сетки с n положениями определяется формулой n! × 4n. Функция 4n растет с увеличением n экспоненциально. Я уже рассказывал о том, как опасен рост этой функции, в главе 1, когда индийский царь должен был заплатить за изобретение шахмат рисовыми зернами, число которых экспоненциально увеличивалось по мере продвижения по клеткам шахматной доски. А факториал n! (произведение всех чисел от 1 до n) – это функция, рост которой на самом деле еще быстрее экспоненциального.
Таково математическое определение длинного пути: алгоритм решения задачи, время работы которого, необходимое для вычисления ответа, экспоненциально возрастает с увеличением размера задачи. Именно для таких задач хотелось бы найти шорткаты. Но что считать качественным шорткатом? Так можно назвать алгоритм, по-прежнему вычисляющий решение сравнительно быстро даже при увеличении размера задачи: так называемый алгоритм полиномиального времени.
Предположим, у меня есть случайный набор слов, которые я хочу расположить в алфавитном порядке. Сколько времени будет занимать эта работа по мере все большего удлинения списка слов? Простой алгоритм для решения этой задачи мог бы в начале просмотреть весь исходный список из N слов и выбрать из него слово, стоящее в словаре раньше всех остальных. Затем нужно повторить ту же операцию для оставшихся N – 1 слов. Таким образом, чтобы расставить по порядку все N слов, нужно будет перебрать N + (N – 1) + (N – 2) + … + 1 слово. Но благодаря шорткату Гаусса мы знаем, что для этого потребуется в общей сложности N × (N + 1)/2 = (N2 + N)/2 просмотров.
Это пример алгоритма полиномиального времени, потому что по мере увеличения числа слов N число просмотров растет пропорционально квадрату N. В случае задачи коммивояжера нужно найти алгоритм, который сможет находить кратчайший маршрут для N городов, перебрав всего, скажем, N2 вариантов, то есть число маршрутов, пропорциональное квадрату числа городов.
К сожалению, первые алгоритмы, приходящие в голову, не относятся к полиномиальным. По сути дела, сначала мы выбираем первый город, в который нужно заехать, затем следующий… Если на карте всего N городов, это требует перебора N! маршрутов. Как я уже говорил, эта функция растет еще быстрее, чем экспоненциальная. Следовательно, необходимо найти стратегию, более рациональную, чем перебор всех маршрутов.
Шорткат к шорткатам
Чтобы показать, что существование такого алгоритма не всегда невозможно, рассмотрим задачу, которая на первый взгляд кажется столь же непреодолимой. Выберем две точки, обозначенные на карте в числе городов, которые должен посетить коммивояжер. Какой маршрут между этими двумя городами будет самым коротким? На первый взгляд кажется, что и здесь необходимо рассмотреть множество вариантов. В конце концов, можно начать с посещения любого города, непосредственно соединенного с начальным, а затем посетить один из городов, непосредственно соединенных уже с этим. Судя по всему, с увеличением числа городов сложность такого метода снова будет расти экспоненциально.
Но в 1956 году голландский программист Эдсгер В. Дейкстра придумал гораздо более рациональную стратегию, позволяющую находить кратчайший маршрут между двумя городами за время, аналогичное тому, что занимает перестановка слов в алфавитном порядке. Он обдумывал практическую проблему прокладки самого быстрого
