Это пример алгоритма полиномиального времени, потому что по мере увеличения числа слов N число просмотров растет пропорционально квадрату N. В случае задачи коммивояжера нужно найти алгоритм, который сможет находить кратчайший маршрут для N городов, перебрав всего, скажем, N² вариантов, то есть число маршрутов, пропорциональное квадрату числа городов.

К сожалению, первые алгоритмы, приходящие в голову, не относятся к полиномиальным. По сути дела, сначала мы выбираем первый город, в который нужно заехать, затем следующий… Если на карте всего N городов, это требует перебора N! маршрутов. Как я уже говорил, эта функция растет еще быстрее, чем экспоненциальная. Следовательно, необходимо найти стратегию, более рациональную, чем перебор всех маршрутов.

Шорткат к шорткатам

Шорткат к шорткатам

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

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

Однажды утром мы с моей молодой невестой ходили по магазинам в Амстердаме, устали и сели на террасе кафе выпить по чашке кофе. Я размышлял, смогу ли я решить эту задачу, и вдруг разработал алгоритм кратчайшего пути. Его изобретение заняло минут двадцать… Одна из причин, по которым он получился таким изящным, в том, что я разработал его без карандаша и бумаги. Позднее я понял, что одно из преимуществ работы без карандаша и бумаги состоит в том, что это почти что вынуждает избегать всех осложнений, которых можно избежать. В конце концов, к моему огромному удивлению, этот алгоритм стал одним из краеугольных камней моей известности.