Кузюрин Н.Н. Фомин С.А. Эффективные алгоритмы и сложность вычислений

Подождите немного. Документ загружается.

1.2. Формально об алгоритмах. Несложно о сложности 61

существенно меньше t(n). Более формальное определение мож-

но найти в разделе 6.1.2.

1.2.3. Сложность в среднем

Другая возможность заключается в рассмотрении сложности

в среднем. В этой постановке вводится некоторое (например,

равномерное) вероятностное распределение на массивах вход-

ных данных битовой длины ≤ n, и сложностью t(n) называется

математическое ожидание времени работы нашего алгорит-

ма на случайном входе, выбранном в соответствии с этим рас-

пределением. Пример анализа в среднем нами уже рассмотрен

для алгоритма быстрой сортировки. Более интересные приме-

ры такого анализа рассмотрены далее, где приводятся полино-

миальные в среднем алгоритмы для ряда N P-трудных задач

(см. раздел 3.5).

Следует отметить, что, несмотря на свою внешнюю привле-

кательность, сложность в среднем в настоящее время не может

конкурировать со сложностью в худшем случае по объему про-

водимых исследований, хотя интенсивность исследований в об-

ласти вероятностного анализа поведения алгоритмов в послед-

ние годы заметно увеличивается. Сложность в среднем также

естественным образом возникает в криптографии при анализе

стойкости различных криптосистем.

1.2.4. Полиномиальные алгоритмы

Итак, алгоритмы для одной и той же задачи целесообраз-

но сравнивать по асимптотическому поведению их сложно-

сти t(n). В теории сложности вычислений традиционно игно-

рируются мультипликативные константы в оценках сложности.

Вызвано это тем, что в большинстве случаев эти константы

привносятся некоторыми малоинтересными внешними факто-

рами, и их игнорирование позволяет абстрагироваться от та-

кого влияния. Приведем несколько примеров таких факторов.

62 Глава 1. Алгоритмы и их сложность

Во-первых, при несущественных модификациях вычисли-

тельной модели сложность обычно изменяется не более чем на

некоторую (как правило, довольно небольшую) мультиплика-

тивную константу. Например, если мы разрешим в машинах

со случайным доступом оператор цикла for, то ввиду наличия

моделирования (см. рис. 1.8) сложность от этого может умень-

шиться не более чем в два раза. Следовательно, если мы иг-

норируем мультипликативные константы, можем свободно ис-

пользовать в машинах со случайным доступом for-do-endfor

циклы и другие алголоподобные конструкции, не оговаривая

всякий раз это специально.

Во-вторых, при переходе от двоичной к восьмеричной или

десятичной системе счисления длина битовой записи, а сле-

довательно, и сложность полиномиальных алгоритмов изме-

няется не более чем на мультипликативную константу. Таким

образом, путем игнорирования таких констант также можно

абстрагироваться от вопроса о том, в какой системе счисления

мы работаем, и вообще не указывать явно в наших оценках

основание логарифмов.

Кроме того, имеет место приблизительное равенство: «фи-

зическое время работы = среднее время выполнения одного

оператора × однородная сложность».

В этой формуле теория сложности вычислений отвечает

за второй сомножитель, а первый зависит от того, насколько

грамотно составлена программа, от качества транслятора на

язык низшего уровня (что определяет, например, сколько вре-

мени занимает доступ к памяти или жесткому диску), быстро-

действия вычислительной техники и т. д. Хоть эти вопросы и

важны, они выходят за рамки теории сложности вычислений,

и игнорирование мультипликативных констант позволяет аб-

страгироваться от них и выделить интересующий нас второй

сомножитель в чистом виде.

По этой причине в теории сложности вычислений ши-

рокое распространение получило обозначение «O-большое».

1.2. Формально об алгоритмах. Несложно о сложности 63

Типичный результат выглядит следующим образом: «данный

алгоритм работает за время O(n

log n)», и его следует по-

нимать как «существует такая константа c > 0, что время

работы алгоритма в наихудшем случае не превышает cn

log n,

начиная с некоторого n».

Практическая ценность асимптотических результатов тако-

го рода зависит от того, насколько мала неявно подразумевае-

мая константа c. Как мы уже отмечали выше, для подавляю-

щего большинства известных алгоритмов она находится в ра-

зумных пределах, поэтому, как правило, имеет место следу-

ющий тезис: алгоритмы, более эффективные с точки зрения

их асимптотического поведения, оказываются также более

эффективными и при тех сравнительно небольших размерах

входных данных, для которых они реально используются на

практике.

Теория сложности вычислений по определению считает, что

алгоритм, работающий за время O(n

log n) лучше алгорит-

ма с временем работы O(n

), и в подавляющем большинстве

случаев это отражает реально существующую на практике си-

туацию. И такой способ сравнения эффективности различных

алгоритмов оказывается достаточно универсальным — слож-

ность в наихудшем случае с точностью до мультипликативной

константы для подавляющего большинства реально возникаю-

щих алгоритмов оказывается достаточно простой функцией

и практически всегда функции сложности разных алгоритмов

можно сравнить между собой по их асимптотическому поведе-

нию.

Таким образом, можно определять классы алгоритмов, за-

мкнутых относительно выбора вычислительной модели.

Следует оговориться, что иногда рассматривают функции сложности,

зависящие от двух-трех параметров, например, от числа вершин и ребер

входного графа, или вертикального и горизонтального размера входной

матрицы. Тем не менее, даже в таких случаях часто удается провести

сравнение асимптотической сложности различных алгоритмов.

64 Глава 1. Алгоритмы и их сложность

Определение 1.2.1. Алгоритм называется полиномиаль-

ным, если его сложность в наихудшем случае t(n) ограничена

сверху некоторым полиномом (многочленом) от n.

Это определение оказывается вполне независимым относи-

тельно выбора вычислительной модели: любые «разумные» мо-

дели (модели, в которых не может происходить экспоненциаль-

ного нарастания памяти, как в алгоритме 13 «Переполнение

памяти умножением») оказываются равносильными в смысле

этого определения.

Например, нетрудно убедиться, что алгоритм 7 «Дейкст-

ры» и алгоритм 9 «MST Прима» полиномиальны. Для задачи

«умножение двух чисел» также имеется полиномиальный алго-

ритм, хотя алгоритм 14 «Умножение» и неполиномиален. В са-

мом деле, его однородная сложность равна R

+ 1, что не огра-

ничено никаким полиномом от битовой длины dlog

(|R

| + 1)e.

Полиномиальный алгоритм для умножения легко строится,

например, с помощью моделирования обыкновенного умноже-

ния столбиком (проделайте это в качестве упражнения).

Полиномиальные алгоритмы противопоставляются экс-

поненциальным, т. е. таким, для которых t(n) ≥ 2

для

некоторой фиксированной константы k ≥ 1 и почти всех n.

Например, экспоненциальными являются алгоритмы 6 «TSP-

перебор», 13 «Переполнение памяти умножением» (относи-

тельно однородной меры сложности) и 14 «Умножение».

В теории сложности задач дискретной оптимизации есте-

ственным образом возникают по крайней мере две модифика-

ции понятия полиномиального алгоритма, одно из которых яв-

ляется его усилением, а другое — ослаблением.

Предположим, что полиномиальный алгоритм к тому же

еще и однороден. Тогда он обладает следующими двумя свой-

ствами (второе из которых, как мы видели выше, влечет пер-

вое):

1.2. Формально об алгоритмах. Несложно о сложности 65

1) длина битовой записи всех чисел, возникающих в процес-

се работы алгоритма, ограничена некоторым полиномом

от длины битовой записи входных данных (это свойство

на самом деле присуще любому полиномиальному алго-

ритму);

2) число арифметических операций (однородная сложность)

ограничено полиномом от размерности задачи.

Основная причина, по которой мы предпочли не рассмат-

ривать умножение и деление в качестве основных операций,

состоит в том, что это нарушило бы импликацию 2 ⇒ 1 (см. ал-

горитм 13 «Переполнение памяти умножением»). Но если мы

разрешим умножение и деление и при этом потребуем, чтобы

свойство 1 обеспечивалось внутренней структурой алгоритма,

то мы получим класс алгоритмов, называемых в литературе

сильно полиномиальными алгоритмами.

Таким образом, сильно полиномиальные алгоритмы обоб-

щают однородные полиномиальные алгоритмы. Хорошим

примером сильно полиномиального алгоритма, который, по-

видимому, нельзя привести к однородному виду (т. е. изба-

виться от делений и умножений), служит известный алгоритм

Гаусса решения систем линейных уравнений.

Итак, отличительной чертой сильно полиномиальных ал-

горитмов является то, что время их работы ограничено поли-

номом от размерности задачи. На другом полюсе находятся

псевдополиномиальные алгоритмы, в которых требуется, что-

бы время работы алгоритма было полиномиально лишь от сум-

мы абсолютных значений (а не от битовой длины записи) вхо-

дящих в задачу числовых параметров. Типичные примеры та-

ких алгоритмов приведены в разделе 2.2.1.

1.2.5. Полиномиальность и эффективность

Может ли полиномиальный алгоритм быть неэффективным?

Разумеется, может, если в полиномиальной оценке времени его

66 Глава 1. Алгоритмы и их сложность

работы t(n) ≤ C · n

либо мультипликативная константа C, ли-

бо показатель k чрезмерно велики.

Опыт показывает, что такое случается крайне редко, и по-

давляющее большинство полиномиальных алгоритмов для

естественных задач удовлетворяет оценке t(n) ≤ 10 · n

. В тех

же немногих случаях, когда полиномиальный алгоритм ока-

зывается малопригодным с практической точки зрения, это

обстоятельство всегда стимулирует бурные исследования по

построению на его основе действительно эффективного алго-

ритма, что, как правило, приводит к интересным самим по

себе побочным следствиям. Хрестоматийным примером такого

рода может служить метод эллипсоидов для линейного про-

граммирования [Kha79], стимулировавший бурное развитие

целого направления ([Kar84]), получившего название «метод

внутренней точки» и занявшего в настоящее время лидирую-

щие позиции в разработке наиболее эффективных алгоритмов

для задач линейного программирования большой размерности.

Кстати, одна из самых известных современных откры-

тых проблем в теории алгоритмов (и вообще математики)

заключается в ответе на вопрос: «существует ли сильно поли-

номиальный алгоритм для задачи линейного программирова-

ния?» ([Sma00]).

Упражнение 1.2.1. Посмотрите на каждый из приведенных

ранее алгоритмов и определите, является ли он полиномиаль-

ным, сильно полиномиальным или псевдополиномиальным?

Может ли неполиномиальный алгоритм быть эффектив-

ным? Ответ утвердительный, по меньшей мере, по трем при-

чинам. Во-первых, может случиться так, что примеры, на ко-

торых время работы алгоритма велико, настолько редки, что

вероятность обнаружить хотя бы один из них на практике пре-

небрежимо мала. В математических терминах это означает, что

алгоритм полиномиален в среднем относительно любого «ра-

зумного» вероятностного распределения и, по-видимому, под

эту категорию попадает симплекс-метод (см. [Схр91]).

1.2. Формально об алгоритмах. Несложно о сложности 67

Во-вторых, многие псевдополиномиальные алгоритмы яв-

ляются эффективными, когда возникающие на практике чис-

ловые параметры не слишком велики.

Наконец, субэкспоненциальные алгоритмы, время работы

которых, например, имеет вид O(n

c log log log n

), при всех разум-

ных длинах входа n могут быть весьма практически эффек-

тивными.

Но в заключение еще раз подчеркнем, что примеров задач,

на которых нарушается основополагающее равенство

«полиномиальность»=«эффективность»

крайне мало по сравнению с числом примеров, на которых оно

блестяще подтверждается.

Отметим, что единственную серьезную конкуренцию маши-

нам RAM как основы для построения теории сложности вычис-

лений на сегодняшний день составляют так называемые маши-

ны Тьюринга, которые мы будем рассматривать в разделе 6.1.

Их принципиальное отличие состоит в отсутствии непрямой

индексации: после проведения каких-либо действий с некото-

рой ячейкой процессор («головка») может перейти лишь в одну

из «соседних» ячеек. Машины Тьюринга удобны при рассмот-

рении комбинаторных задач с небольшим количеством число-

вых параметров, а также (в силу своей структурной простоты)

для теоретических исследований.

Глава 2

Аппроксимация с гарантированной

точностью

2.1. Алгоритмы с оценками точности

Приближенные алгорит-

мы с оценками точности.

Жадные алгоритмы для задач

типа покрытия и упаковки.

Приближенные алгоритмы на

графах.

Одним из общих подходов к решению N P-трудных задач,

который активно развивается в настоящее время, является раз-

работка приближенных алгоритмов с гарантированными оцен-

ками качества получаемого решения.

Точность приближенного алгоритма характеризует муль-

типликативная ошибка, которая показывает, в какое макси-

мально возможное число раз может отличаться полученное ре-

шение от оптимального (по значению заданной целевой функ-

ции).

Определение 2.1.1. Алгоритм называется C-приближен-

ным, если при любых исходных данных он находит допусти-

2.1. Алгоритмы с оценками точности 69

мое решение со значением целевой функции, отличающимся

от оптимума не более чем в C раз.

Заметим, что иногда также говорят об

-приближенных ал-

горитмах, причем смысл отклонения (больше или меньше еди-

ницы) обычно ясен из контекста и направления оптимизации

(максимизации или минимизации). Мультипликативная ошиб-

ка может быть константой или зависеть от параметров входной

задачи. Наиболее удачные приближенные алгоритмы позволя-

ют задавать точность своей работы. В качестве примера пе-

речислим приближенные алгоритмы, которые мы рассмотрим

далее в этой книге:

• 2-приближенный алгоритм для задачи о рюкзаке из раз-

дела 2.1.3.

• 3/2-приближенный алгоритм для метрической задачи

коммивояжера из раздела 2.1.4.

• 0, 878-приближенный алгоритм для задачи о максималь-

ном разрезе в графе из раздела 4.4.2.

• 2-приближенный алгоритм для минимального вершинно-

го покрытия из раздела 2.1.2.

• (1 + ln m)-приближенный алгоритм для задачи о покры-

тии из раздела 2.1.1.

• (1 + ε)-приближенный алгоритм для задачи о рюкзаке из

раздела 2.2.2.

70 Глава 2. Аппроксимация с гарантированной точностью

2.1.1. Жадные алгоритмы для



Покрытия мно-

жеств



Жадные алгоритмы для

задачи о покрытии под-

множеств, локальный

алгоритм для вершинного

покрытия.

Одной из простейших эвристик, часто применяемых при

решении различных задач, является так называемая жадная

эвристика. Для некоторых задач, например, для задачи об

остовном дереве минимального веса в графе, эта эвристика

фактически позволяет найти оптимальное решение (см. алго-

ритм 9 «MST Прима»). В более трудных случаях она позволяет

получать гарантированные оценки точности получаемого с ее

помощью решения.

Рассмотрим сейчас жадную эвристику для классической

N P-трудной задачи — задачи о покрытии.

Задача 10. «Покрытие множества»

• Множество X, |X| = m.

• Семейство подмножеств {S

, . . . , S

}, S

⊆ X.

• X = ∪

j=1

(покрытие гарантировано).

Найти минимальное по мощности множество подмно-

жеств, покрывающее X:

|J| → min,

J ⊆ {1, 2, . . . , n},

X = ∪

j∈J

В англоязычной литературе — Set Cover.