Учитель пытается составить расписание на следующий год. Автоперевозчик прокладывает оптимальные маршруты доставки товаров для своих грузовиков. Кладовщик супермаркета ищет рациональные способы укладки коробок на полки. Футбольному болельщику не терпится узнать, сможет ли его команда победить в своей лиге. Любитель судоку хочет получить действенную стратегию решения этих дьявольских головоломок. Все они стараются найти шорткаты. Но, как ни жаль, на свете есть задачи, решению которых лучшее мышление не помогает. Даже самому Гауссу, попытайся он решить такую задачу, пришлось бы взяться за тяжкий труд перебора всех возможных сценариев. Возможно, поразительнее всего тот факт, что доказательства невозможности существования шорткатов для некоторых задач дает само искусство шортката – математика.
Классическая задача, к решению которой, по мнению математиков, не может быть шортката, называется задачей коммивояжера. В ней нужно найти кратчайший маршрут по сети городов. Ее название, по-видимому, связано с изданным в 1832 году в Германии справочником для коммивояжеров, в котором приводилась формулировка задачи и несколько примеров маршрутов по Германии и Швейцарии[124]. Математики до сих пор не придумали для гарантированного решения этой задачи ничего умнее, чем перебор всех возможных маршрутов в поисках кратчайшего.
Беда в том, что по мере добавления новых городов число возможных маршрутов стремительно растет, и перебор всех возможных вариантов становится практически невозможным, даже на компьютере. Разве нет более быстрого способа выбрать лучшее решение? Неужели не найдется какого-нибудь очередного Эйлера или Гаусса или Ньютона, который придумал бы хитроумную стратегию определения кратчайшего маршрута? Нельзя ли, например, каждый раз просто выбирать следующим город, ближайший к тому, в котором оказался коммивояжер? Эта методика называется алгоритмом ближайшего соседа. Во многих случаях она дает весьма хорошие маршруты, всего на 25 процентов длиннее оптимального. Однако совсем не трудно построить такую сеть, в которой этот алгоритм выдает не самый короткий, а самый длинный маршрут объезда городов.
Уже были разработаны алгоритмы, гарантированно выдающие для любой сети маршруты, длина которых превышает длину оптимального маршрута не более чем на 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 миллиарда лет.
Число возможных конфигураций сетки с
Таково математическое определение длинного пути: алгоритм решения задачи, время работы которого, необходимое для вычисления ответа, экспоненциально возрастает с увеличением размера задачи. Именно для таких задач хотелось бы найти шорткаты. Но что считать качественным шорткатом? Так можно назвать алгоритм, по-прежнему вычисляющий решение сравнительно быстро даже при увеличении размера задачи: так называемый алгоритм полиномиального времени.
Предположим, у меня есть случайный набор слов, которые я хочу расположить в алфавитном порядке. Сколько времени будет занимать эта работа по мере все большего удлинения списка слов? Простой алгоритм для решения этой задачи мог бы в начале просмотреть весь исходный список из
Это пример алгоритма полиномиального времени, потому что по мере увеличения числа слов
К сожалению, первые алгоритмы, приходящие в голову, не относятся к полиномиальным. По сути дела, сначала мы выбираем первый город, в который нужно заехать, затем следующий… Если на карте всего
Шорткат к шорткатам
Чтобы показать, что существование такого алгоритма не всегда невозможно, рассмотрим задачу, которая на первый взгляд кажется столь же непреодолимой. Выберем две точки, обозначенные на карте в числе городов, которые должен посетить коммивояжер. Какой маршрут между этими двумя городами будет самым коротким? На первый взгляд кажется, что и здесь необходимо рассмотреть множество вариантов. В конце концов, можно начать с посещения любого города, непосредственно соединенного с начальным, а затем посетить один из городов, непосредственно соединенных уже с этим. Судя по всему, с увеличением числа городов сложность такого метода снова будет расти экспоненциально.