Служба спасения студентов
Служба спасения для студентов (18+)

Новый алгоритм для задачи выполнения наибольшего количества дизъюнктов

Стоимость
3000 руб.
Содержание
Теория
Объем
58 лист.
Год написания

Описание работы

Работа пользователя 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-полной. Несмотря на то, что в предположении гипотезы об экспонен-циальном времени эти задачи не могут быть решены за субэкспонен-циальное время, задача максимальной выполнимости имеет большое количество применений, и подходы к этой задаче активно изучаются.
  • последние годы исследования версий задачи максимальной выпол-нимости, параметризованных общим количеством дизъюнктов и коли-чеством выполненных дизъюнктов, сильно продвинулись за счёт вве-дения сильных правил упрощения, основанных на правиле резолюции, и новых техник сведения экземпляра задачи к экземпляру задачи о покрытии множества. Другой важный результат заключается в том, что задача (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. Поэтому основное направление исследований в этой области
– уменьшение основания экспоненты.
    • последние годы активно продвинулось изучение других пара-метризаций той же задачи: параметризация количеством выполненных дизъюнктов [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).
Алгоритм будет иметь следующую структуру:
  1. Свести экземпляр задачи к экземпляру задачи (n, 5)-MAXSAT.
  1. Свести экземпляр задачи к экземпляру задачи (n, 3)-MAXSAT.
  1. Запустить на полученном экземпляре лучший известный алго-
ритм для (n, 3)-MAXSAT [3].
Уменьшенная мера позволяет использовать тот факт, что время работы алгоритма для задачи (n, 3)-MAXSAT гораздо меньше времени работы алгоритма в общем случае. За счёт увеличения награды за све-дение переменной с большим количеством вхождений к 3-переменной достигается уменьшение чисел расщепления в правилах для перемен-ных с большим количеством вхождений. При этом алгоритм для (n, 3)-MAXSAT относительно заданной меры работает за большее время, чем относительно длины, но это время всё ещё меньше времени работы ал-горитма для общего случая.
 
Список литературы
  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–
    1.  
  1. Bansal N., Raman V. Upper bounds for MaxSat: Further improved // International symposium on algorithms and computation. — Springer. 1999. — P. 247–258.
  1. 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–
    1.  
  1. Berg J., Hyttinen A., Järvisalo M. Applications of MaxSAT in data analysis // Pragmatics of SAT. — 2015.
  1. Bliznets I., Golovnev A. A new algorithm for parameterized MAX-SAT // International Symposium on Parameterized and Exact Com-putation. — Springer. 2012. — P. 37–48.
  1. Bliznets I. A. A new upper bound for (n, 3)-MAX-SAT // Journal of Mathematical Sciences. — 2013. — Vol. 188, no. 1. — P. 1–6.
  1. Chen J., Kanj I. A. Improved exact algorithms for Max-Sat // Discrete Applied Mathematics. — 2004. — Vol. 142, no. 1–3. — P. 17–27.
  2. 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.
  1. Golovnev A., Kutzkov K. New exact algorithms for the 2-constraint satisfaction problem // Theoretical Computer Science. — 2014. — Vol.
    1. — P. 18–27.
  1. Hirsch E. A. New worst-case upper bounds for SAT // Journal of Automated Reasoning. — 2000. — Vol. 24, no. 4. — P. 397–420.
 
57
 
  1. 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.
  1. 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.
  1. Mahajan M., Raman V. Parameterizing above guaranteed values: Max-Sat and MaxCut // J. Algorithms. — 1999. — Vol. 31, no. 2. — P. 335– 354.
  1. Niedermeier R., Rossmanith P. New upper bounds for MaxSat // International Colloquium on Automata, Languages, and Program-ming. — Springer. 1999. — P. 575–584.
  1. 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.
  1. 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.

 

Сколько стоит помощь с учебной работой?