Новый алгоритм для задачи выполнения наибольшего количества дизъюнктов
Описание работы
Работа пользователя Vseznayka1995
Добрый день! Уважаемые студенты, Вашему вниманию представляется дипломная работа на тему: «Новый алгоритм для задачи выполнения наибольшего количества дизъюнктов»
Оригинальность работы 97%
Оглавление
Аннотация3
Введение5
1Обзор литературы10
1.1Историяразвитияобласти . . . . . . . . . . . . . . . . . .10
1.2Правилаупрощения......................12
1.3Выводы.............................15
2Уменьшенная мера16
2.1Мотивация...........................16
2.2Определение..........................16
2.3Свойства ............................17
2.4Выводы.............................20
3Разбор 5-переменных22
3.1Общиенаблюдения ......................22
3.2Разбор(4,1)-переменных . . . . . . . . . . . . . . . . . . .25
3.3Разбор (3, 2)-переменных в двух дизъюнктах длины 1 . .27
3.4Разбор (3, 2)-литералов в дизъюнкте длины 1 . . . . . . .30
3.5Разбор других (3, 2)-переменных . . . . . . . . . . . . . .32
3.6Выводы.............................41
4Разбор 4-переменных42
4.1Общиенаблюдения ......................42
4.2Разбор(2,2)-переменных . . . . . . . . . . . . . . . . . . .43
4.3Разбор (3, 1)-переменных – не одиночек . . . . . . . . . .48
4.4Разбор(3,1)-одиночек.....................50
4.5Выводы.............................53
Заключение54
Список литературы57
Аннотация
Задача булевой выполнимости – исторически первая задача, для которой была доказана NP-полнота. Её оптимизационная версия, за-дача максимальной выполнимости, состоящая в выполнении наиболь-шего количества дизъюнктов в булевой формуле, также является NP-полной. Несмотря на то, что в предположении гипотезы об экспонен-циальном времени эти задачи не могут быть решены за субэкспонен-циальное время, задача максимальной выполнимости имеет большое количество применений, и подходы к этой задаче активно изучаются.
Оригинальность работы 97%
Оглавление
Аннотация3
Введение5
1Обзор литературы10
1.1Историяразвитияобласти . . . . . . . . . . . . . . . . . .10
1.2Правилаупрощения......................12
1.3Выводы.............................15
2Уменьшенная мера16
2.1Мотивация...........................16
2.2Определение..........................16
2.3Свойства ............................17
2.4Выводы.............................20
3Разбор 5-переменных22
3.1Общиенаблюдения ......................22
3.2Разбор(4,1)-переменных . . . . . . . . . . . . . . . . . . .25
3.3Разбор (3, 2)-переменных в двух дизъюнктах длины 1 . .27
3.4Разбор (3, 2)-литералов в дизъюнкте длины 1 . . . . . . .30
3.5Разбор других (3, 2)-переменных . . . . . . . . . . . . . .32
3.6Выводы.............................41
4Разбор 4-переменных42
4.1Общиенаблюдения ......................42
4.2Разбор(2,2)-переменных . . . . . . . . . . . . . . . . . . .43
4.3Разбор (3, 1)-переменных – не одиночек . . . . . . . . . .48
4.4Разбор(3,1)-одиночек.....................50
4.5Выводы.............................53
Заключение54
Список литературы57
Аннотация
Задача булевой выполнимости – исторически первая задача, для которой была доказана NP-полнота. Её оптимизационная версия, за-дача максимальной выполнимости, состоящая в выполнении наиболь-шего количества дизъюнктов в булевой формуле, также является NP-полной. Несмотря на то, что в предположении гипотезы об экспонен-циальном времени эти задачи не могут быть решены за субэкспонен-циальное время, задача максимальной выполнимости имеет большое количество применений, и подходы к этой задаче активно изучаются.
- последние годы исследования версий задачи максимальной выпол-нимости, параметризованных общим количеством дизъюнктов и коли-чеством выполненных дизъюнктов, сильно продвинулись за счёт вве-дения сильных правил упрощения, основанных на правиле резолюции, и новых техник сведения экземпляра задачи к экземпляру задачи о покрытии множества. Другой важный результат заключается в том, что задача (n, 3)-MAXSAT, параметризованная количеством перемен-ных, решается гораздо быстрее, чем в общем случае [3]. В данной ра-боте рассматривается задача максимальной выполнимости, решаемая относительно длины формулы, то есть суммарного количества литера-лов во всех дизъюнктах. Несмотря на то, что некоторые новые пра-вила оказываются полезными для такой задачи, большинство из них увеличивают длину формулы и не могут быть применены. В этой ра-боте представлены новые правила упрощения, не увеличивающие дли-ну формулы. Также предлагается новый параметр с пониженной стои-мостью 3-переменных, использующий то, что (n, 3)-MAXSAT решается гораздо быстрее, чем общий случай задачи максимальной выполнимо-сти. Комбинация двух методов позволяет получить алгоритм, работаю-щий за время O∗(1.093L). Это улучшает предыдущую верхнюю оценку в O∗(1.106L), полученную Банзалом и Раманом [2].
Введение
Актуальность задачи
Задача о максимальной выполнимости, или, сокращённо, MAXSAT, как оптимизационная версия задачи о выполнимости (сокращённо SAT), одной из самых известных NP-полных задач, имеет широкий круг при-менений, от анализа данных [4] до медицины [12]. При этом не толь-ко задача MAXSAT, но многие её частные случаи, такие, как (n, 3)-MAXSAT, являются NP-трудными [15].
Гипотеза об экспоненциальном времени говорит, что задача 3SAT, то есть задача булевой выполнимости с дополнительным ограничени-ем, что длина каждого дизъюнкта не более трёх, не может быть реше-на быстрее, чем за экспоненциальное время от количества переменных. Можно показать, что из этого следует отсутствие субэкспоненциаль-ного алгоритма и относительно длины входа. Как следствие, задача о максимальной выполнимости также не может быть решена за субэкспо-ненциальное время от длины входа, так как наличие такого алгоритма автоматически влекло бы за собой существование такого алгоритма и для 3SAT. Поэтому основное направление исследований в этой области
– уменьшение основания экспоненты.
Актуальность задачи
Задача о максимальной выполнимости, или, сокращённо, MAXSAT, как оптимизационная версия задачи о выполнимости (сокращённо SAT), одной из самых известных NP-полных задач, имеет широкий круг при-менений, от анализа данных [4] до медицины [12]. При этом не толь-ко задача MAXSAT, но многие её частные случаи, такие, как (n, 3)-MAXSAT, являются NP-трудными [15].
Гипотеза об экспоненциальном времени говорит, что задача 3SAT, то есть задача булевой выполнимости с дополнительным ограничени-ем, что длина каждого дизъюнкта не более трёх, не может быть реше-на быстрее, чем за экспоненциальное время от количества переменных. Можно показать, что из этого следует отсутствие субэкспоненциаль-ного алгоритма и относительно длины входа. Как следствие, задача о максимальной выполнимости также не может быть решена за субэкспо-ненциальное время от длины входа, так как наличие такого алгоритма автоматически влекло бы за собой существование такого алгоритма и для 3SAT. Поэтому основное направление исследований в этой области
– уменьшение основания экспоненты.
-
- последние годы активно продвинулось изучение других пара-метризаций той же задачи: параметризация количеством выполненных дизъюнктов [8] и общим количеством дизъюнктов [16]. Для формул с большой средней длиной дизъюнкта эти алгоритмы дают хорошее вре-мя работы. Однако если в формуле большинство дизъюнктов имеют длину 1 или 2, алгоритм относительно длины применять эффективнее. При этом стоит отметить, что задача MAX-2-SAT, где все дизъюнкты имеют длину 1 или 2, уже является NP-трудной, хотя для неё суще-ствуют специальные алгоритмы, позволяющие решать её быстрее, чем в общем случае [9]. Тем не менее, если ограничения на максимальную длину дизъюнкта нет, но средняя длина небольшая, задача эффектив-но решается именно алгоритмом относительно длины формулы.
5
Условие задачи
Задача MAXSAT формулируется следующим образом:
MAXSAT
Вход: Булева формула F в конъюнктивной нормальной форме (КНФ) и число k
Ответ: Означивание переменных, выполняющее хотя бы k дизъ-юнктов.
Длина формулы обозначается за L.
Как упоминалось выше, цель работы – создать алгоритм за O∗(αL) при минимальном α. Однако, в процессе решения задачи выяснилось, что такой алгоритм проще построить для другой, уменьшенной меры d = L − n3. Такая мера всегда не превосходит длины формулы L, таким образом, алгоритм, работающий за O∗(αd) автоматически работает за
O∗(αL).
Алгоритм будет иметь следующую структуру:
Уменьшенная мера позволяет использовать тот факт, что время работы алгоритма для задачи (n, 3)-MAXSAT гораздо меньше времени работы алгоритма в общем случае. За счёт увеличения награды за све-дение переменной с большим количеством вхождений к 3-переменной достигается уменьшение чисел расщепления в правилах для перемен-ных с большим количеством вхождений. При этом алгоритм для (n, 3)-MAXSAT относительно заданной меры работает за большее время, чем относительно длины, но это время всё ещё меньше времени работы ал-горитма для общего случая.
Задача MAXSAT формулируется следующим образом:
MAXSAT
Вход: Булева формула F в конъюнктивной нормальной форме (КНФ) и число k
Ответ: Означивание переменных, выполняющее хотя бы k дизъ-юнктов.
Длина формулы обозначается за L.
Как упоминалось выше, цель работы – создать алгоритм за O∗(αL) при минимальном α. Однако, в процессе решения задачи выяснилось, что такой алгоритм проще построить для другой, уменьшенной меры d = L − n3. Такая мера всегда не превосходит длины формулы L, таким образом, алгоритм, работающий за O∗(αd) автоматически работает за
O∗(αL).
Алгоритм будет иметь следующую структуру:
- Свести экземпляр задачи к экземпляру задачи (n, 5)-MAXSAT.
- Свести экземпляр задачи к экземпляру задачи (n, 3)-MAXSAT.
- Запустить на полученном экземпляре лучший известный алго-
Уменьшенная мера позволяет использовать тот факт, что время работы алгоритма для задачи (n, 3)-MAXSAT гораздо меньше времени работы алгоритма в общем случае. За счёт увеличения награды за све-дение переменной с большим количеством вхождений к 3-переменной достигается уменьшение чисел расщепления в правилах для перемен-ных с большим количеством вхождений. При этом алгоритм для (n, 3)-MAXSAT относительно заданной меры работает за большее время, чем относительно длины, но это время всё ещё меньше времени работы ал-горитма для общего случая.
Список литературы
- An improved branching algorithm for (n, 3)-MaxSAT based on refined observations / W. Li [et al.] // International Conference on Combin-atorial Optimization and Applications. — Springer. 2017. — P. 94–
- Bansal N., Raman V. Upper bounds for MaxSat: Further improved // International symposium on algorithms and computation. — Springer. 1999. — P. 247–258.
- Belova T., Bliznets I. Upper and Lower Bounds for Different Paramet-erizations of (n, 3)-MAXSAT // International Conference on Combin-atorial Optimization and Applications. — Springer. 2018. — P. 299–
- Berg J., Hyttinen A., Järvisalo M. Applications of MaxSAT in data analysis // Pragmatics of SAT. — 2015.
- Bliznets I., Golovnev A. A new algorithm for parameterized MAX-SAT // International Symposium on Parameterized and Exact Com-putation. — Springer. 2012. — P. 37–48.
- Bliznets I. A. A new upper bound for (n, 3)-MAX-SAT // Journal of Mathematical Sciences. — 2013. — Vol. 188, no. 1. — P. 1–6.
- Chen J., Kanj I. A. Improved exact algorithms for Max-Sat // Discrete Applied Mathematics. — 2004. — Vol. 142, no. 1–3. — P. 17–27.
- Chen J., Xu C., Wang J. Dealing with 4-variables by resolution: an improved MaxSAT algorithm // Workshop on Algorithms and Data Structures. — Springer. 2015. — P. 178–188.
- Golovnev A., Kutzkov K. New exact algorithms for the 2-constraint satisfaction problem // Theoretical Computer Science. — 2014. — Vol.
- — P. 18–27.
- Hirsch E. A. New worst-case upper bounds for SAT // Journal of Automated Reasoning. — 2000. — Vol. 24, no. 4. — P. 397–420.
57
- Kulikov A. S., Kutskov K. New upper bounds for the problem of maximal satisfiability // Discrete Mathematics and Applications. — 2009. — Vol. 19, no. 2. — P. 155–172.
- Lin P.-C. K., Khatri S. P. Application of Max-SAT-based ATPG to optimal cancer therapy design // BMC genomics. — 2012. — Vol. 13, S6. — S5.
- Mahajan M., Raman V. Parameterizing above guaranteed values: Max-Sat and MaxCut // J. Algorithms. — 1999. — Vol. 31, no. 2. — P. 335– 354.
- Niedermeier R., Rossmanith P. New upper bounds for MaxSat // International Colloquium on Automata, Languages, and Program-ming. — Springer. 1999. — P. 575–584.
- Raman V., Ravikumar B., Rao S. S. A simplified NP-complete MAX-SAT problem // Information Processing Letters. — 1998. — Vol. 65, no. 1. — P. 1–6.
- Resolution and domination: an improved exact MaxSAT algorithm / C. Xu [et al.] // Proceedings of the 28th International Joint Conference on Artificial Intelligence. — AAAI Press. 2019. — P. 1191–1197.