Величайшие математические задачи - Йен Стюарт

Некоторые алгоритмы настолько эффективны, что выполняют работу намного быстрее, чем за полиномиальное время. К примеру, чтобы определить четность или нечетность числа, достаточно посмотреть на его последнюю цифру. Если (в десятичной записи) это цифра 0, 2, 4, 6 или 8, число — четное, в противном случае — нечетное. Весь алгоритм включает в себя не более шести шагов:

Последняя цифра — 0? Если да, то СТОП. Число четное.

Последняя цифра — 2? Если да, то СТОП. Число четное.

Последняя цифра — 4? Если да, то СТОП. Число четное.

Последняя цифра — 6? Если да, то СТОП. Число четное.

Последняя цифра — 8? Если да, то СТОП. Число четное.

СТОП. Число нечетное.

Итак, время выполнения программы ограничено шестью шагами, вне зависимости от размера входных данных. Такой алгоритм относится к классу алгоритмов «постоянного времени».

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Можно вспомнить все ту же вторую главу. Пока команда Агравала не придумала свой алгоритм класса P для проверки на простоту, наилучший известный алгоритм принадлежал классу не-P. Тем не менее он тоже был достаточно хорош, считал за время nlogn для n-значных чисел, а это, вообще говоря, лучше, чем показатели алгоритма Агравала — Каяла — Саксены, пока мы не достигаем чисел с 101000 знаками. До открытия этого алгоритма мнения о статусе испытания на простоту разделялись. Некоторые специалисты считали, что это задача класса P и подходящий алгоритм рано или поздно будет найден. Другие были уверены, что этого не произойдет. Новый алгоритм возник практически ниоткуда: его породила одна из бесчисленных идей, которые можно было попробовать, и данная конкретная идея сработала. Это отрезвляющий прецедент: мы не знаем истинного положения вещей, не можем предсказать его заранее, и догадки лучших экспертов могут быть как верными, так и ошибочными.

Великая задача, которая нас в данный момент интересует, заключается в поиске ответа на более фундаментальный вопрос. Существуют ли сложные задачи? Могут ли все задачи оказаться простыми, если, конечно, приложить достаточно ума и сообразительности? На самом деле здесь есть одна тонкость, потому что мы уже видели одну несомненно сложную задачу: распечатку списка всех n-значных двоичных чисел. Я уже упоминал о том, что это глупый пример: сложность заключается не в расчетах, а в простой монотонной работе по распечатке очень длинного ответа. Нам известно, что никакие уловки здесь не помогут, поскольку ответ будет таким длинным по определению. Если бы он был короче, он не был бы ответом.