Величайшие математические задачи

Расстановка слов в списке в алфавитном порядке представляет собой задачу класса P. Простейший способ выполнить эту задачу — это так называемый «пузырьковый» метод, получивший название потому, что слова, находящиеся ниже по списку, чем следует, при этом «всплывают» вверх, как пузырьки в стакане газировки. Алгоритм раз за разом просматривает список, сравнивает соседние слова и меняет их местами, если порядок не соответствует алфавитному. Пусть, к примеру, список вначале выглядит так:

РОГ ДОМ БОТ АКТ

Сначала происходит следующее:

ДОМ РОГ БОТ АКТ

ДОМ БОТ РОГ АКТ

ДОМ БОТ АКТ РОГ

Полужирным шрифтом выделены те слова, сравнение которых проводилось только что и которые были (или не были) переставлены. При втором проходе получаем:

БОТ ДОМ АКТ РОГ

БОТ АКТ ДОМ РОГ

БОТ АКТ ДОМ РОГ

Третий проход:

АКТ БОТ ДОМ РОГ

АКТ БОТ ДОМ РОГ

АКТ БОТ ДОМ РОГ

На четвертом проходе ничего не происходит, так что мы понимаем, что программа завершила работу. Обратите внимание, как слово АКТ постепенно всплывает вверх (т. е. к началу списка).

Если в списке четыре слова, алгоритм на каждом шагу проводит три сравнения, а всего шагов получается четыре. Если слов в списке n, то на каждом проходе проводится n − 1 сравнение, а проходов необходимо n, так что всего требуется n (n − 1) шагов. Это чуть меньше, чем n², так что время работы программы полиномиально, более того, квадратично. Алгоритм может прекратить работу раньше, но в самом худшем случае, если окажется, что слова в списке стоят точно в обратном порядке, ему потребуется n (n − 1) шагов. Пузырьковый алгоритм сортировки очевиден и относится к классу P, но это далеко не самый эффективный алгоритм. Самый быстрый алгоритм сортировки — алгоритм сравнения — организован более хитро и выполняется за nlogn шагов.

Простой алгоритм с экспоненциальным временем работы — алгоритм класса E — это, к примеру, задание «распечатать список всех n-значных двоичных чисел». В таком списке 2ⁿ чисел, и на печать (и вычисление) каждого уходит примерно n шагов, так что полное время работы составляет приблизительно 2ⁿn, что больше, чем 2ⁿ, но меньше, чем 3ⁿ для достаточно больших n. Однако это довольно глупый пример, поскольку медленным его делает не сложность вычислений, а всего лишь размер выходных данных, и позже это наблюдение окажется весьма важным.

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

n! =n(n— 1) × (n— 2) × … × 3 × 2 × 1

маршрутов (читается «n факториал»). Эта величина растет быстрее, чем любая экспоненциальная величина{37}. Более эффективный метод, известный как динамическое программирование, позволяет решить задачу о коммивояжере за экспоненциальное время. Первый подобный метод — алгоритм Хелда — Карпа — находит кратчайший маршрут за 2ⁿn² шагов; при достаточно больших n это опять же попадает в интервал между 2ⁿ и 3ⁿ.

Несмотря на то что эти алгоритмы «неэффективны», при помощи специальных уловок можно ускорить расчет в случае, если число городов велико по человеческим меркам, но не слишком велико для применения подобных хитростей. В 2006 г. Д. Эпплгейт, Р. Биксби, В. Шваталь и У. Кук решили задачу о коммивояжере для 85 900 городов. На середину 2012 г. это достижение все еще оставалось рекордным.

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