Оказавшись в городе 3, я снова пересчитываю метки связанных с ним городов, которые я еще не посетил. Продолжая этот процесс, я в конце концов доберусь до пункта назначения, города 5, и его метка будет обозначать кратчайшее расстояние от города, с которого я начал. Затем можно воспроизвести все перемещения в обратном порядке, чтобы выяснить, через какие города проходит маршрут, соответствующий этому расстоянию. Обратите внимание, что в описанном случае он, как выясняется, вовсе не проходит через город 2.

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

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

Если компьютер способен выполнять 100 миллионов операций в секунду, это не будет слишком большой проблемой при малом N. Но между временами работы алгоритма, находящего ответ за N² шагов, и алгоритма, находящего ответ за N⁵ шагов, огромная разница.

За одну секунду алгоритм сложности N² может проверить сеть из 10 000 городов. Алгоритму сложности N⁵ для проверки такого же числа городов потребуется 31 710 лет! И тем не менее это считается математическим шорткатом. По сравнению с экспоненциальным алгоритмом, который был у нас до сих пор, – а ему для перебора 10 000 городов требуется время, превосходящее возраст Вселенной, – это, несомненно, и есть шорткат. Более того, за время, равное возрасту Вселенной, алгоритм сложности 2^N не способен перебрать даже 100 городов.

Однако с практической точки зрения целесообразно бороться за алгоритмы с как можно более низкими степенями N. Некоторые короткие пути бывают короче других.

Иголки в стогах

Иголки в стогах

Вы можете надеяться, что, раз вы не коммивояжер, отсутствие шортката к прокладке кратчайшего маршрута, позволяющего объехать всех покупателей, вас не касается. Беда в том, что задач с такими же осложнениями существует очень много. Например, инженеру может понадобиться спроектировать электронную схему из сотни элементов так, чтобы робот прокладывал соединения между ними самым рациональным образом. Поскольку этот робот будет производить тысячи таких плат в сутки, сокращение времени его путешествия по соединениям этой сети даже на несколько секунд может дать компании огромную экономию средств. Но нам хотелось бы найти шорткаты не только к маршрутам перемещения по сетям. Ниже перечислены некоторые из задач, обладающих тем же качеством, что и задача коммивояжера, – задач, к решению которых, насколько нам известно, может не существовать шорткатов. Возможно, даже великий Гаусс не избежал бы при их решении долгой и нудной работы!