Пессимальные Алгоритмы и Анализ Вычислительной Усложнённости

«Усложнённость (Simplexity) — процесс, которым природа достигает простых результатов сложными путями.» — Bruce Schiff

1. Введение

Представьте себе следующую задачу: у нас есть таблица из n целочисленных ключей A₁, A₂, …, A_n, и целочисленное значение X. Нам нужно найти индекс числа X в этой таблице, но при этом мы особо никуда не торопимся. На самом деле, мы бы хотели делать это как можно дольше.

Для этой задачи мы могли бы остановиться на самом тривиальном алгоритме, а именно, перебирать все A_n по порядку и сравнивать их с X. Но, может так случиться, что X = A₁, и алгоритм остановится на самом первом шаге. Таким образом, мы видим, что наивный алгоритм в наилучшем случае имеет временную сложность O(1). Возникает вопрос — можем ли мы улучшить (то есть, ухудшить) этот результат?

Разумеется, мы можем сильно замедлить этот алгоритм, добавив в него пустых циклов перед первой проверкой равенства X и A₁. Но, к сожалению, этот способ нам не годится, потому что любой дурак заметит, что алгоритм просто-напросто впустую тратит время. Таким образом, нам нужно найти такой алгоритм, который бы всё-таки продвигался к цели, не смотря на отсутствие энтузиазма, или вовсе желания до неё в конечном итоге дойти.

Мы можем построить алгоритм, который удовлетворяет этому требованию, и который сильно лучше (медленнее), чем наивный алгоритм, если отсортируем таблицу А в порядке возрастания. Затем, мы сможем использовать процедуру, реализующую ленивый поиск, которая представлена ниже:

Число сравнений в этом алгоритме не зависит ни от X, ни от A_i и задаётся следующей рекурсивной формулой:

Из которой получаем, что

Тем самым, получаем ухудшение в n раз по сравнению с наивным алгоритмом. Обратите внимание, что отсутствие энтузиазма у алгоритма ленивого поиска совершенно не очевидно из его поведения, потому что он проверяет равенство X и A_i каждые O(1) операций, никогда не сравнивает одни и те же значения, и останавливается, когда искомое значение найдено. Немногие алгоритмы поиска, честные или не очень, могут сравниться с ним по производительности.

2. Обобщение

Процедура research является примером совершенно нового направления Информатики (Computer Science) — дизайна и анализа ленивых алгоритмов. Интуитивно, ленивый алгоритм, решающий задачу P, — это алгоритм, который впустую тратит время настолько мудрёным образом, что позволяет обмануть среднестатистического наивного наблюдателя. Мы можем написать это утверждение строгим математическим языком, говоря, что A является ленивым алгоритмом для задачи P тогда и только тогда,

где, N — множество наивных наблюдателей, t — время, W(A, t, w, P) — предикат, который означает «А тратит время t впустую способом w решая задачу P», а F(w, o) — предикат, который означает «способ w достаточно запутан, чтобы обмануть o». Относительно конечности множества N мы не делаем никаких предположений.

При изучении ленивых алгоритмов, производительность алгоритма А лучше всего описывается его неэффективностью или временем выполнения в наилучшем случае — минимумом (как функция от n) времени выполнения А при всех возможных входных данных длины n. Усложненность задачи Р — максимальная неэффективность среди всех ленивых алгоритмов, которые решают задачу Р. Алгоритм называют пессимальным для задачи P, если неэффективность А в наилучшем случае асимптотически стремится к усложненности Р.

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

3. Задача нахождения пути в интересных графах

Поиск в таблице можно рассматривать, как особый случай следующей более общей задачи. Допустим, у нас есть «лабиринт» — ненаправленный граф G с n вершинами и вершиной u отмеченной как «вход». Наша задача найти путь от вершины u до вершины v, отмеченной как «выход», двигаясь по лабиринту по одному ребру за единицу времени. Следуя классическому анализу алгоритмов, скорее всего, мы бы сразу обратились к одному из эффективных алгоритмов поиска кратчайшего пути в графе. Однако, допустим, что этот лабиринт довольно интересный внутри, и что мы в принципе были бы непротив провести несколько дополнительных циклов алгоритма в поиске вершины v. На самом деле, мы надеемся… нет, мы несомненно желаем, чтобы поиск занял как можно больше времени. При том, что наше чувство долга не даёт нам полностью забросить поиски, мы не сможем долго игнорировать первобытные потребности нашей человеческой природы. Кроме того, что плохого в расслабленном подходе к решению задачи, если мы всё равно делаем то, что нужно? Тем более, что нам всегда говорили «поспешишь — людей насмешишь», и, в любом случае, никому не обязательно быть идеальным. Ну, и всё в таком духе…

Принимая всё это во внимание, мы видим, что эта задача очень хорошо ложится в предметную область нашей теории.

На самом деле, эта задача была широко изучена в Теории Графов, где получила название «задача нахождения самого небрежного пути». Важный раздел Математических Методов Исследования Операций, который называют Анемичное Программирование, полностью посвящен неэффективным методам решения этой задачи. Что мы знаем о её усложненности? Ранее, как было показано Вагнером^{[Вагнер]}, если мы ничего не знаем о нахождении v, наилучшее время может быть так же мало, как O(1): на каждом шаге, даже на самом первом, мы рискуем наступить на v и провалиться из лабиринта, не смотря на то, как бы мы ни хотели этого избежать. Однако, как показал Гомер^[Гомер], если граф находится на плоскости (или плоском земном шаре), и у нас есть оракул, который подобно компасу показывает в каком направлении находится цель, мы можем оттянуть момент прибытия к цели, пока не посетим большую часть вершин графа. На самом деле, время, на которое мы можем оттянуть этот момент, ограничено не столько усложнённостью задачи, сколько её монотонностью^[1]. Неэффективность алгоритма Гомера равна Ω(n), что является нижней границей усложненности задачи нахождения самого небрежного пути.
————————
^[1] Также известная как скучность.

Метод ленивого поиска и алгоритм небрежного пути Гомера оба основаны на одной и той же идее, известной как Метод Немощного Спуска. Мы также хотим вскользь упомянуть еще одну важную парадигму дизайна ленивых алгоритмов, которая была описана Гомером в той же работе, и которой автор дал яркое название Хитрость Пенелопы. Она основана на использовании цикла for, в котором шаг осцилирует между положительными и отрицательными значениями на каждой итерации. К сожалению, эта техника (которая сейчас называется Метод с Возвратом) стала настолько известной, что даже самый наивный наблюдатель может без труда её распознать. Так что, сейчас она представляет лишь исторический интерес.

4. Поиск назад

Довольно похожей задачей является систематическое перечисление всех n вершин связного графа G. Эта задача была хорошо изучена в классической Теории Алгоритмов, и обычно решается хорошо известными алгоритмами поиска в глубину^[Верн1] или поиска в ширину^[Верн2], у которых временная сложность в наилучшем случае принадлежит Ω(n).

Долгое время принято было считать это верхней границей усложненности задачи, пока 4го октября 1984г в 14:17 комьюнити ленивых алгоритмистов не пошатнулось открытием алгоритма поиска, который принадлежит Ω(n²) по неэффективности на важном классе графов. Метод поиска назад, как он был назван своим изобретателем, будет описан ниже. Как и его предшественники, алгоритм назначает вершинам v₁, v₂, …, v_n графа G целые числа λ(v₁), λ(v₂), …, λ(v_n) от 1 до n. Алгоритм представлен рекурсивной процедурой bwfs. Мы полагаем, что все числа λ(v) изначально равны нулю. Рекурсия начинается с вызова bwfs(v_l, 1).

Мы оставим читателю поучительное упражнение доказать корректность алгоритма и показать, что его неэффективность действительно принадлежит ϴ(n²) для графов, представляющих собой прямые линии. Интересной особенностью с точки зрения пессимальности расходуемой памяти в этом случае является то, что глубина рекурсии bwfs может достигать ϴ(n²) в зависимости от стартовой точки графа. Неэффективность этого алгоритма на обычных графах остается нерешенной задачей, но, вроде бы, алгоритм никогда не быстрее, чем O(n√n).

Интересное замечание, достаточно удалить один из циклов for, чтобы из bwfs получить знакомый нам поиск в глубину. Однако, порядок, в котором в первый раз проходятся вершины графа, весьма странный и запутанный, и он совсем не похож на порядок, получаемый алгоритмом прохода в глубину.

По определению, нумерация назад вершин графа — это значения λ(v), которые были присвоены вершинам этим алгоритмом. Как у нумераций в глубину и в ширину, у этой нумерации есть несколько интересных свойств. Из-за ограничения на размер текста, мы приведем лишь пару из них. Если грани графа направлены таким образом, что граф является ациклическим, то либо λ(head(e)) ≥ λ(tail(e))) для всех граней e, либо λ(head(e)) ≤ λ(tail(e)) для всех граней e. Более того, если d — максимальная степень вершин графа, то для любых двух смежных вершин u и v будет верно, что |λ(u) − λ(v)| ≤ d log min(λ(u), λ(v)). Эти и другие свойства нумерации назад делают ее очень важной с точки зрения комбинаторики.

5. Медленносорт

Ни одна другая задача не показывает мощь и элегантность ленивой алгоритмики так, как сортировка n заданных чисел. Эта задача обладает длинной и богатой историей, начала которой прослеживаются очень давно, уж точно раньше, чем становление ленивой алгоритмики, как признанной дисциплины во второй половине прошлой среды. Благодаря стараниям множества пионеров индустрии, неэффективность алгоритмов сортировки неуклонно росла от скромной Ω(n log n) алгоритма Сортировки Слиянием (Merge Sort) к Ω(n √n) Сортировки Шелла (Shell’s Sort) с определеннымыми инкрементами, к Ω(n²) Сортировки Пузырьком (Bubble Sort), и наконец, к хитрому алгоритму поиска, принадлежащему Ω(n³), недавно описанному Бентли^{[Бентли]}. (Видимо, впервые он был опубликован Steele, Woods, Finkel, Crispin, и Goodfellow^[SWFCG])

Один из наиболее важных результатов современной теории усложнённости, это доказательство того, что задача сортировки может быть решена за время Ω(n^log(n)/(2+e)). Это первая найденная задача с неполиномиальной усложнённостью. Элегантный алгоритм, который достикает такой неэффективности называется Медленносорт (Slowsort) и описан ниже.

Алгоритм Медленносорт является идеальным примером парадигмы Умножай и Сдавайся, которая, пожалуй, является самой важной парадигмой разработки ленивых алгоритмов. Идея стратегии Умножай и Сдавайся заключается в том, чтобы заменить данную задачу двумя или более подзадачами, каждая из которых лишь немного проще оригинала, а далее продолжать множить подзадачи рекурсивно, пока это возможно. В какой-то момент все подзадачи будут настолько просты, что их решение уже нельзя будет отложить, в этот момент мы будем вынуждены сдаться. Опыт показывает, что в большинстве случаев, к этому времени общее количество впустую проделанной работы будет значительно больше, чем если бы мы использовали более прямой подход.

Чтобы лучше понять стратегию Умножай и Сдавайся, давайте по шагам рассмотрим разработку алгоритма Медленносорт. Мы можем разделить задачу сортировки чисел A₁, A₂, …, A_n по возрастанию на две подзадачи: (1) найти максимум этих чисел, (2) отсортировать остальные. Подзадача (1) может быть дальше разделена на подзадачи: (1.1) найти максимум первых [n/2] элементов, (1.2) найти максимум последних [n/2] элементов, (1.3) найти наибольшее из этих двух значений. И наконец, подзадачи (1.1) и (1.2) могут быть решены путём сортировки элементов и выбора последнего (читай максимального) элемента отсортированного массива. Таким образом мы преумножили первичную задачу на три лишь немного более простых подзадачи (плюс накладные расходы): отсортировать первую половину, отсортировать вторую половину, отсортировать все элементы кроме одного. Мы продолжим делать это рекурсивно, пока все размноженные массивы не будут содержать не более одного элемента. В этот момент нам придётся сдаться.

Рекурсивное определение времени выполнения Медленносорта будет выглядеть знакомо для тех, кто прочитал cекцию 3. В общем-то, получается T(n) = 2T(n/2) + T(n − 1). Расстояние Хэмминга между этой формулой и хорошо известной рекурсивной формулой Сортировки Слиянием (Merge Sort) T(n) = 2T(n/2) + cn равно всего лишь 5, но простой довод о конечных различиях показывает, что этого достаточно, чтобы у первого уравнения не было полиномиально ограниченного решения. На самом деле, можно показать, что решение удовлетворяет следующим неравенствам^[1]:

для любого фиксированного e > 0 и двух констант C_a и C_b. Идея доказательства (а нам сказали, что нашу статью напечатают только, если в ней будет хотябы одно доказательство) в том, чтобы предположить, что T(n) = C₁n^{C₂ ln n} для некоторых констант. Тогда

————————
^[1] Мы используем «log» для логарифма по основанию 2 и «ln» для натуральных логарифмов.

Считая, что C₂ = 1/(2 ln 2), мы получаем, что T(n) ≤ C_bn^log(n)/2, а считая, что C₂ = 1/((2 + e) ln 2), мы получаем, что T(n) ≥ C_an^log(n)/(2+e) для существенно больших n. (Константы C_a и C_b просто подставные значения (ориг. fudge factor), чтобы запустить индукцию.) Следуя духу ленивой алгоритмики, более детальное доказательство будет предоставлено авторами в ближайшем будущем в виде сканированных изображений перфокарт с кодом доказательства на EQN записанных на 7-дорожковых EBCDIC кассетах с нечетным контрольным битом.

В качестве практического применения, очевидно, что Медленносорт является наиболее подходящим алгоритмом, если вдруг ваш босс посылает вас отсортировать что-нибудь в Париж. Одно из хороших свойств этого алгоритма заключается в том, что количество инверсий в А не возрастает. Так что, в определенном смысле (в смысле, вы в Париже, все расходы покрыты), Медленносорт никогда не делает неверных шагов.

6. Выводы и нерешенные задачи

В течение долгого времени Информатика (Computer Science) занималась только исследованием либо наихудших, либо средних сценариев работы алгоритмов. В этой публикации мы впервые пытаемся исправить очевидную дискриминацию изучения наилучших сценариев, и мы можем только надеяться, что за нами подтянутся и другие.

Анализ Медленносорта привел нас к следующему предположению, которое мы называем Увеличивающейся Гипотезой (УГ): Если сложность задачи равна O(gf), где g и f — функции от длины входных данных, и f = o(g), тогда усложнённость этой задачи равна Θ(g^f).

Дополненная Увеличивающаяся Гипотеза (ДУГ) утверждает, что, если сложность задачи равна O(g+f), то её усложненность равна Θ(gf). Очевидно, что ДУГ подразумевает УГ.

Доказательство или опровержение УГ — одна из основных задач Теории Усложнённости. Однако, мы вынуждены закончить печальным фактом, что скорее всего доказать УГ невозможно из-за хорошо известной неполноты арифметики Пеано.

Благодарность

Нам бы хотелось поблагодарить Ed Lasowska и Lyle Ramshaw за их неленивую помощь.

Ссылки

[Бентли] Д. Л. Бентли, Перлы Программирования, CACM, 27(1984) 287-291
[Вагнер] Р. Вагнер, Тангейзер, (либретто на французском и немецком), L’avant-scène, Париж, 1984
[Верн1] Ж. Верн, Путешествие к Центру Земли, (английский перевод), Heritage Press, 1966
[Верн2] Ж. Верн, Вокруг Света за 80 Дней, (английский перевод), International Collectors Library, 1956
[Гомер] Г. Гомер, Иллиада и Одиссей, перевод Самуеля Батлера, Encyclopedia Britannica, Чикаго, 1952
[SWFCG] Г. Стиль и другие, Словарь Хакера, Harper and Row, 1983

Примечание

Статья была напечатана в ACM SIGACT NEWS, 16(3):49-53, 1984. После этого она была перенабрана с плохой фотокопии Гордоном Лэком (Gordon Lack) в 2000 году. А в конце 2013 года переведена на русский язык Валентином Симоновым (valyard).

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

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