Рис. 3.5: Карта-памятка раздела 3.3.0

3.4Точность алгоритма для почти всех входов

Хотя человека, использующего жадный алгоритм, можно заставить сильно ошибиться при принятии сложных решений (например, при решении NP-трудных задач), в типичном случае он обычно выигрывает. Этот почти философский тезис будет нами проиллюстрирован на примере жадного алгоритма для задачи о покрытии.

В данном разделе мы рассмотрим некоторое ослабление анализа сложности в среднем. Это ослабление происходит в двух направлениях: во-первых, мы рассматриваем не только точные алгоритмы, но и приближенные, а во-вторых, анализ сложности в среднем заменяется на анализ для «почти всех» исходных данных.

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

лее чем в логарифмическое число раз (по m). Наша цель сейчас — показать, что для «типичных» данных (в отличие от худшего случая, см. упражнение 2.1.2) это отношение близко к единице, т. е. размер покрытия, найденного жадным алгоритмом, почти равен размеру минимального покрытия.

Как и в предыдущем разделе, мы будем использовать формулировку задачи о покрытии на языке (0; 1)-матриц и целочисленных линейных программ:

В этой целочисленной линейной программе n столбцов-переменных x1; : : : ; xn соответствуют подмножествам S1; : : : ; Sn и их включению в решение-покрытие. Матрица A также является матрицей инцидентности, а векторы стоимости и ограничений — также векторы размерности n и m соответственно, состоящие полностью из единиц.

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

Как и в разделе 3.2, предположим, что A = (aij) — случайная (0,1)-матрица, такая, что для всех i; j выполнено

P faij = 1g = p; P faij = 0g = 1 p:

Пусть RG = ZMG , где ZG — величина покрытия, найденного жадным алгоритмом, а M — величина минимального покрытия. Наш основной результат заключается в следующей теореме.

Теорема 11. Пусть вероятность 0 < p < 1 фиксирована, и пусть для задачи (3.5) со случайной матрицей A, определенной выше, выполнены следующие условия:

Тогда для любого фиксированного " > 0

PfRG 1 + "g ! 1 при n ! 1:

Заметим, что условия теоремы требуют, чтобы матрица A не была «экспоненциально вытянутой» по высоте или ширине. В частности, для «пропорциональных» матриц, у которых m = cn, где c — некоторая константа, и «несильно перекошенных матриц», у которых m = O(nc), условия (3.6) и (3.7) теоремы 11 выполнены автоматически.

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

l0 = l0( ) = (1 ) ln m/ ln(1 p) ;

тогда ( )

n

E X = l0 P (l0);

Лемма 8. Пусть Y — сумма n независимых случайных величин, каждая из которых принимает значение 1 с вероятностью p и 0 с вероятностью 1 p. Тогда

PfjY npj > npg 2 expf ( 2/3)npg:

По этой лемме вероятность того, что некоторая фиксированная строка содержит менее чем (1 )pn единиц (или более чем (1 + )pn единиц) оценивается сверху так:

Pbad 2 expf ( 2/3)npg;

и математическое ожидание числа таких строк не превосходит mPbad. Тогда при n ! 1, по условию (3.7) получаем

mPbad 2 expfln m ( 2/3)npg = 2 expfln m O(1)ng ! 0:

Из P fX 1g E X — первого неравенства Чебышева следует, что вероятность события «каждая строка содержит не менее (1 )pn единиц» стремится к 1.

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

Пусть Nt — число непокрытых строк после t-го шага жадного алгоритма. Подсчитывая нижнюю оценку числа единиц в подматрице, образованной непокрытыми строками (Nt 1), и делая вывод о существовании столбца в этой подматрице с числом единиц не менее среднего, имеем:

N0 (1 (1 )p)t = m(1 (1 )p)t:

144 Глава 3. ВЕРОЯТНОСТНЫЙ АНАЛИЗ ДЕТЕРМИНИРОВАННЫХ АЛГОРИТМОВ

Первое неравенство получается оценкой снизу суммарного числа единиц в подматрице из Nt 1 непо-

Отсюда получается верхняя оценка мощности «жадного покрытия» (ZG = t + 1) в типичном случае:

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