4632
правки
Максимальная выполнимость формул в 2-КНФ: различия между версиями
Материал из WEGA
Максимальная выполнимость формул в 2-КНФ (посмотреть исходный код)
Версия от 04:02, 3 апреля 2025
, в четверг в 04:02→Основные результаты
Irina (обсуждение | вклад) м (→Нотация) |
Irina (обсуждение | вклад) |
||
| Строка 33: | Строка 33: | ||
== Основные результаты == | == Основные результаты == | ||
Основным результатом данной статьи является процедура, решающая задачу MAX 2-SAT за время <math>O(m \cdot 2^{\omega n/3})</math>. Метод может быть обобщен для ''подсчета'' количества решений ''любой'' задачи оптимизации с ограничениями, в которой на одно ограничение приходится не более двух переменных (см. [17]), хотя изложение в данной статье будет несколько | Основным результатом данной статьи является процедура, решающая задачу MAX 2-SAT за время <math>O(m \cdot 2^{\omega n/3})</math>. Метод может быть обобщен для ''подсчета'' количества решений ''любой'' задачи оптимизации с ограничениями, в которой на одно ограничение приходится не более двух переменных (см. [17]), хотя изложение в данной статье будет несколько отличным от приведенного в указанном источнике и значительно упрощенным. Известно несколько других точных алгоритмов для MAX 2-SAT, работающих более эффективно в специальных случаях – например, на разреженных экземплярах задачи [3, 8, 9, 11, 12, 13, 15, 16]. Ниже редставлена единственная известная на момент написания статьи процедура, выполняемая за время <math>O(poly(m) \cdot 2^{\delta n})</math> (при некотором фиксированном <math>\delta < 1</math>) во всех возможных случаях. | ||
'''Ключевая идея''' | '''Ключевая идея''' | ||
Алгоритм производит редукцию от MAX 2-SAT к задаче MAX TRIANGLE, в которой на входе имеется граф с целочисленными весами вершин и ребер, а целью является вывод 3-цикла с максимальным весом. На первый взгляд существование такой редукции кажется странным, поскольку MAX TRIANGLE можно тривиально решить за время <math>O(n^3)</math>, перебрав все возможные 3-циклы. Суть в том, что редукция экспоненциально увеличивает размер задачи: | Алгоритм производит редукцию от MAX 2-SAT к задаче MAX TRIANGLE, в которой на входе имеется граф с целочисленными весами вершин и ребер, а целью является вывод 3-цикла с максимальным весом. На первый взгляд существование такой редукции кажется странным, поскольку MAX TRIANGLE можно тривиально решить за время <math>O(n^3)</math>, перебрав все возможные 3-циклы. Суть в том, что редукция экспоненциально увеличивает размер задачи: из экземпляра MAX 2-SAT с m дизъюнктами и n переменными мы получаем экземпляр MAX TRIANGLE с <math>O(2^{2n/3})</math> ребрами, <math>O(2^{n/3})</math> вершинами и весами в диапазоне {-m, ..., m}. | ||
| Строка 53: | Строка 53: | ||
'''Доказательство'''. Пусть C – заданная формула в 2-КНФ. Предположим без потери общности, что n кратно 3. Пусть F – экземпляр задачи MAX 2-SAT. Произвольным образом разобьем n переменных экземпляра F на три множества <math>P_1, P_2, P_3</math>, каждое из которых содержит n/3 переменных. Для каждого <math>P_i</math> составим список <math>L_i</math> из всех <math>2^{n/3}</math> присваиваний переменным из <math>P_i</math>. | '''Доказательство'''. Пусть C – заданная формула в 2-КНФ. Предположим без потери общности, что n кратно 3. Пусть F – экземпляр задачи MAX 2-SAT. Произвольным образом разобьем n переменных экземпляра F на три множества <math>P_1, P_2, P_3</math>, каждое из которых содержит n/3 переменных. Для каждого <math>P_i</math> составим список <math>L_i</math> из всех <math>2^{n/3}</math> присваиваний переменным из <math>P_i</math>. | ||
Определим граф <math>G = (V, E)</math>, где <math>V = L_1 \cup L_2 \cup L_3</math> и <math>E = \{ (u, v) | u \in P_i, v \in P_j, i \ne j \}</math>. Таким образом, G – это полный трехдольный граф с <math>2^{n/3}</math> вершинами в каждой доле, и каждая вершина в G соответствует присваиванию n/3 переменным в C. Веса в вершинах и ребрах G распределяются следующим образом. Для вершины v определим w(v) как количество дизъюнктов, выполнимых в результате частичного присваивания, обозначаемого v. Для каждого ребра {u, v} определим <math>w(\{u, v\}) = -W_{uv}</math>, где <math>W_{uv}</math> – количество дизъюнктов, выполнимых ''одновременно'' вершинами u и v. | |||
Определим граф <math>G = (V, E)</math>, где <math>V = L_1 \cup L_2 \cup L_3</math> и <math>E = \{ (u, v) | u \in P_i, v \in P_j, i \ne j \}</math>. Таким образом, G – это полный трехдольный граф с <math>2^{n/3}</math> вершинами в каждой доле, и каждая вершина в G соответствует присваиванию n/3 переменным в C. Веса в вершинах и ребрах G распределяются следующим образом. Для вершины v определим w(v) как количество дизъюнктов, выполнимых в результате частичного присваивания, | |||
Определим вес треугольника в G как полную сумму всех весов и вершин в треугольнике. | Определим вес треугольника в G как полную сумму всех весов и вершин в треугольнике. | ||
