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

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

2.2. Аппроксимация с заданной точностью 111

Алгоритм 27. PTAS для рюкзака

def KnapsackFPTAS (D, B, epsilon, LowerBound):

Вычисляем нижнюю оценку стоимости

F_lb ← LowerBound (copy (D), B)

параметр округления scale

scale ← epsilon ∗ F_lb/len (D)/(1 + epsilon)

Набор c округленными стоимостями

Ds ← [(int (ﬂoor (c/scale)), a) for c, a ∈ D]

knapset ← KnapsackDynpLightest (Ds, B)

ApproxCost ← 0

for i ∈ knapset :

ApproxCost ← ApproxCost + D[i][0]

D = [(134, 16), (789, 250), (56, 43), (345, 333), (4567, 857), (555, 47)]

B = 1000

Optimal Knapsack: [0, 2, 4, 5] costs 5312

LowerBound= <function MaxItemCost at 0x00AA8470> => F_lb= 4567

eps = 0.1 => scale = 69.196969697

Ds = [(1, 16), (11, 250), (0, 43), (4, 333), (66, 857), (8, 47)]

Approx. knapsack: [0, 4, 5] costs 5256

LowerBound= <function KnapsackGreedy at 0x00AA83F0> => F_lb= 5312

eps = 0.1 => scale = 80.4848484848

Ds = [(1, 16), (9, 250), (0, 43), (4, 333), (56, 857), (6, 47)]

Approx. knapsack: [0, 4, 5] costs 5256

LowerBound= <function KnapsackGreedy at 0x00AA83F0> => F_lb= 5312

eps = 0.06 => scale = 50.1132075472

Ds = [(2, 16), (15, 250), (1, 43), (6, 333), (91, 857), (11, 47)]

Approx. knapsack: [0, 2, 4, 5] costs 5312

Глава 3

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

3.1. Сложность и полиномиальность в сред-

нем

Среди подходов к решению N P-трудных задач можно выде-

лить два основных. Первый заключается в построении прибли-

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

получаемого решения (этот подход уже был рассмотрен нами

в главе 2), а второй — в отказе от анализа сложности алгорит-

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

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

хода (анализу сложности в среднем).

Известно, что большинство задач дискретной оптимизации

является N P-трудным, и для них существование полиномиаль-

ных алгоритмов маловероятно. Несмотря на это, для многих

исходных данных (входов) такие задачи бывают легко разре-

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

жет заключаться в небольшом подмножестве входов. Проблема

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

ки эффективности алгоритмов и в то же время играет замет-

ную роль в математической криптографии. Концепция слож-

ности в среднем для таких задач представляется более адек-

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

3.1. Сложность и полиномиальность в среднем 113

Имеется еще одно соображение в пользу перехода от ана-

лиза по худшему случаю к анализу сложности в среднем. Оно

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

ритмы не являются эффективными при анализе по худшему

случаю. Пожалуй, наиболее известным примером такого алго-

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

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

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

нии практических задач.

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

ния в определении эффективности привели к понятию слож-

ности в среднем (average case complexity), под которым, грубо

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

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

исходных данных. С середины 80-х годов начала развиваться

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

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

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

полиномиальные в среднем алгоритмы. Однако достигнутые

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

сложности при анализе по худшему случаю.

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

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

ничений, введено новое понятие «сглаженной сложности»

(smoothed complexity) и доказано, что некоторые варианты

симплекс-метода имеют полиномиальную сглаженную слож-

ность. Построены приближенные полиномиальные в среднем

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

тируемыми оценками точности, существенно лучшими анало-

гичных оценок для худшего случая.

Перейдем к конкретизации сказанного выше. Пусть для

данного алгоритма A время его работы на входе I обознача-

ется через T

(I). Пусть также для каждого натурального n

задано распределение вероятностей на входах I длины n, обо-

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

значаемое P

(I). Поскольку T является случайной величиной,

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

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

ритма E

на входах длины n.

Определение 3.1.1. «Полиномиальный в среднем (точно)»

Алгоритм A называется полиномиальным в среднем,

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

ны входа, т. е.

∃C > 0 : E

= O(n

Однако в теоретических работах, касающихся теории сво-

димости и сложности в среднем, полиномиальность в среднем

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

приведенное выше определение слишком чувствительно: изме-

нение T на T

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

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

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

не является полиномиальным в среднем на машине Тьюринга.

Упражнение 3.1.1. Приведите пример функции T

(време-

ни работы некоторого алгоритма A) и распределения исход-

ных данных P

(I), для которых T

является полиномиальной

в среднем (E

= O(n

)), а T

— нет.

Эту ситуацию нельзя признать удовлетворительной, по-

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

ности по худшему случаю: определение полиномиального ал-

горитма не зависит от выбранной модели вычислений.

Поэтому в теоретических работах, касающихся теории сво-

димости и сложности в среднем, используют обычно другое

определение.

Определение 3.1.2. «Полиномиальный в среднем»

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

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

∃ε > 0 : E

= O(n).

3.2. Задача упаковки 115

Тем не менее, в исследовании сложности в среднем конкрет-

ных алгоритмов обычно используется определение 3.1.1 «По-

линомиальный в среднем (точно)» с указанием конкретной вы-

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

это машины с произвольным доступом к памяти — RAM). Мы

в следующих разделах также будем следовать этому определе-

нию.

3.2. Задача упаковки

Алгоритм динамического программирова-

ния для задачи упаковки подмножеств.

Полиномиальность алгоритма «в среднем».

Задача 15. «Упаковка» (Packing)

Дано конечное множество L из m элементов и система

его подмножеств S

, . . . , S

. Требуется найти максималь-

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

щихся подмножеств.

При реализации и анализе алгоритмов гораздо удобней

формализовать представление отношений между элементами

и подмножествами в виде матрицы инцидентности.

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

L = {l

, . . . , l

} — m-элементное множество;

, . . . , S

} — семейство подмножеств L;

Тогда

• Элемент l

и подмножество S

инцидентны, если

∈ S

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

• Матрицей инцидентности называется {0,1}-матрица

A = (a

) размером m × n, для которой:

= 1 ⇔ элемент l

и подмножество S

инцидентны.

Таким образом, задача 15 «Packing» будет эквивалентна

следующей 0–1 целочисленной линейной программе:

j=1

→ max,

∈ {0, 1} ∀j : 1 ≤ j ≤ n,

j=1

≤ 1 ∀i : 1 ≤ i ≤ m.

(3.1)

В этой целочисленной линейной программе n столбцов и пе-

ременных x

, . . . , x

соответствуют подмножествам S

, . . . , S

и их включению в решение, а 0–1-матрица инцидентности

A = (a

) размера m × n описывает состав каждого подмно-

жества (см. определение 3.2.1 «Инцидентность»). Таким об-

разом, m строк-ограничений, соответствующих m предметам,

очевидным образом выражают ограничение на попарную непе-

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

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

Заметим, что в литературе «Упаковкой подмножеств» на-

зывается иногда и более общая постановка ЦЛП, где c

, . . . , c

и b

, . . . , b

— произвольные положительные целые числа:

j=1

→ max,

∀j : 1 ≤ j ≤ n x

∈ {0, 1},

∀i : 1 ≤ i ≤ m

j=1

≤ b

3.2. Задача упаковки 117

Известно, что задача 15 «Packing» NP-полна [Joh90].

Тривиальный метод решения задачи 15 «Packing» — пол-

ный перебор всех N = 2

наборов подмножеств с проверкой

на совместность и выбором набора, содержащего наибольшее

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

Более перспективный подход — ограничить перебор по до-

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

программирования.

Обозначим через X

множество всех допустимых булевых

векторов для системы с n − j нулевыми последними компонен-

тами и через e

— вектор размерности n с единичной j-й ком-

понентой и остальными нулевыми компонентами. Тогда можно

строить множество допустимых решений X

на основе множе-

ства X

j−1

, пытаясь добавить вектор e

ко всем допустимым

решениям из X

j−1

. Более формально это описано в алгорит-

ме 28 «Упаковка-ДинПрог».

Нетрудно убедиться, что сложность алгоритма 28 «Упа-

ковка-ДинПрог» составляет O((m + n)n|X

|). Действительно,

внешний цикл — O(n), внутренний — O(|X

|), проверка на до-

пустимость и добавление нового решения — O(m + n).

Упражнение 3.2.1. Укажите, как надо организовать вычис-

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

сложность O(m).

Таким образом, сложность алгоритма существенно зависит

от размера множества допустимых решений, возникающих при

выполнении алгоритма.

Упражнение 3.2.2. Какие входные данные для алгорит-

ма 28 «Упаковка-ДинПрог» заставят его работать экспоненци-

ально долго? А какие — за O(n

Но можно показать, что алгоритм 28 «Упаковка-ДинПрог»

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

, т. е. работать эффек-

Причем в более строгом варианте, в смысле определения 3.1.1 «Поли-

номиальный в среднем (точно)».

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

Алгоритм 28. «Упаковка»: динамическое программирование

def PackingDynP (A) :

(m, n) ← A.shape

X ← [(

zeros (n, int), # решение

zeros (m, int), # покрытие

0 # размер покрытия

)]

for j ∈ xrange (n) :

Sj ← getColumn (j)

for sol, cov, size ∈ X[: ] :

newcov ← cov + Sj

if max (newcov) ≤ 1 :

newsol ← copy (sol)

newsol[j] ← 1

X.append ((

newsol,

newcov,

size + 1))

return getOptimalSet (X)

Работа алгоритма показана на рис. 3.2.

тивно на случайных входных данных.

Теорема 3.2.1. Пусть a

в (3.1) являются независимы-

ми случайными величинами, принимающими значения {0, 1},

причем выполняется:

P{a

= 1} = p,

P{a

= 0} = 1 − p,

≥ ln n.

(3.2)

3.2. Задача упаковки 119

[[0 1 0 1]

[1 0 1 0]

[0 1 1 0]] --> 3x4-matrix A

column(0)+< [0 0 0 0], [0 0 0]>

=> [0 1 0]+[0 0 0]=[0 1 0] => [1 0 0 0]

column(1)+< [0 0 0 0], [0 0 0]>

=> [1 0 1]+[0 0 0]=[1 0 1] => [0 1 0 0]

column(1)+< [1 0 0 0], [0 1 0]>

=> [1 0 1]+[0 1 0]=[1 1 1] => [1 1 0 0]

column(2)+< [0 0 0 0], [0 0 0]>

=> [0 1 1]+[0 0 0]=[0 1 1] => [0 0 1 0]

column(3)+< [0 0 0 0], [0 0 0]>

=> [1 0 0]+[0 0 0]=[1 0 0] => [0 0 0 1]

column(3)+< [1 0 0 0], [0 1 0]>

=> [1 0 0]+[0 1 0]=[1 1 0] => [1 0 0 1]

column(3)+< [0 0 1 0], [0 1 1]>

=> [1 0 0]+[0 1 1]=[1 1 1] => [0 0 1 1]

Выбран набор [1 1 0 0] размером 2

Рис. 3.1. Работа алгоритма 28 «Упаковка-ДинПрог»

Тогда алгоритм 28 «Упаковка-ДинПрог» является полино-

миальным в среднем.

Доказательство. Математическое ожидание времени работы

алгоритма есть O(nm E |X

|). Поэтому для доказательства тео-

ремы 3.2.1 достаточно будет оценить сверху математическое

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

. Пусть k > 0,

— вектор с k единицами (на позициях {j

, . . . , j

}) и n − k

нулями;

— вероятность выполнения i-го неравенства для

;

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

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

— допустимое решение.

Упражнение 3.2.3. Чему будет равны x

, p

и P

при k = 0?

Сначала оценим сверху p

≡ P







j=1

(k)

≤ 1







= P







j∈{j

, ...,j

}

≤ 1







= P







j∈{j

, ...,j

}

= 0







+ P







j∈{j

, ...,j

}

= 1







= (1 − p)

+ kp(1 − p)

k−1

= (1 − p)

k−1

(1 + p(k − 1)) ≤

≤ (1 − p)

k−1

(1 + p)

k−1

= (1 − p

)

k−1

≤ e

−p

(k−1)

Теперь оценим собственно вероятность попадания x

в до-

пустимые решения:

i=1

≤

i=1

−p

(k−1)

= e

−mp

(k−1)

Упражнение 3.2.4. Докажите, что E |X

| =

k=0





Следовательно, мы можем оценить математическое ожида-

ние мощности X

следующим образом:

E |X

| =

k=0





= 1 +

k=1





≤ 1 + n +

k=2





< 1 + n +

k=2

−mp

(k−1)

≤ 1 + n +

k=2

k ln n−mp

(k−1)

= 1 + n + n

k=2

(k−1)(ln n−mp

)

При условии mp

≥ ln n в последней сумме каждый член не

превосходит 1. Это и означает, что E[X

] = O(n