4622
правки
Максимальная выполнимость формул в 2-КНФ: различия между версиями
Материал из WEGA
Максимальная выполнимость формул в 2-КНФ (посмотреть исходный код)
Версия от 03:42, 25 марта 2025
, 25 март→Основные результаты
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == МАКС 2-ВЫП (''MAX 2-SAT'') == Постановка задачи == В задаче о максимальной выполнимости формул в 2-КНФ (которая далее будет обозначаться как MAX 2-SAT, или МАКС 2-ВЫП) на входе имеется булева формула в конъюнктивной нормальной форме, такая...») |
Irina (обсуждение | вклад) |
||
| Строка 37: | Строка 37: | ||
'''Ключевая идея''' | '''Ключевая идея''' | ||
Алгоритм производит редукцию от MAX 2-SAT к задаче MAX TRIANGLE, в которой на входе имеется граф с целочисленными весами вершин и ребер, а целью является вывод 3-цикла с максимальным весом. На первый взгляд существование такой редукции кажется странным, поскольку MAX TRIANGLE можно тривиально решить за время O(n3), перебрав все возможные 3-циклы. Суть в том, что редукция экспоненциально увеличивает размер задачи: от экземпляра MAX 2-SAT с m пунктами и n переменными к экземпляра MAX TRIANGLE с O(22n/3) ребрами, O(2n/3) вершинами и весами в диапазоне {-m... ; mg. | Алгоритм производит редукцию от MAX 2-SAT к задаче MAX TRIANGLE, в которой на входе имеется граф с целочисленными весами вершин и ребер, а целью является вывод 3-цикла с максимальным весом. На первый взгляд существование такой редукции кажется странным, поскольку MAX TRIANGLE можно тривиально решить за время O(n3), перебрав все возможные 3-циклы. Суть в том, что редукция экспоненциально увеличивает размер задачи: от экземпляра MAX 2-SAT с m пунктами и n переменными к экземпляра MAX TRIANGLE с O(22n/3) ребрами, O(2n/3) вершинами и весами в диапазоне {-m... ; mg. | ||
| Строка 44: | Строка 45: | ||
'''Основной алгоритм''' | '''Основной алгоритм''' | ||
Сначала описывается редукция от MAX 2-SAT к MAX TRIANGLE, согласно которой каждый треугольник веса K в полученном графе находится в взаимно-однозначном соответствии с присваиванием, при котором становятся выполнимыми K дизъюнктов экземпляра MAX 2-SAT. Пусть a, b – вещественные числа, и пусть Z[a; b] := [a; b] \ Z. | Сначала описывается редукция от MAX 2-SAT к MAX TRIANGLE, согласно которой каждый треугольник веса K в полученном графе находится в взаимно-однозначном соответствии с присваиванием, при котором становятся выполнимыми K дизъюнктов экземпляра MAX 2-SAT. Пусть a, b – вещественные числа, и пусть Z[a; b] := [a; b] \ Z. | ||
