Искусство мыслить рационально. Шорткаты в математике и в жизни - Маркус Дю Сотой

Это увеличивает время, необходимое для перебора всех этих вариантов, до 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.