В информатике и исследовании операций многие задачи комбинаторной оптимизации вычислительно неподатливы для решения задачи точно (т.е. для получения оптимального решения).
Многие такие задачи допускают быстрые (полиномиального времени) аппроксимационные алгоритмы — алгоритмы, гарантированное возвращающие приближённое к оптимальному решение для любого входа.
Вероятностное округление — это широко используемый подход для разработки и анализа таких аппроксимационных алгоритмов. Базовая идея — использование вероятностного метода для преобразования соответствующей оптимального решения задачи линейного программирования (ЛП) в приближённое к оптимальному решению исходной задачи.
Обзор Базовый подход имеет три шага: Формулируем задачу как задачу целочисленного линейного программирования (ЦЛП). Вычисляем оптимальное дробное решение задачи линейного программирования (без условия целочисленности). Округляем дробное решение задачи линейного программирования до решения целочисленной задачи ЛП.
(Хотя подход, в основном, использует линейное программирование, могут быть использованы и другие виды ослабления условий. Например, алгоритм Гоемана и Уильямсона использует приближённый алгоритм максимального разреза полуопределённого программирования.)
Целью первого шага является выбор подходящей постановки задачи целочисленного линейного программирования. Для этого требуется хорошее знание линейного программирования, и, в частности, понимание, как моделировать задачи с помощью линейного программирования и целочисленного линейного программирования. Однако для многих задач существует хорошо работающая естественная целочисленная задача линейного программирования, что показано в примере с задачей покрытия множества. (Целочисленная задача линейного программирования должна иметь небольшой зазор целочисленности. Более того, вероятностное округление часто используется для доказательства зазоров целочисленности.)
На втором шаге оптимальное дробное решение, обычно, может быть вычислено за полиномиального времени с помощью стандартного алгоритма линейного программирования.
На третьем шаге дробное решение должно быть преобразовано в целочисленное решение (и тем самым в решение исходной задачи). Этот процесс называется округлением дробного решения. Конечное целочисленное решение должно (доказуемо) иметь цену, не отличающуюся сильно от цены дробного решения. Тем самым обеспечивается, что цена целочисленного решения не намного больше цены оптимального целочисленного решения.
Основная техника, используемая на третьем шаге (округление) — использование вероятностного подхода, а затем использование вероятностных доводов для ограничения роста цены, возникающего при округлении. Здесь вероятностные доводы используются, чтобы показать существование дискретной структуры с желаемыми свойствами. В этом контексте используются вероятностные доводы, чтобы показать следующее: Если дано какое-то дробное решение задачи ЛП, вероятностное округление с положительной вероятностью даёт целочисленное решение , которое является приближённым к согласно некоторому желаемому критерию.
Наконец, чтобы сделать третий шаг вычислительно эффективным, либо показывается, что является приближённым к с большой вероятностью (так что шаг остаётся вероятностным), либо дерандомизируется шаг округления, обычно с помощью метода условных вероятностей. Последний метод преобразует вероятностный процесс округления в эффективный детерминированный процесс, который гарантированно даёт хороший выход.
Сравнение с другими приложениями вероятностного метода Шаг вероятностного округления отличается от большинства приложений вероятностного метода в двух отношениях: Вычислительная сложность шага округления важна. Шаг должен быть имплементирован быстрым алгоритмом (т.е. алгоритмом полиномиального времени). Распределение вероятности, лежащее в основе случайного эксперимента, является функцией от решения экземпляра задачи линейного программирования. Этот факт является решающим для доказательства гарантированной эффективности алгоритма аппроксимации. То есть для любого экземпляра задачи алгоритм возвращает решение, которое аппроксимирует оптимальное решение для этого конкретного экземпляра. Для сравнения, приложения вероятностного метода в комбинаторике обычно показывают существование структур, свойства которых зависят от параметров входа. Например, рассмотрим теорему Турана, которую можно сформулировать в виде «любой граф с вершинами и средней степенью должен иметь независимое множество размера по меньшей мере ». (См. статью «Метод условных вероятностей», где приведено вероятностное доказательство теоремы Турана.) В то время как существуют графы, для которых эта граница точна, существуют также графы, которые имеют независимые множества, много большие, чем . Таким образом, размер независимого множества, который существует в графе согласно теореме Турана может, в общем случае, быть много меньше, чем максимальное независимое множество графа.
Пример покрытия множества Метод лучше всего проиллюстрировать на примере. Следующий пример показывает, как можно использовать случайное округление для создания аппроксимационого алгоритма для задачи о покрытии множества.
Возьмём любой экземпляр задачи покрытия множества с совокупностью .
Для шага 1, пусть целочисленная задача ЛП — это стандартная задача целочисленного линейного программирования для покрытия множества.
Для шага 2, пусть задача ЛП — это ослабление задачи ЦЛП до задачи ЛП, и пусть — это оптимальное решение этой ослабленной задачи, полученное любым стандартным алгоритмом линейного программирования. (На решение задачи ЛП тратится время, полиномиально зависящее от размера входа.)
(Допустимые решения задачи ЛП — это вектора , которые назначают каждому множеству неотрицательный вес , такой, что, для любого элемента , покрывает — суммарный вес, назначенный множествам, содержащим , не меньше 1, то есть
Оптимальное решение является допустимым решением, цена которого
настолько мала, насколько это возможно.)
Заметим, что любое покрытие множества для даёт a допустимое решение (где для , в противном случае). Цена этого покрытия равна цене , то есть
Другими словами, задача линейного программирования является ослаблением данной задачи покрытия множества.
Поскольку имеет минимальную цену среди допустимых решений задачи ЛП, цена является нижней границей цены оптимального покрытия множества.
Шаг 3: Случайное округление Ниже описание третьего описания шага — шага округления, который должен преобразовать частичное покрытие множества минимальной цены в допустимое целочисленное решение (соответствующее правильному покрытию множества).
Шаг округления даст решение , которое с положительной вероятностью имеет цену, отличающуюся от цены на малый множитель. Тогда (поскольку цена является нижней границей цены оптимального покрытия множества), цена будет отличаться от оптимальной цены на малый множитель.
В качестве отправного пункта рассмотрим наиболее естественную схему округления: Для каждого множества по очереди, возьмём с вероятностью , в противном случае возьмём .
Согласно этой схеме округления математическое ожидание цены выбранных множеств не превосходит , цены частичного покрытия. Это хорошо, но, к сожалению, покрытие не хорошее. Если переменные малы, вероятность, что элемент не покрыт, составляет примерно
Таким образом, математическое ожидание доли покрытых элементов будет постоянно.
Чтобы сделать покрывающим все элементы с большой вероятностью, стандартная схема округления сначала повышает вероятности округления на подходящий множитель . Стандартная схема округления: Фиксируем параметр . Для каждого множества , берём с вероятностью , в противном случае берём .
Умножение вероятностей на увеличивает математическое ожидание цены на , но делает покрытие всех элементов более вероятным. Идея здесь выбрать с как можно меньшим значением так, что все элементы доказуемо будут покрыты с ненулевой вероятностью. Ниже приведён детальный анализ.
Лемма (гарантированная эффективность схемы округления) Фиксируем . С положительной вероятностью схема округления вернёт покрытие с ценой, не превосходящей (и эта цена отличается в раз от цены оптимального покрытия множества).
(Заметим, что при некоторой осторожности значение может быть сведено к .)
Доказательство Выход схемы случайного округления имеет желаемые свойства, пока не случатся следующие «плохие» события: цена решения превысит для некоторого элемента , не покрывает .
Математическое ожидание каждого не превосходит . Ввиду линейности математического ожидания, ожидание не превосходит . Тогда, согласно неравенству Маркова, вероятность первого плохого события не превосходит .
Для оставшихся плохих событий (по одному для каждого элемента ) заметим, что, поскольку , для любого заданного элемента , вероятность, что не покрыто, равна
(Здесь использовано неравенство , которое строго выполняется для .)
Таким образом, для любого числа элементов, вероятность, что элемент не покрыт, меньше .
Вероятность, что одно из плохих событий случится, меньше . Тогда, вероятность отсутствия плохих событий больше нуля и является покрытием множества с ценой, не превосходящей .
Q.E.D. (Что и требовалось доказать)
Дерандомизация методом условных вероятностей
Лемма выше показывает существование покрытия множества с ценой ). В этом контексте нашей целью является эффективный алгоритм аппроксимации, не просто доказательство существования, так что мы не закончили рассмотрение шага 3.
В качестве одного из подходов, можно было бы увеличить немножко , а затем показать, что вероятность успеха не меньше, скажем, 1/4. Используя эту модификацию, повторяя шаг случайного округления несколько раз, можно обеспечить успех с большой вероятностью.
Этот подход ослабляет гарантированную эффективность, но мы опишем другой подход, который даёт детерминированный алгоритм, который обеспечивает гарантированную эффективность, указанную выше. Подход называется методом условных вероятностей.
Детерминированный алгоритм эмулирует схему вероятностного округления — рассматривается каждое множество и выбирается , однако, вместо выбора случайно, основываясь на , алгоритм делает детерминированный выбор, таким образом, что условная вероятность неудачи, определённая выбором, остаётся меньшим 1.
Ограничение условной вероятности неудачи Мы хотим иметь возможность установить значение каждой переменной , чтобы сохранять условную вероятность неудачи меньше 1. Чтобы достичь этого, нам нужна хорошая граница условной вероятности неудачи. Граница получается путём пересмотра исходного доказательства существования. Это доказательство неявным образом ограничивает вероятность неудачи математическим ожиданием случайной переменной , где
является набором элементов, оставшихся непокрытыми.
Случайная переменная может показаться несколько таинственной, но она отражает систематический поход вероятностного доказательства. Первый член в формуле для получается из применения неравенствв Маркова к границе вероятности первого плохого события (цена слишком велика). Этот член привносит по меньшей мере 1 в , если цена слишком велика. Второй член считает число плохих событий второго вида (непокрытые элементы). Он привносит по меньшей мере 1 в , если оставляет какой-либо элемент непокрытым. Таким образом, в любом выходном результате, когда меньше 1, решение должно покрывать все элементы и иметь цену, согласующуюся с желаемой границей из леммы. Кратко, если шаг округления завершается неудачей, . Из этого следует (согласно неравенству Маркова), что является верхней границей вероятности неудачи. Заметим, что приведённые выше доводы уже неявным образом присутствуют в доказательстве леммы, что также показывает, что .
Чтобы применить метод условных вероятностей, нам нужно расширить доводы для ограничения условной вероятности неудачи во время выполнения шага округления. Обычно это можно сделать систематически, хотя это технически может быть трудоёмким.