Рандомизированный аппроксимирующий алгоритм для задачи MAX 3-SAT - Рандомизированные алгоритмы

В предыдущем разделе были представлены некоторые способы использования линейности ожидания для анализа рандомизированного процесса. Посмотрим, как применить эту идею при разработке аппроксимирующего алгоритма. Задача будет рассматриваться на примере задачи 3-SAT; вы увидите, что одним из следствий рандомизированного аппроксимирующего алгоритма является неожиданно сильное общее утверждение по поводу 3-SAT, которое на первый взгляд не имеет никакого отношения ни к алгоритмам, ни к рандомизации.

Задача

При изучении NР-полноты одной из основных задач была задача 3-SAT: для заданного множества условий C₁, ..., C_k, каждое из которых имеет длину 3, по множеству переменных X = {х₁, ..., x_n}, существует ли выполняющее логическое присваивание?

Например, такая задача может встретиться в системе для проверки истинности или ложности системы утверждений об окружающем мире (переменные {x_i}) по нескольким условиям, связывающим их друг с другом (условия {C_j}). Но окружающий мир — весьма противоречивое место, и если наша система накопит достаточно информации, множество условий может не иметь выполняющих присваиваний. И что тогда?

Если найти логическое присваивание, выполняющее все условия, не удается, будет естественно преобразовать экземпляр 3-SAT в задачу оптимизации: для заданного множества входных условий C₁, ..., C_k найти логическое присваивание, выполняющее как можно больше условий. Назовем эту задачу максимальной задачей3-SAT (или сокращенно MAX 3-SAT). Конечно, это NР-сложная задача оптимизации, так как принятие решения о том, равно ли максимальное количество одновременно выполняемых условий k, является NР-сложным. Посмотрим, что можно сказать об аппроксимирующих алгоритмах с полиномиальным временем.

Разработка и анализ алгоритма

Неожиданно простой рандомизированный алгоритм дает сильные гарантии эффективности для этой задачи. Допустим, каждой переменной х₁, ..., х_n независимо присваивается 0 или 1 (каждое значение имеет вероятность 1/2). Какое ожидаемое число условий будет выполнено таким случайным присваиванием?

Обозначим Z случайную переменную, равную количеству выполненных условий. Как и в разделе 13.3, разложим Z на сумму случайных переменных, каждая из которых принимает значение 0 или 1, а именно Z_i = 1, если условие C_i выполнено, или 0 в противном случае. Следовательно, Z = Z₁ + Z₂ + ... + Z_k. Теперь значение E[Z_i] равно вероятности того, что условие C_i выполнено, а эта вероятность легко вычисляется: чтобы условие C_i не было выполнено, каждой из его трех переменных должно быть присвоено значение, которое мешает его истинности; так как переменные присваиваются независимо, вероятность равна Следовательно, условие С_i выполняется с вероятностью и

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

(13.14) Возьмем формулу 3-SAT, в которой каждое условие содержит три разные переменные. Ожидаемое количество условий, выполненных случайным присваиванием, лежит в пределах множителя 7/8 от оптимума.

Но если разобраться, что же в действительности произошло в этом (откровенно говоря, простом) анализе случайного присваивания, становится ясно, что можно привести и более сильное утверждение. Для любой случайной переменной должна существовать некоторая точка, в которой она принимает значение, по крайней мере большее своего ожидания. Мы показали, что для любого экземпляра 3-SAT случайное логическое присваивание в ожидании выполняет 7/8 всех условий; следовательно, должно существовать логическое присваивание, выполняющее количество условий, по крайней мере не меньшее ожидания.

(13.15) Для каждого экземпляра 3-SAT существует логическое присваивание, выполняющее по крайней мере 7/8 всех условий.

В утверждении (13.15) есть нечто по-настоящему удивительное. Мы прибыли к неочевидному факту, касающемуся 3-SAT, — существованию присваивания, выполняющего много условий, — в формулировке которого нет ничего связанного с рандомизацией; тем не менее мы пришли к нему посредством рандомизированного построения. Кроме того, рандомизированное построение предоставляет, пожалуй, простейшее доказательство (13.15). Этот принцип довольно часто встречается в комбинаторике: чтобы продемонстрировать возможность существования некоторой структуры, мы показываете, что случайное построение приводит к ней с положительной вероятностью. Подобные построения создаются в результате применения вероятностного метода.

Любопытное, хотя и второстепенное следствие (13.15): каждый экземпляр 3-SAT, содержащий не более 7 условий, является выполнимым. Почему? Если экземпляр содержит k ≤ 7 условий, то из (13.15) следует, что существует присваивание, выполняющее не менее 7/8k из них. Но если k ≤ 7, то 7/8k > k - 1; а поскольку количество условий, выполняемых присваиванием. должно быть целым, оно должно быть равно k, иначе говоря, выполняются все условия.

Дальнейший анализ: поиск хорошего присваивания

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

Простейшее решение заключается в генерировании случайных логических присваивании до тех пор, пока одно из них не выполнит по крайней мере 7/8k условий. Из (13.15) известно, что такое присваивание существует; но сколько времени потребуется для того, чтобы найти его методом случайных испытаний?

Здесь будет естественно применить границу времени ожидания, полученную в (13.7). Если мы сможем показать, что вероятность того, что случайное присваивание удовлетворяет по крайней мере 7/8k условий, не менее р, то ожидаемое количество испытаний, выполняемых алгоритмом, составляет 1/р. Итак, нам хотелось бы показать, что величинаp по крайней мере не более чем обратно-полиномиальна по n и k.

Для j = 0, 1, 2, ..., k пусть р обозначает вероятность того, что случайное присваивание выполняет ровно j условий. Следовательно, ожидаемое количество выполненных условий по определению ожидания составляет из предшествующего анализа оно равно 7/8k. Нас интересует величина Как использовать нижнюю границу ожидаемого количества для получения нижней границы этой величины?

Начнем с равенства

Обозначим k' наибольшее натуральное число, строго меньшее 7/8k. Если заменить слагаемые в первой сумме на k'p_j, а слагаемые во второй сумме на kp_j, правая сторона приведенного равенства только возрастает. Также заметим, что а следовательно,

Отсюда Но так как k' — натуральное число, строго меньшее 7/8 другого натурального числа, а следовательно,

Мы получили желаемое — нижнюю границу для р. С учетом границы времени ожидания (13.7) мы видим, что ожидаемое число испытаний, необходимых для нахождения выполняющего присваивания, не превышает 8k.

(13.16) Существует рандомизированный алгоритм с полиномиальным ожиданием времени выполнения, который гарантированно выдает логическое присваивание, выполняющее по крайней мере 7/8 всех условии.