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

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

3.5.



Рюкзак



: полиномиальность в среднем 141

событие A

событие B

событие C

Используя соотношение

P(A|B) =

P(A ∩ B)

P(B)

получим

P(A|B ∩ C) · P(C|B) + P(A|B ∩ C) · P(C|B) =

y + z

x + y + z + w

x + w

x + y + z + w

x + y

x + y + z + w

= P(A|B).

Теперь мы готовы оценить вероятность малого прироста

стоимости доминирующего подмножества:

Лемма 3.5.6. P(ДельтаМала|ПаретоНабор) ≤ 2nε.

Доказательство. Оценим P(ДельтаМала|ПаретоНабор), используя

леммы 3.5.3, 3.5.4, 3.5.5:

P(ДельтаМала|ПаретоНабор) =

= P(ДельтаМала|ПаретоНабор ∩ ВНабореНеМалы) · P(ВНабореНеМалы|ПаретоНабор)

+ P(ДельтаМала|ПаретоНабор ∩ ВНабореНеМалы) · P(ВНабореНеМалы|ПаретоНабор)

≤ P(ДельтаМала|ПаретоНабор∩ВНабореНеМалы)+P(ВНабореНеМалы|ПаретоНабор)

≤ nε + nε = 2nε.

142 Глава 3. Вероятностный анализ алгоритмов

Определения и

Лемма 3.5.2 (Δ

> 0)

Лемма 3.5.4

P(Δ < ε| 6 ∃малый) ≤ nε

Лемма 3.5.3

P(∃малый) ≤ nε

Теорема 3.5.1

E(q) = O(n

)

Лемма 3.5.6

P(Δ < ε) ≤ 2nε

Лемма 3.5.5

P(A|B) = P(A|B ∩ C) · ...

Рис. 3.6. Граф зависимостей утверждений в разделе 3.5

Теперь мы готовы перейти к доказательству самой теоре-

мы. Возьмем ε =

, тогда

E(Δ

|Δ

> 0) ≥ ε

· P(ДельтаМала|ПаретоНабор) =

= ε

· (1 − P(ДельтаМала|ПаретоНабор)) ≥

≥ ε

· (1 − 2nε) =

· (1 −

) =

27n

Обозначим математическое ожидание стоимости S

через

. S

— это множество максимального веса и стоимости, со-

держащее все предметы.

С одной стороны,

= n · E(c

) =

С другой стороны, учитывая, что стоимость пустого на-

бора S

равна нулю, стоимость S

можно подсчитать, как

u∈{2, ...,m}:Δ

, и

3.5.



Рюкзак



: полиномиальность в среднем 143

u=2

P(Δ

> 0) E(Δ

|Δ

> 0) ≥

27n

u=2

P(Δ

> 0).

Откуда получаем

u=2

P(Δ

> 0) = 27n

Теперь мы можем выразить математическое ожидание размера

множества доминирующих решений:

E(q) = 1 +

u=2

P(Δ

> 0) ≤ 1 +

= O(n

Вспоминая, что сложность алгоритма равна O(nq), получа-

ем полиномиальность алгоритма 25 «Рюкзак Немхаузера–Уль-

мана» в среднем, разумеется, на случайных входных данных

с описанным в начале раздела распределением.

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

мами) раздела 3.5 на рис. 3.6.

Следует отметить, что в работе [BV03] доказана полино-

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

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

в задаче о рюкзаке.

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

ритма 25 «Рюкзак Немхаузера–Ульмана» на случайных дан-

ных, можно увидеть на рисунке 3.7. Представлено время (по-

казатель time) работы алгоритма 25 «Рюкзак Немхаузера–Уль-

мана» и максимальный размер множества частичных решений

(показатель ParetoS) в зависимости от n — числа предметов

для рюкзака.

144 Глава 3. Вероятностный анализ алгоритмов

Рис. 3.7. Алгоритм 25 «Рюкзак Немхаузера–Ульмана» на случайных дан-

ных

Глава 4

Вероятностные алгоритмы и их

анализ

4.1. Вероятностная проверка тождеств

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

лее эффективных, чем детерминированные, был предложен

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

AB = C (см. [Fre77]).

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

ремножении матриц A и B и сравнении результата с C.

Сложность такого алгоритма есть O(n

) при использовании

стандартного алгоритма умножения матриц размера n × n и

O(n

2.376

) при использовании лучшего из известных быстрых

алгоритмов матричного умножения [CW90].

Вероятностный алгоритм Фрейвалда для этой задачи имеет

сложность O(n

) и заключается в умножении левой и правой

частей на случайный булев вектор x = (x

, . . . , x

) с после-

дующим сравнением полученных векторов. Алгоритм выдает

ответ, что AB = C, если ABx = Cx, и является алгоритмом

с односторонней ошибкой, т. е. ошибается только для случаев

неравенства — легко видеть, что если алгоритм сообщает, что

тождество не выполнено, то всегда AB 6= C.

При этом ABx вычисляется как A(Bx), что и обеспечивает

146 Глава 4. Вероятностные алгоритмы и их анализ

оценку сложности алгоритма O(n

Следующая теорема обеспечивает корректность алгоритма.

Теорема 4.1.1. Пусть A, B, и C — n × n матрицы, эле-

менты которых принадлежат некоторому полю F, причем

AB 6= C. Тогда для вектора x, выбранного случайно и равно-

мерно из {0, 1}

P {ABx = Cx} ≤ 1/2.

Доказательство. Пусть D = AB − C. Мы знаем, что D — не

полностью нулевая матрица и хотим оценить вероятность то-

го, что Dx = 0. Без ограничения общности можно считать,

что ненулевые элементы имеются в первой строке и они распо-

лагаются перед нулевыми. Пусть d — вектор, равный первой

строке матрицы D, и предположим, что первые k элементов

в d — ненулевые. Имеем

P{Dx = 0} ≤ P{d

x = 0}.

Но d

x = 0 тогда и только тогда, когда

−

i=2

Для каждого выбора x

, . . . , x

правая часть этого равен-

ства фиксирована и равна некоторому элементу v поля F.

Вероятность того, что x

равно v, не превосходит

, посколь-

ку x

равномерно распределено на двухэлементном множестве

{0, 1}, а вероятность события d

x = 0 либо равна

, если

правая часть принадлежит множеству {0, 1}, либо равна ну-

лю в противном случае.

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

ритмы традиционно успешно применяются, является задача

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

4.1. Вероятностная проверка тождеств 147

Задача 17. Проверить для заданного полинома P (x

, . . . , x

)

выполнение тождества P (x

, . . . , x

) ≡ 0.

Следующая лемма (см. [MR95]), по сути, описывает веро-

ятностный алгоритм Монте–Карло с односторонней ошибкой.

Лемма 4.1.2. Пусть Q(x

, . . . , x

) — многочлен от многих

переменных степени d над полем F и пусть S ⊆ F — про-

извольное подмножество. Если r

, . . . , r

выбраны случайно,

независимо и равномерно из S, то

P (Q(r

, . . . , r

) = 0 | Q(x

, . . . , x

) 6≡ 0) ≤

|S|

Доказательство. По индукции по n.

Базисный случай n = 1 включает полиномы от одной пе-

ременной Q(x

) степени d. Поскольку каждый такой полином

имеет не более d корней, вероятность того, что Q(r

) = 0 не

превосходит

|S|

Пусть теперь предположение индукции верно для всех по-

линомов, зависящих от не более n − 1 переменной.

Рассмотрим полином Q(x

, . . . , x

) и разложим его по пе-

ременной x

Q(x

, . . . , x

) =

i=0

, . . . , x

где k ≤ d — наибольшая степень x

в Q.

Предполагая, что Q зависит от x

, имеем k > 0, и коэф-

фициент при x

, Q

, . . . , x

) не равен тождественно нулю.

Рассмотрим две возможности.

Первая — Q

, . . . , r

) = 0. Заметим, что степень Q

не

превосходит d − k, и по предположению индукции вероятность

этого события не превосходит

(d−k)

|S|

148 Глава 4. Вероятностные алгоритмы и их анализ

Вторая — Q

, . . . , r

) 6= 0. Рассмотрим следующий по-

лином от одной переменной:

q(x

) = Q(x

, r

, . . . , r

) =

i=0

, . . . , r

Полином q(x

) имеет степень k и не равен тождественно

нулю, т.к. коэффициент при x

есть Q

, . . . , r

). Базовый

случай индукции дает, что вероятность события

q(r

) = Q(r

, r

, . . . , r

) = 0

не превосходит

|S|

Мы доказали два неравенства:

P{Q

, . . . , r

) = 0} ≤

d − k

|S|

;

P{Q(r

, r

, . . . , r

) = 0| Q

, . . . , r

) 6= 0} ≤

|S|

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

роятность события Q(r

, r

, . . . , r

) = 0 не превосходит суммы

двух вероятностей (d − k)/|S| и k/|S|, что дает в сумме желае-

мое d/|S|.

Упражнение 4.1.1. Покажите, что для любых двух собы-

тий E

, E

P{E

} ≤ P{E

| E

} + P{E

Упражнение 4.1.2. Имеется n × n матрица A, элементами

которой являются линейные функции f

(x) = a

x + b

Придумайте алгоритм Монте-Карло с односторонней ошиб-

кой для проверки этой матрицы на вырожденность (det A ≡ 0).

4.2. Вероятностные методы в перечислительных задачах 149

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

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

пределенные вычисления. Эффективным параллельным алго-

ритмом (или NC-алгоритмом) называется алгоритм, который

на многопроцессорной RAM (так называемой PRAM) с числом

процессоров, не превосходящим некоторого полинома от длины

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

логарифма длины входа.

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

ного алгоритма (NC-алгоритма) для нахождения максималь-

ного паросочетания в двудольном графе является одной из

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

мов. Удалось, однако, построить эффективный параллельный

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

сочетания в двудольном графе (так называемый RNC-алго-

ритм) [MR95]. Примеры применения вероятностных алгорит-

мов для построения эффективных параллельных и распреде-

ленных алгоритмов рассматриваются в разделе 4.3.

4.2. Вероятностные методы

в перечислительных задачах

В данном разделе мы рассмотрим перечислительные задачи

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

для решения таких задач.

Алгоритм для решения перечислительной задачи получает

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

(например, граф) и в качестве выхода выдает неотрицательное

целое, являющееся числом решений задачи (например, число

гамильтоновых циклов в графе или число совершенных паро-

сочетаний).

Пусть Z — некоторая перечислительная задача, I — вход

задачи. Пусть далее #(I) обозначает число различных решений

для входа I задачи Z.

150 Глава 4. Вероятностные алгоритмы и их анализ

Определение 4.2.1. Пусть

Z — перечислительная задача.

I — вход для Z, n = |I|.

#(I) — число различных решений для входа I задачи Z.

ε > 0 — параметр точности.

Вероятностный алгоритм A(I, ε) — полиномиальная

рандомизированная аппроксимационная схема, если

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

P[(1 − ε)#(I) ≤ A(I, ε) ≤ (1 + ε)#(I)] ≥

Определение 4.2.2. Полностью полиномиальной ран-

домизированной аппроксимационной схемой (FPRAS)

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

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

от n и 1/ε.

Определение 4.2.3. Полностью полиномиальной ран-

домизированной аппроксимационной схемой с пара-

метрами (ε, δ) (или кратко (ε, δ)-FPRAS) для перечисли-

тельной задачи Z называется полностью полиномиальная

рандомизированная аппроксимационная схема, которая на

каждом входе I вычисляет ε-аппроксимацию для #(I) с веро-

ятностью не менее 1 − δ за время, полиномиальное от n, 1/ε

и log 1/δ.

Рассмотрим теперь одну перечислительную задачу.