Анализ сложности в среднем. Вероятностные алгоритмы

МИНИСТЕРСТВО ОБРАЗОВАНИЯ  И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ  БЮДЖЕТНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО  ОБРАЗОВАНИЯ

«ЛИПЕЦКИЙ ГОСУДАРСТВЕННЫЙ  ПЕДАГОГИЧЕСКИЙ  
УНИВЕРСИТЕТ»

ФАКУЛЬТЕТ ИНФОРМЦИОННЫХ  И СОЦИАЛЬНЫХ ТЕХНОЛОГИЙ

КАФЕДРА  ИНФОРМАТИКИ

 

 

 

Реферат

На тему: “Анализ сложности в среднем. Вероятностные алгоритмы”

 

 

 

 

Выполнила:

Студентка 3 курса  группы И-10-1

Бирюкова А.Р.

Проверила:

Карлова М.Ю.

 

 

Липецк 2013

 

 

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

 

Среди подходов к решению NP-трудных задач можно выделить два. Первый заключается в построении приближенных алгоритмов с гарантированными оценками точности получаемого решения, а второй — в отказе от анализа сложности алгоритмов по наихудшему случаю и переходе к анализу сложности в среднем.

Настоящая лекция посвящена  изучению второго подхода (анализу  сложности в среднем) применительно к задаче упаковки.

 

При анализе сложности  в среднем вводится некоторая  вероятностная мера на

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

Рассмотрим этот подход на примере задачи об упаковке.

 

Задача 13 ЗАДАЧА ОБ УПАКОВКЕ Дано конечное множество L из m элементов и система его подмножеств S1, . . . , Sn. Требуется найти максимальную по числу подмножеств подсистему попарно непересекающихся подмножеств.

Эта задача эквивалентна следующей 0−1 целочисленной линейной программе:

 

                                                                                                                                                        

   

 

(3.1)

 

В этой целочисленной  линейной программе n столбцов-переменных x₁,….,x_nсоответствуют подмножествам S₁,...,S_n и их включению в решение. (0,1)-матрица A (размера m x n) описывает состав каждого подмножества (или принадлежность каждого из m предметов, заданным n подмножествам). Проще говоря, матрица A является матрицей инцидентности семейства S₁,...,S_n подмножеств множества L.

Напомним определения:

 

Определение 32 Элемент l_i и подмножество S_i инцидентны, если l_i є S

 

Определение 33 Матрицей инцидентности для семейства S₁,...,S_n подмножеств множества L называется (0,1)-матрица A = (a_ij) размером m x n, построенная по следующему правилу: a_ij = 1 в том и только в том случае, когда элемент l_i є L и подмножество S_i инцидентны.

Это позволяет при  изучении задач о покрытии/упаковке пользоваться как терминологией подмножеств конечного множества, так и вести рассмотрения в терминах (0, 1)-матриц.

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

 

В литературе задача с ЦЛП постановкой 3.1, также встречается под

названием УПАКОВКА ПОДМНОЖЕСТВ.

 

Очевидно, вектор (0,... ,0) является допустимым в 3.1. Предположим, что все элементы a_ij матрицы ограничений из 3.1 являются независимыми случайными величинами, принимающими значения {0, 1}, причем для всех i, j выполнено

 

P {a_ij = 1} = p, P{a_ij = 0} = 1 − p.

 

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

 

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

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

Теорема 15 Пусть выполнено условие

 

mp²≥ ln n       (3.2)

 

Тогда имеется модификация  метода динамического программирования для задачи (13), являющаяся полиномиальным в среднем алгоритмом.

 

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

Обозначим через T(k) множество всех допустимых булевых векторов для системы (3.1) с n−k нулевыми последними компонентами и через e_k - вектор размерности n с единичной k-й компонентой и остальными нулевыми компонентами. Рассмотрим алгоритм 18.

 

Нетрудно убедиться, что сложность  алгоритма В есть O(mn|T(n)|). Действительно - внешний цикл O(n), внутренний O(|T (n)|), проверка на допустимость нового решения - O(m) (если непонятно, обязательно подумайте почему).

Математическое ожидание времени работы алгоритма ( O(nmE|T (n)|). Поэтому для доказательства теоремы 15 достаточно будет оценить сверху математическое ожидание размера множества T(n).

Вероятность P(k) того, что некоторый вектор x^k с k единичными компонентами и n −k нулевыми компонентами является допустимым решением (3.1) (то есть удовлетворяет всем ограничениям в (3.1)) можно оценить сверху следующим образом:

 

 

 

 

где p_i(k) - вероятность выполнения i-неравенства для x^k:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

откуда (при k > 1)

Следовательно, мы можем оценить  математическое ожидание мощности T(n) следующим образом

При условии mp² > lnn в последней сумме каждый член не превосходит 1. Это и означает, что E|T(n)| = O(n²).

В заключение отметим, что из полученных результатов вытекает не только полиномиальный в среднем алгоритм для задачи оптимизации (3.1), но и полиномиальный в среднем алгоритм для, вообще говоря, более трудной задачи подсчета числа целых точек в многограннике (3.1).

 

 

Вероятностные алгоритмы (Лас-Вегас и Монте-Карло).

 

Вероятностный алгоритм -  это, неформально, алгоритм, исполнение которого (и, соответственно, результат) зависит от случайных величин (или, как часто говорят, от результатов "подбрасывания монеты").

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

На формальном уровне вероятностный  алгоритм " это некоторая вероятностная машина Тьюринга.

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

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

По аналогии с детерминированными алгоритмами, где эффективные алгоритмы отождествляются с так называемыми полиномиальными алгоритмами, а класс языков (предикатов) распознаваемых в полиномиальное время обозначается P, предикаты распознаваемые эффективным вероятностными алгоритмами образуют классы BP P и RP для Монте-Карло алгоритмов (соответственно, с двусторонними и односторонними ошибками) и ZPP для Лас-Вегас алгоритмов.

 

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

 

Определение 35 Предикат L принадлежит классу BPP, если существуют та-

кие вероятностная машина Тьюринга M и полином p(n), что машина M на входе

x остановится за время, не превосходящее p(|x|), причем

 

1. L(x) = 1 ⇒ M с вероятностью большей 2/3 дает ответ "да"

2. L(x) = 0 ⇒ M с вероятностью большей 2/3 дает ответ "нет"

 

Предикаты из класса BPP можно считать реально вычислимыми, т.к. вероятностные машины вполне могут рассматриваться как реальные устройства. В этом

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

Другое (эквивалентное) определение  класса BPP не использует понятие вероятностной машины Тьюринга.

Определение 36 Предикат L принадлежит классу BPP, если существуют та-

кие предикат R(x,y) є P и  полином p(n), что |y| ≤ p(|x|), и

 

1. L(x) = 1 → доля строк  y, для которых R(x,y) = 1, больше 2/3

2. L(x) = 0 → доля строк  y, для которых R(x,y) = 0, больше 2/3

 

Нетрудно доказать, что  если в определении класса BPP число 2/3 заменить на любое фиксированное число, большее 1/2, то класс BP P не изменится. Следует отметить также, что сделав достаточное число запусков данного вероятностного алгоритма с одними и теми же исходными данными, можно добиться сколь угодно малой вероятности ошибки выбрав ответ (1 или 0), который дало большинство.

 

Аналогично определяется класс RP.

 

Определение 37 Предикат L принадлежит классу RP, если существуют такие

предикат R(x,y) є P и полином p(n), что |y| ≤ p(|x|), и

 

1. L(x) = 1 → доля строк y, для которых R(x,y) = 1 больше 1/2

2. L(x) = 0 → доля строк  y, для которых R(x,y) = 0 равна 1

 

Класс ZPP определяется так:

 

Определение 38 ZPP = RP ∩ co − RP , где co − RP = {L| L є RP }.

 

Один из первых примеров вероятностных алгоритмов, более эффективных чем детерминированные, был предложен Фрейвалдом для задачи проверки матричного равенства AB = C. Обычный детерминированный алгоритм заключается в перемножении матриц A и B и сравнении результата с C.

Сложность такого алгоритма  есть O(n³) при использовании стандартного алгоритма умножения матриц размера n x n, и O(n^2.376) при использовании лучшего из известных быстрых алгоритмов матричного умножения.

Вероятностный алгоритм Фрейвалда для этой задачи имеет  сложность O(n²) и заключается в умножении левой и правой частей на случайный булев вектор x = (x₁, ...,x_n) с последующим сравнением полученных векторов. Алгоритм выдает ответ, что AB = C, если ABx = Cx и является алгоритмом типа Монте-Карло с односторонней ошибкой. При этом ABx вычисляется как A(Bx), что и обеспечивает оценку сложности алгоритма O(n²).

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

 

Теорема 17 Пусть A, B, и C n x n матрицы над полем F², причем AB ≠ C. Тогда для случайного вектора x выбранного случайно и равномерно из {0,1}ⁿ,

 

P{ABx = Cx} ≤ 1/2.

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

матрица и хотим оценить вероятность того, что Dx = 0. Без ограничения общности можно считать, что ненулевые элементы имеются в первой строке и они располагаются перед нулевыми. Пусть d - вектор, равный первой строке матрицы D, и предположим, что первые k элементов в d - ненулевые.

 

P{Dx = 0} ≤ P{d^Tx = 0}.

 

Но, d^Tx = 0 тогда и только тогда, когда 

 

 

 

 

            Для каждого выбора x₂,...,x_k правая часть этого равенства фиксирована и равна некоторому v > 0. Вероятность, что x₁ равно v, не превосходит 1/2, поскольку x₁ равномерно распределено на двухэлементном множестве ({0, 1}).

            Классическим примером задачи, где вероятностные алгоритмы успешно применяются, является задача проверки тождеств для многочлена от многих переменных:

 

Задача 14 Верно ли для заданного полинома P(x₁,.. .,x_n), что P(x₁,.. .,x_n) ≡ 0?

Следующая лемма по сути описывает вероятностный Монте-Карло  алгоритм с односторонней ошибкой.

Лемма 2 Пусть Q(x₁, ..., x_n) - многочлен от многих переменных степени d над

полем F и пусть S є F произвольное подмножество. Если r¹,...,rⁿ выбраны

случайно, независимо и равномерно из S, то

 

 

 

 

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

 

             Базисный случай n = 1 включает полиномы от одной переменной Q(x₁) степени

d. Поскольку каждый такой полином имеет не более d корней, вероятность, что

Q(r₁) = 0 не превосходит d/|S|.

       Пусть теперь предположение индукции верно для всех полиномов, зависящих от не более n − 1 переменной.

Рассмотрим полином Q(x₁,.. .,x_n) и разложим его по переменной x₁

 

 

 

где k ≤ d наибольшая степень x₁ в Q.

             Предполагая, что Q зависит от x₁, имеем k > 0, и коэффициент при x^k₁ ,

Q_k(x₂,...,x_n) не равен тождественно нулю. Рассмотрим две возможности.

             Первая - Q_k(r₂,. ..,r_n) = 0. Заметим, что степень Q_k не превосходит d − k, и

по предположению индукции вероятность  этого события не превосходит 

 

             Вторая - Q_k(r₂,.. .,r_n) ≠ 0

Рассмотрим следующий  полином от одной переменной:

 

 

 

             Полином q(x₁) имеет степень k, и не равен тождественно нулю, поскольку коэффициент при x^k₁ есть Q_k(r₂,...,r_n). Базовый случай индукции дает, что вероятность события q(r₁) = Q(r₁,r₂,...,r_n) = 0 не превосходит

 

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