Какова же длительность процесса выявления кратчайшего маршрута в шагах алгоритма? При наличии N городов она оказывается сравнимой с длительностью перестановки слов в алфавитном порядке. На каждом шаге из рассмотрения исключается очередной город, который не нужно учитывать в дальнейшем. Поэтому время, необходимое алгоритму для решения задачи, пропорционально N2, то есть квадрату N. С точки зрения математики это несомненный шорткат!
Но на практике даже то, что на этом математическом языке называется шорткатом, может требовать для получения решения чрезвычайно долгого времени. В общем случае математики действительно считают алгоритмы полиномиального времени, подобные тому, который ищем мы, шорткатами. Квадратичные алгоритмы и в самом деле работают довольно быстро. Но, хотя математики называют быстрыми и алгоритмы третьей, четвертой или пятой степени, их работа может занимать долгое физическое время.
Если компьютер способен выполнять 100 миллионов операций в секунду, это не будет слишком большой проблемой при малом N. Но между временами работы алгоритма, находящего ответ за N2 шагов, и алгоритма, находящего ответ за N5 шагов, огромная разница.
За одну секунду алгоритм сложности N2 может проверить сеть из 10 000 городов. Алгоритму сложности N5 для проверки такого же числа городов потребуется 31 710 лет! И тем не менее это считается математическим шорткатом. По сравнению с экспоненциальным алгоритмом, который был у нас до сих пор, – а ему для перебора 10 000 городов требуется время, превосходящее возраст Вселенной, – это, несомненно, и есть шорткат. Более того, за время, равное возрасту Вселенной, алгоритм сложности 2N не способен перебрать даже 100 городов.
Однако с практической точки зрения целесообразно бороться за алгоритмы с как можно более низкими степенями N. Некоторые короткие пути бывают короче других.
Иголки в стогах
Вы можете надеяться, что, раз вы не коммивояжер, отсутствие шортката к прокладке кратчайшего маршрута, позволяющего объехать всех покупателей, вас не касается. Беда в том, что задач с такими же осложнениями существует очень много. Например, инженеру может понадобиться спроектировать электронную схему из сотни элементов так, чтобы робот прокладывал соединения между ними самым рациональным образом. Поскольку этот робот будет производить тысячи таких плат в сутки, сокращение времени его путешествия по соединениям этой сети даже на несколько секунд может дать компании огромную экономию средств. Но нам хотелось бы найти шорткаты не только к маршрутам перемещения по сетям. Ниже перечислены некоторые из задач, обладающих тем же качеством, что и задача коммивояжера, – задач, к решению которых, насколько нам известно, может не существовать шорткатов. Возможно, даже великий Гаусс не избежал бы при их решении долгой и нудной работы!
Задача о багажнике. Вам нужно перевезти в багажнике автомобиля коробки разных размеров. Задача требует отобрать те коробки, при укладке которых останется меньше всего неиспользованного пространства. Как выясняется, никакого рационального алгоритма, позволяющего выбрать оптимальное сочетание коробок, исходя из их размеров, не существует. Предположим, что все коробки имеют одинаковую высоту и ширину, которые точно совпадают с внутренними размерами багажника, но разную длину. Длина багажника – 150 см, а длина имеющихся в вашем распоряжении коробок равна 16, 27, 37, 42, 52, 59, 65 и 95 см. Есть ли какой-нибудь удобный способ выбрать такое сочетание коробок, которое заполнит багажник с наименьшими потерями?
Задача о расписании уроков. В начале каждого учебного года каждая школа сталкивается с задачей составления расписания для учеников. Но у возможностей распределения занятий по расписанию есть ограничения, связанные с тем, какие предметы выбирает каждый из учеников. Поскольку Ада решила заниматься химией и музыкой, уроки по этим предметам нельзя назначать на одно и то же время. А Алан выбрал химию и киноведение. Но в день может быть всего восемь уроков. Школе нужно каким-то образом втиснуть в расписание все предметы так, чтобы ни у кого не было нескольких уроков в одно и то же время. С учетом всех этих ограничений составление расписания иногда бывает похоже на укладку ковра в комнате с не вполне подходящими размерами. Не успеешь уложить ковер в одном углу, как он вспучивается в другом. Еще это похоже на решение судоку: казалось бы, все числа наконец оказались на нужных местах, как вдруг обнаруживается, что в одной из строк стоят две двойки. Черт!
Судоку. Если вы уже пытались решить какие-нибудь из самых трудных вариантов этой японской головоломки, вам случалось попадать в ситуации, в которых, по-видимому, остается только выбрать следующее число наудачу, а затем разбираться с логическими следствиями из этого решения. Если это решение было неверным и приводит к противоречию, вам остается только вернуться к тому шагу, на котором вы его приняли, и попытаться пойти по другому пути.
Задача о званом ужине. Проблема, сходная с задачей о расписании уроков, возникает, когда вы хотите пригласить друзей на ужин, но некоторые из них не ладят друг с другом, и вы не хотите приглашать их на один и тот же ужин. Чтобы определить минимальное количество ужинов, на которых у вас побывают все, но так, чтобы ни на одном из них не встретились те, кто не хочет встречаться, необходимо перебрать все возможные комбинации приглашенных.
Раскрашивание карты. Если взять любую географическую карту и попытаться раскрасить страны так, чтобы никакие две граничащие страны не были закрашены одним и тем же цветом, этого всегда можно добиться, используя четыре цвета. Но нельзя ли обойтись всего тремя? И в этом случае единственный имеющийся у нас алгоритм, позволяющий определить, хватит ли трех цветов для раскрашивания карты, сводится к перебору всех возможных вариантов ее раскрашивания. Как и при решении судоку, можно начать закрашивать страны, а потом обнаружить, что сделанный ранее выбор цветов приводит к тому, что две соседние страны приходится закрасить одним и тем же цветом. Если на карте изображены N стран, существует 3N способов раскраски этих стран тремя цветами, что означает, что число возможных вариантов растет экспоненциально.
Тот факт, что для этого требуется не более четырех цветов, был предметом одной из величайших теорем, доказанных в XX веке. Еще в 1890 году теорема была доказана для пяти цветов. Это доказательство было не слишком сложным: оно было основано на шорткате, часто используемом математиками. Предположим, что существуют карты, которые невозможно раскрасить пятью цветами. Возьмем такую карту с наименьшим числом стран. Тогда при помощи некоторых хитроумных выкладок можно показать, что одна страна может быть удалена так, что и оставшуюся карту нельзя будет раскрасить пятью цветами. Но это противоречит исходному утверждению, что изначальная карта содержала наименьшее возможное количество стран.
Вот, кстати, пример несерьезного применения шортката, в котором мы рассматриваем наименьший экземпляр чего-либо, чтобы доказать, что такой объект не может существовать: доказательство невозможности существования неинтересных чисел. Предположим, что неинтересные числа существуют. Пусть N – наименьшее неинтересное число. Но сам тот факт, что это наименьшее неинтересное число, делает его интересным.
