Спасибо Вам за работу!
Информация о работе
Подробнее о работе
Новый алгоритм для задачи выполнения наибольшего количества дизъюнктов
- 58 страниц
- 2020 год
- 1 просмотр
- 0 покупок
Гарантия сервиса Автор24
Уникальность не ниже 50%
Фрагменты работ
Оглавление
Аннотация 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
Введение
Актуальность задачи
Задача о максимальной выполнимости, или, сокращённо, MAXSAT, как оптимизационная версия задачи о выполнимости (сокращённо SAT), одной из самых известных NP-полных задач, имеет широкий круг при-менений, от анализа данных [4] до медицины [12]. При этом не толь-ко задача MAXSAT, но многие её частные случаи, такие, как (n, 3)-MAXSAT, являются NP-трудными [15].
Гипотеза об экспоненциальном времени говорит, что задача 3SAT, то есть задача булевой выполнимости с дополнительным ограничени-ем, что длина каждого дизъюнкта не более трёх, не может быть реше-на быстрее, чем за экспоненциальное время от количества переменных. Можно показать, что из этого следует отсутствие субэкспоненциаль-ного алгоритма и относительно длины входа. Как следствие, задача о максимальной выполнимости также не может быть решена за субэкспо-ненциальное время от длины входа, так как наличие такого алгоритма автоматически влекло бы за собой существование такого алгоритма и для 3SAT.
...
1. Обзор литературы
1.1. История развития области
Задача булевой выполнимости была исторически первой задачей, для которой была доказана NP-полнота (этот известный факт называ-ется теоремой Кука-Левина). Задача о максимальной выполнимости, как оптимизационная версия этой задачи, автоматически является NP-полной и изучается с тех времён.
История развития точных алгоритмов для MAXSAT представлена в таблицах 1.1 – 1.4.
Таблица 1.1: Развитие алгоритмов для задачи MAXSAT
Работа
Год
Результат
Нидермайер и Россманит [14]
1999
O∗(1.1279L) = O∗(20.1737L)
–
Банзал и Раман [2]
1999
O∗(1.1057L) = O∗(20.1450L)
16.5%
Видно, что со времён работы [2] значимого улучшения не произо-шло. В решении задачи в других мерах, связанных с количеством дизъ-юнктов при этом, как показано чуть ниже, существовал прогресс.
...
Определение 2.1. Уменьшенной мерой формулы F называется вели-чина d = L − n3.
Поскольку n3 является неотрицательной величиной, для любой фор-мулы d ≤ L. Таким образом, любой алгоритм, работающий за O∗(αd),
16
автоматически работает за O∗(αL). Следовательно, достаточно суще-ствования алгоритма за O∗(αd). В дальнейшем в работе строится алго-ритм относительно именно уменьшенной меры.
Отметим, что такую меру можно записать в следующем виде:
∑ ∑
d = L − n3 = knk − n3 = 2n3 + knk (1)
k≥3 k≥4
Для задач (n, 4)-MAXSAT и (n, 5)-MAXSAT эта запись имеет вид d = 2n3 + 4n4 и d = 2n3 + 4n4 + 5n5, соответственно. В частности, для мотивации, представленной в разделе 2.1, видно, что при удалении од-ного литерала у 4-переменной эта мера уменьшается на 2, то есть на столько же, на сколько она уменьшается при удалении одного литерала
• 3-переменной.
...
3. Разбор 5-переменных
3.1. Общие наблюдения
Итак, после того, как правило расщепления 2.1 неприменимо, остал-ся экземпляр задачи (n, 5)-MAXSAT. В данном разделе представлен разбор случаев, в совокупности позволяющих избавиться от всех 5-переменных. Прежде всего, несколько наблюдений.
Во-первых, не умаляя общности, 5-переменная может быть (4, 1)-переменной или (3, 2)-переменной. В силу правила упрощения 1.5, в первом случае переменная может встречаться в дизъюнктах длины 1 лишь отрицательно, во втором случае – либо дважды отрицательно, ли-бо однажды положительно или отрицательно. Каждый из этих случаев разобран в разделах этой главы.
Во-вторых, вспомним доказательство леммы 2.1. В доказательстве изменение уменьшенной длины формулы считалось как сумма измене-ний весов всех переменных. Для 5-переменных оказывается, что случа-ев переменных-соседей немного. Все эти случаи приведены в таблице 3.1. В первом столбце перечислено количество вхождений во всю фор-мулу.
...
4. Разбор 4-переменных
4.1. Общие наблюдения
Прежде всего, без ограничения общности, как и в прошлой гла-ве, все 4-переменные являются либо (2, 2)-переменными, либо (3, 1)-переменными.
Мера d, как указано в мотивации в разделе 2.1, разрабатывалась под задачу (n, 4)-MAXSAT для сглаживания разницы в свойствах меж-ду 3-переменными и 4-переменными. Для этой задачи она, как уже ука-зывалось выше, имеет очень простой вид
d = 2n3 + 4n4
Прежде всего, очевидно, что это число всегда чётное. Это объяс-няет то, что в этой главе все векторы расщепления чётные.
Более того, очень часто будет достаточно следующей леммы.
Лемма 4.1. Пусть l – 4-литерал в формуле (n, 4)-MAXSAT вида
(l ∨ C1) ∧ · · · ∧ (l ∨ Ci) ∧ (l ∨ D1) ∧ · · · ∧ (l ∨ Dj) ∧ F ′
Пусть в объединении Ci встречаются литералы хотя бы k раз-личных переменных. Тогда при означивании l = 1 мера d уменьшается хотя бы на 4 + 2k.
Доказательство.
...
Заключение
Itaque earum rerum hic tene-
tur a sapiente delectus, ut aut
reiciendis voluptatibus maiores
alias consequatur aut perferen-
dis doloribus asperiores repellat.
M. Tullius Cicero
Основным результатом работы является следующая теорема. По сравнению с предыдущим лучшим результатом в области [2] она даёт улучшение в логарифмической шкале на 11.7%.
Теорема 5.1. Существует алгоритм для задачи MAXSAT, работаю-щий за O∗(1.0927L).
Доказательство. Как показано в разделе 2.1, любой алгоритм за O∗(αd) работает и за O∗(αL).
Алгоритм за O∗(1.0927d) представлен в главах 2 – 4. Он последова-тельно выполняет правила упрощения и расщепления до тех пор, пока формула не станет экземпляром задачи (n, 3)-MAXSAT, после чего за-пускается алгоритм, представленный в работе [3] для этой задачи.
Полученные оценки на вектора расщепления представлены для удоб-ства в таблице 5.1. Последняя строчка относится к работе [3].
...
Список литературы
1. 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–
108.
2. Bansal N., Raman V. Upper bounds for MaxSat: Further improved // International symposium on algorithms and computation. — Springer. 1999. — P. 247–258.
3. 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–
313.
4. Berg J., Hyttinen A., Järvisalo M. Applications of MaxSAT in data analysis // Pragmatics of SAT. — 2015.
5. Bliznets I., Golovnev A. A new algorithm for parameterized MAX-SAT // International Symposium on Parameterized and Exact Com-putation. — Springer. 2012. — P. 37–48.
6. Bliznets I. A. A new upper bound for (n, 3)-MAX-SAT // Journal of Mathematical Sciences. — 2013. — Vol. 188, no. 1. — P. 1–6.
7. Chen J., Kanj I. A. Improved exact algorithms for Max-Sat // Discrete Applied Mathematics. — 2004. — Vol. 142, no. 1–3. — P. 17–27.
8. 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.
9. Golovnev A., Kutzkov K. New exact algorithms for the 2-constraint satisfaction problem // Theoretical Computer Science. — 2014. — Vol.
526. — P. 18–27.
10. Hirsch E. A. New worst-case upper bounds for SAT // Journal of Automated Reasoning. — 2000. — Vol. 24, no. 4. — P. 397–420.
57
11. 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.
12. 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.
13. Mahajan M., Raman V. Parameterizing above guaranteed values: Max-Sat and MaxCut // J. Algorithms. — 1999. — Vol. 31, no. 2. — P. 335– 354.
14. Niedermeier R., Rossmanith P. New upper bounds for MaxSat // International Colloquium on Automata, Languages, and Program-ming. — Springer. 1999. — P. 575–584.
15. 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.
16. 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.
Форма заказа новой работы
Не подошла эта работа?
Закажи новую работу, сделанную по твоим требованиям
