Это увеличивает время, необходимое для перебора всех этих вариантов, до 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 году голландский программист Эдсгер В. Дейкстра придумал гораздо более рациональную стратегию, позволяющую находить кратчайший маршрут между двумя городами за время, аналогичное тому, что занимает перестановка слов в алфавитном порядке. Он обдумывал практическую проблему прокладки самого быстрого маршрута между двумя голландскими городами, Роттердамом и Гронингеном.
Однажды утром мы с моей молодой невестой ходили по магазинам в Амстердаме, устали и сели на террасе кафе выпить по чашке кофе. Я размышлял, смогу ли я решить эту задачу, и вдруг разработал алгоритм кратчайшего пути. Его изобретение заняло минут двадцать… Одна из причин, по которым он получился таким изящным, в том, что я разработал его без карандаша и бумаги. Позднее я понял, что одно из преимуществ работы без карандаша и бумаги состоит в том, что это почти что вынуждает избегать всех осложнений, которых можно избежать. В конце концов, к моему огромному удивлению, этот алгоритм стал одним из краеугольных камней моей известности.
Рассмотрим следующую карту:
Рис. 10.3. Каков кратчайший маршрут между городами 1 и 5?
Алгоритм Дейкстры предполагает, что я начинаю путешествие из начального города, города 1. На каждом этапе я буду вычислять для каждого города промежуточную сумму расстояний, что должно помочь мне найти кратчайший маршрут. Первым делом я помечу все города, связанные с начальным, расстояниями до них. В данном случае города 2, 3 и 6 получают соответственно метки 7, 9 и 14, и первым ходом я перемещаюсь в ближайший из этих городов. Однако следует помнить, что, когда алгоритм чудесным образом решит задачу, может оказаться, что самым лучшим первым ходом был переезд совсем в другой город.
Итак, вначале я переезжаю в город 2, потому что он расположен на самом малом расстоянии от начального пункта, города 1.
Затем я присваиваю городу 1, из которого я только что уехал, метку «посещенного». Находясь в следующем пункте, городе 2, я должен изменить метки всех городов, связанных с ним. Следовательно, речь идет о городах 3 и 4. Сначала я вычисляю расстояние до них от исходного пункта, города 1, через тот пункт, в котором я нахожусь, город 2. Если новое расстояние короче, чем то, которым следующий город помечен сейчас, я присваиваю ему метку с новым расстоянием. Если новое расстояние больше, город сохраняет старую метку. В случае города 3 новое расстояние (7 + 10) больше старого; следовательно, у этого города остается старая метка с числом 9. У некоторых городов, например города 4, может не быть предыдущей метки, потому что они не связаны с городами, которые я посетил до этого. Теперь я присваиваю этим новым городам метки с только что вычисленными расстояниями до них. Таким образом, город 4 получает метку с числом 7 + 15 = 22.
Теперь я снова помечаю город, в котором я нахожусь, как посещенный и переезжаю в следующий город, имеющий самую малую текущую сумму расстояний от начального пункта. В результате описанных выше операций таким пунктом оказывается город 3. В этом примере видно, что, хотя первое перемещение в город 2 казалось рациональным, дальнейший путь из него оказывается не самым коротким. Поэтому уже на этом этапе алгоритм может склоняться к прокладке маршрута через город 3.
Оказавшись в городе 3, я снова пересчитываю метки связанных с ним городов, которые я еще не посетил. Продолжая этот процесс, я в конце концов доберусь до пункта назначения, города 5, и его метка будет обозначать кратчайшее расстояние от города, с которого я начал. Затем можно воспроизвести все перемещения в обратном порядке, чтобы выяснить, через какие города проходит маршрут, соответствующий этому расстоянию. Обратите внимание, что в описанном случае он, как выясняется, вовсе не проходит через город 2.
