Проблема удовлетворения ограничений

Набор объектов, состояние которых должно удовлетворять ограничениям

Задачи удовлетворения ограничений ( CSP ) — это математические вопросы, определяемые как набор объектов, состояние которых должно удовлетворять ряду ограничений или ограничений . CSP представляют сущности в задаче как однородный набор конечных ограничений по переменным , который решается методами удовлетворения ограничений . CSP являются предметом исследований как в области искусственного интеллекта, так и в области исследования операций , поскольку регулярность в их формулировке обеспечивает общую основу для анализа и решения проблем многих, казалось бы, не связанных между собой семейств. CSP часто демонстрируют высокую сложность , требующую сочетания эвристик и комбинаторных методов поиска для решения за разумное время. Программирование ограничений (CP) — это область исследований, которая специально фокусируется на решении таких проблем. ^{[1] [2]} Кроме того, проблема булевой выполнимости (SAT), теории выполнимости по модулю (SMT), смешанное целочисленное программирование (MIP) и программирование наборов ответов (ASP) — все это области исследований, фокусирующиеся на решении конкретных форм проблемы удовлетворения ограничений.

Примеры проблем, которые можно смоделировать как проблему удовлетворения ограничений, включают:

• Вывод типа ^{[3] [4]}
• Головоломка «Восемь королев»
• Проблема раскраски карты
• Задача о максимальном разрезе ^[5]
• Судоку , кроссворды , футошики , какуро (перекрестные суммы), Numbrix / Hidato и многие другие логические головоломки

Они часто предоставляются с учебными пособиями по решателям CP , ASP, Boolean SAT и SMT. В общем случае проблемы ограничений могут быть намного сложнее и не могут быть выражены в некоторых из этих более простых систем. Примеры из "реальной жизни" включают автоматизированное планирование , ^{[6] [7]} разрешение лексической неоднозначности , ^{[8] [9]} музыковедение , ^[10] конфигурацию продукта ^[11] и распределение ресурсов . ^[12]

Существование решения CSP можно рассматривать как проблему принятия решения . Это можно решить, найдя решение или не найдя его после исчерпывающего поиска ( стохастические алгоритмы обычно никогда не достигают исчерпывающего вывода, в то время как направленный поиск часто достигает его для достаточно малых задач). В некоторых случаях CSP может быть известно заранее, через какой-то другой процесс математического вывода.

Формальное определение

Формально задача удовлетворения ограничений определяется как тройка , где ^[13] ${\displaystyle \langle X,D,C\rangle }$

• ${\displaystyle X=\{X_{1},\ldots ,X_{n}\}}$это набор переменных,
• ${\displaystyle D=\{D_{1},\ldots ,D_{n}\}}$представляет собой набор соответствующих им областей значений, и
• ${\displaystyle C=\{C_{1},\ldots ,C_{m}\}}$представляет собой набор ограничений.

Каждая переменная может принимать значения в непустом домене . Каждое ограничение в свою очередь является парой , где — набор индексов, а — -арное отношение на соответствующем произведении доменов , где произведение берется с индексами в порядке возрастания. Оценка переменных — это функция от подмножества переменных к определенному набору значений в соответствующем подмножестве доменов. Оценка удовлетворяет ограничению, если значения, присвоенные переменным, удовлетворяют отношению . ${\displaystyle X_{i}}$ ${\displaystyle D_{i}}$ ${\displaystyle C_{j}\in C}$ ${\displaystyle \langle t_{j},R_{j}\rangle }$ ${\displaystyle t_{j}\subseteq \{1,2,\ldots ,n\}}$ ${\displaystyle k}$ ${\displaystyle R_{j}}$ ${\displaystyle k}$ ${\displaystyle \times _{i\in t_{j}}D_{i}}$ ${\displaystyle v}$ ${\displaystyle \langle t_{j},R_{j}\rangle }$ ${\displaystyle t_{j}}$ ${\displaystyle R_{j}}$

Оценка является последовательной , если она не нарушает ни одно из ограничений. Оценка является полной , если она включает все переменные. Оценка является решением , если она является последовательной и полной; говорят, что такая оценка решает проблему удовлетворения ограничений.

Решение

Задачи удовлетворения ограничений в конечных областях обычно решаются с использованием формы поиска . Наиболее используемые методы — это варианты обратного отслеживания , распространения ограничений и локального поиска . Эти методы также часто комбинируются, как в методе VLNS , и текущие исследования включают другие технологии, такие как линейное программирование . ^[14]

Откат назад — это рекурсивный алгоритм. Он поддерживает частичное назначение переменных. Изначально все переменные не назначены. На каждом шаге выбирается переменная, и ей по очереди назначаются все возможные значения. Для каждого значения проверяется согласованность частичного назначения с ограничениями; в случае согласованности выполняется рекурсивный вызов. Когда все значения перепробованы, алгоритм возвращается назад. В этом базовом алгоритме отката назад согласованность определяется как удовлетворение всех ограничений, все переменные которых назначены. Существует несколько вариантов отката назад. Отметка назад повышает эффективность проверки согласованности. Откат назад позволяет сэкономить часть поиска, откатываясь «более чем по одной переменной» в некоторых случаях. Обучение ограничениям выводит и сохраняет новые ограничения, которые можно использовать позже, чтобы избежать части поиска. Опережающий просмотр также часто используется в откате назад, чтобы попытаться предвидеть последствия выбора переменной или значения, таким образом, иногда определяя заранее, когда подзадача выполнима или невыполнима.

Методы распространения ограничений — это методы, используемые для изменения проблемы удовлетворения ограничений. Точнее, это методы, которые обеспечивают форму локальной согласованности , которая является условиями, связанными с согласованностью группы переменных и/или ограничений. Распространение ограничений имеет различные применения. Во-первых, оно превращает проблему в эквивалентную, но обычно более простую в решении. Во-вторых, оно может доказать выполнимость или невыполнимость проблем. Это не гарантируется в общем случае; однако это всегда происходит для некоторых форм распространения ограничений и/или для определенных видов проблем. Наиболее известными и используемыми формами локальной согласованности являются согласованность дуг , согласованность гипердуг и согласованность путей . Самым популярным методом распространения ограничений является алгоритм AC-3 , который обеспечивает согласованность дуг.

Методы локального поиска являются алгоритмами неполной выполнимости. Они могут найти решение проблемы, но могут потерпеть неудачу, даже если проблема выполнима. Они работают путем итеративного улучшения полного назначения по переменным. На каждом шаге небольшое количество переменных изменяют значение с общей целью увеличения количества ограничений, удовлетворяемых этим назначением. Алгоритм минимальных конфликтов является алгоритмом локального поиска, специфичным для CSP, и основан на этом принципе. На практике локальный поиск, по-видимому, работает хорошо, когда эти изменения также затрагиваются случайным выбором. Была разработана интеграция поиска с локальным поиском, что привело к гибридным алгоритмам .

Теоретические аспекты

Сложность вычислений

CSP также изучаются в теории вычислительной сложности , теории конечных моделей и универсальной алгебре . Оказалось, что вопросы о сложности CSP переходят в важные универсально-алгебраические вопросы о базовых алгебрах. Этот подход известен как алгебраический подход к CSP. ^[15]

Поскольку каждая вычислительная задача принятия решений является полиномиально эквивалентной CSP с бесконечным шаблоном, ^[16] общие CSP могут иметь произвольную сложность. В частности, существуют также CSP в классе NP-промежуточных задач, существование которых было продемонстрировано Ладнером , при условии, что P ≠ NP .

Однако большой класс CSP, возникающих из естественных приложений, удовлетворяет дихотомии сложности, что означает, что каждый CSP в этом классе либо находится в P , либо NP-полном . Таким образом, эти CSP предоставляют одно из крупнейших известных подмножеств NP , которое избегает NP-промежуточных проблем. Дихотомия сложности была впервые доказана Шефером для булевых CSP, т. е. CSP над 2-элементной областью, и где все доступные отношения являются булевыми операторами . Этот результат был обобщен для различных классов CSP, в частности для всех CSP над конечными областями. Эта гипотеза о дихотомии конечной области была впервые сформулирована Томасом Федером и Моше Варди ^[17] и окончательно доказана независимо Андреем Булатовым ^[18] и Дмитрием Жуком в 2017 году. ^[19]

Другие классы, для которых подтверждена дихотомия сложности:

• все редукты первого порядка , [ ^20] ${\displaystyle (\mathbb {Q} ,<)}$
• все редукции первого порядка счетного случайного графа , ^[21]
• все редукты первого порядка модельного компаньона класса всех C-отношений, ^[22]
• все редукты первого порядка универсального однородного частично упорядоченного множества , ^[23]
• все редукции первого порядка однородных неориентированных графов, ^[24]
• все редукты первого порядка всех унарных структур, ^[25]
• все CSP в классе сложности MMSNP. ^[26]

Большинство классов CSP, которые, как известно, поддаются обработке, — это те, в которых гиперграф ограничений имеет ограниченную ширину дерева ^[27] или в которых ограничения имеют произвольную форму, но существуют нетривиальные по уравнениям полиморфизмы набора отношений ограничений ^{[28] .}

Гипотеза о дихотомии бесконечной области ^[29] была сформулирована для всех CSP редуктов конечно ограниченных однородных структур, утверждая, что CSP такой структуры принадлежит P тогда и только тогда, когда ее полиморфный клон является нетривиальным по уравнениям, и NP-трудным в противном случае.

Сложность таких CSP с бесконечной областью применения, а также других обобщений (Valued CSP, Quantified CSP, Promise CSP) все еще является областью активных исследований. ^[30] [1][2]

Каждый CSP также можно рассматривать как проблему сдерживания конъюнктивного запроса . ^[31]

Проблемы с функциями

Аналогичная ситуация существует между функциональными классами FP и #P . По обобщению теоремы Ладнера , также нет проблем ни в FP, ни в #P-полном , пока FP ≠ #P. Как и в случае решения, проблема в #CSP определяется набором отношений. Каждая проблема принимает булеву формулу в качестве входных данных, а задача состоит в том, чтобы вычислить количество удовлетворяющих назначений. Это можно дополнительно обобщить, используя большие размеры доменов и прикрепляя вес к каждому удовлетворяющему назначению и вычисляя сумму этих весов. Известно, что любая сложная взвешенная задача #CSP находится либо в FP, либо в #P-трудном. ^[32]

Варианты

Классическая модель проблемы удовлетворения ограничений определяет модель статических, негибких ограничений. Эта жесткая модель является недостатком, который затрудняет простое представление проблем. ^[33] Было предложено несколько модификаций базового определения CSP для адаптации модели к широкому спектру проблем.

Динамические CSP

Динамические CSP ^[34] ( DCSP s) полезны, когда исходная формулировка проблемы каким-либо образом изменяется, обычно потому, что набор рассматриваемых ограничений развивается из-за окружающей среды. ^[35] DCSP рассматриваются как последовательность статических CSP, каждая из которых является преобразованием предыдущей, в которой переменные и ограничения могут быть добавлены (ограничение) или удалены (релаксация). Информация, найденная в исходных формулировках проблемы, может быть использована для уточнения следующих. Метод решения можно классифицировать в соответствии со способом передачи информации:

• Оракулы : решения, найденные для предыдущих CSP в последовательности, используются в качестве эвристик для руководства разрешением текущей CSP с нуля.
• Локальное исправление: каждая CSP рассчитывается, начиная с частичного решения предыдущей и исправляя несоответствующие ограничения с помощью локального поиска .
• Запись ограничений: новые ограничения определяются на каждом этапе поиска, чтобы отразить изучение несогласованной группы решений. Эти ограничения переносятся на новые проблемы CSP.

Гибкие CSP

Классические CSP рассматривают ограничения как жесткие, то есть они являются императивными (каждое решение должно удовлетворять всем из них) и негибкими (в том смысле, что они должны быть полностью удовлетворены, иначе они полностью нарушены). Гибкие CSP ослабляют эти предположения, частично ослабляя ограничения и позволяя решению не соответствовать всем из них. Это похоже на предпочтения в планировании на основе предпочтений . Некоторые типы гибких CSP включают:

• MAX-CSP, где допускается нарушение ряда ограничений, а качество решения измеряется количеством выполненных ограничений.
• Weighted CSP , MAX-CSP, в котором каждое нарушение ограничения взвешивается в соответствии с предопределенным предпочтением. Таким образом, удовлетворение ограничения с большим весом является предпочтительным.
• Нечеткие ограничения модели CSP представляют собой нечеткие отношения, в которых удовлетворение ограничения является непрерывной функцией значений его переменных, переходя от полностью удовлетворенного до полностью нарушенного.

Децентрализованные CSP

В DCSP ^[36] каждая переменная ограничения рассматривается как имеющая отдельное географическое местоположение. На обмен информацией между переменными накладываются жесткие ограничения, требующие использования полностью распределенных алгоритмов для решения проблемы удовлетворения ограничений.

Смотрите также

• Составной граф ограничений
• Программирование ограничений
• Декларативное программирование
• Ограниченная оптимизация (COP)
• Оптимизация распределенных ограничений
• Гомоморфизм графа
• Уникальные игры гипотеза
• Проблема удовлетворения взвешенных ограничений (WCSP)

Ссылки

1. Лекутр, Кристоф (2013). Сети ограничений: методы и алгоритмы . Wiley. стр. 26. ISBN 978-1-118-61791-5.
2. «Ограничения – вкл. возможность публикации открытого доступа». springer.com . Получено 2019-10-03 .
3. Чандра, Сатиш и др. «Вывод типа для статической компиляции JavaScript». ACM SIGPLAN Notices 51.10 (2016): 410-429.
4. Джим, Тревор и Йенс Палсберг. «Вывод типа в системах рекурсивных типов с подтипированием». Доступно на веб-странице авторов (1999).
5. Фархи, Эдвард; Арам В. Харроу (2016). «Квантовое превосходство через алгоритм квантовой приближенной оптимизации». arXiv : 1602.07674 [quant-ph].
6. Малик Галлаб; Дана Нау; Паоло Траверсо (21 мая 2004 г.). Автоматизированное планирование: теория и практика. Elsevier. стр. 1–. ISBN 978-0-08-049051-9.
7. Удовлетворение динамических гибких ограничений и его применение в планировании ИИ, архивировано 06.02.2009 на Wayback Machine Ян Мигель – слайды.
8. Деметриу, Джордж К. «Устранение лексической неоднозначности с помощью обработки ограничений в Прологе (CHIP)». Труды шестой конференции Европейского отделения Ассоциации компьютерной лингвистики. Ассоциация компьютерной лингвистики, 1993.
9. Макдональд, Мэриэллен К. и Марк С. Сейденберг. «Оценка удовлетворения ограничений лексического и фразового понимания». Справочник по психолингвистике (второе издание). 2006. 581–611.
10. Маурисио Торо, Карлос Агон, Камило Руэда, Жерар Ассайаг. «GELISP: СТРУКТУРА ДЛЯ ПРЕДСТАВЛЕНИЯ ПРОБЛЕМ УДОВЛЕТВОРЕНИЯ МУЗЫКАЛЬНЫХ ОГРАНИЧЕНИЙ И СТРАТЕГИЙ ПОИСКА». Журнал теоретических и прикладных информационных технологий 86 (2). 2016. 327–331.
11. Применение подхода удовлетворения ограничений для решения проблем конфигурации продукта с использованием правил конфигурации на основе мощности , Донг Янг и Мин Донг, Журнал интеллектуального производства, том 24, страницы 99–111 (2013)
12. Моди, Прагнеш Джей и др. «Подход к распределению ресурсов с учетом динамических распределенных ограничений». Международная конференция по принципам и практике программирования в условиях ограничений. Springer, Берлин, Гейдельберг, 2001.
13. Стюарт Джонатан Рассел; Питер Норвиг (2010). Искусственный интеллект: современный подход . Prentice Hall. стр. Глава 6. ISBN 9780136042594.
14. Милано, Микела ; Ван Хентенрик, Паскаль, ред. (2011). Гибридная оптимизация: десять лет CPAIOR . Международная конференция по интеграции методов искусственного интеллекта и OR в программирование в ограничениях для задач комбинаторной оптимизации. Нью-Йорк: Springer. ISBN 9781441916440. OCLC  695387020.
15. Барто, Либор; Брэди, Заратустра; Булатов, Андрей; Козик, Марчин; Жук, Дмитрий (2024-05-15). "Объединение трех алгебраических подходов к CSP с помощью минимальных алгебр Тейлора". TheoretiCS . 3 : 11361. arXiv : 2104.11808 . doi :10.46298/theoretics.24.14. ISSN  2751-4838.
16. Bodirsky, Manuel; Grohe, Martin (2008). "Non-dichotomies in Constraint Satisfaction Complexity". В Aceto, Luca; Damgård, Ivan; Goldberg, Leslie Ann; Halldórsson, Magnús M.; Ingólfsdóttir, Anna; Walukiewicz, Igor (ред.). Automata, Languages ​​and Programming . Lecture Notes in Computer Science. Vol. 5126. Berlin, Heidelberg: Springer. pp. 184–196. doi :10.1007/978-3-540-70583-3_16. ISBN 978-3-540-70583-3.
17. Федер, Томас; Варди, Моше Й. (1998). «Вычислительная структура монотонного монадического SNP и удовлетворение ограничений: исследование с помощью теории данных и групп». Журнал SIAM по вычислениям . 28 (1): 57–104. doi :10.1137/S0097539794266766. ISSN  0097-5397.
18. Булатов, Андрей (2017). «Теорема дихотомии для неравномерных CSP». Труды 58-го ежегодного симпозиума IEEE по основам компьютерной науки, FOCS 2017. IEEE Computer Society. стр. 319–330. arXiv : 1703.03021 . doi : 10.1109/FOCS.2017.37. ISBN 978-1-5386-3464-6.
19. Жук, Дмитрий (2020). «Доказательство гипотезы дихотомии CSP». Журнал ACM . 67 (5): 1–78. arXiv : 1704.01914 . doi : 10.1145/3402029.
20. Бодирски, Мануэль; Кара, Ян (2010-02-08). «Сложность проблем удовлетворения временных ограничений». J. ACM . 57 (2): 9:1–9:41. doi :10.1145/1667053.1667058. ISSN  0004-5411.
21. Бодирский, Мануэль; Пинскер, Майкл (2011). «Теорема Шефера для графов». Труды 43-го ежегодного симпозиума по теории вычислений (STOC '11) . Ассоциация вычислительной техники . С. 655–664. arXiv : 1011.2894 . doi : 10.1145/1993636.1993724. ISBN 978-1-4503-0691-1. S2CID  47097319.
22. Бодирски, Мануэль; Йонссон, Питер; Фам, Трунг Ван (2017-08-02). «Сложность проблем удовлетворения ограничений филогении». ACM Trans. Comput. Logic . 18 (3): 23:1–23:42. arXiv : 1503.07310 . doi :10.1145/3105907. ISSN  1529-3785.
23. Компачер, Майкл; Фам, Трунг Ван (2017). «Дихотомия сложности для удовлетворения ограничений Посета». DROPS-IDN/V2/Document/10.4230/LIPIcs.STACS.2017.47 . Замок Дагштуль – Центр информатики Лейбница. doi : 10.4230/LIPIcs.STACS.2017.47 .
24. Бодирски, Мануэль; Мартин, Барнаби; Пинскер, Майкл; Понграц, Андраш (январь 2019 г.). «Проблемы удовлетворения ограничений для редукций однородных графов». SIAM Journal on Computing . 48 (4): 1224–1264. arXiv : 1602.05819 . doi : 10.1137/16M1082974. ISSN  0097-5397.
25. Бодирский, Мануэль; Мотте, Антуан (2018-05-20), "Дихотомия для редукций первого порядка унарных структур", Логические методы в информатике , 14 (2), arXiv : 1601.04520 , doi : 10.23638/LMCS-14(2:13)2018
26. Бодирский, Мануэль; Мадлен, Флоран; Мотте, Антуан (2018-07-09). «Универсально-алгебраическое доказательство дихотомии сложности для монотонного монадического SNP». Труды 33-го ежегодного симпозиума ACM/IEEE по логике в компьютерных науках . LICS '18. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 105–114. arXiv : 1802.03255 . doi :10.1145/3209108.3209156. ISBN 978-1-4503-5583-4.
27. Барто, Либор; Козик, Марчин (2014-01-01). «Проблемы удовлетворения ограничений, решаемые методами локальной согласованности». J. ACM . 61 (1): 3:1–3:19. doi :10.1145/2556646. ISSN  0004-5411.
28. Бодирский, Мануэль (2021). Сложность удовлетворения ограничений бесконечной области. Конспект лекций по логике. Кембридж: Издательство Кембриджского университета. ISBN 978-1-107-04284-1.
29. Бодирский, Мануэль; Пинскер, Майкл; Понграч, Андраш (март 2021 г.). «Проективные клоновые гомоморфизмы». Журнал символической логики . 86 (1): 148–161. arXiv : 1409.4601 . дои : 10.1017/jsl.2019.23. ISSN  0022-4812.
30. Пинскер, Майкл (31.03.2022). «Текущие проблемы удовлетворения ограничений бесконечной области: дилеммы бесконечных овец». arXiv : 2203.17182 [cs.LO].
31. Колайтис, Фокион Г.; Варди, Моше Й. (2000). «Конъюнктивно-запросное сдерживание и удовлетворение ограничений». Журнал компьютерных и системных наук . 61 (2): 302–332. doi : 10.1006/jcss.2000.1713 .
32. Cai, Jin-Yi; Chen, Xi (2012). «Сложность подсчета CSP с комплексными весами». Труды сорок четвертого ежегодного симпозиума ACM по теории вычислений (STOC '12) . стр. 909–920. arXiv : 1111.2384 . doi : 10.1145/2213977.2214059. ISBN 978-1-4503-1245-5. S2CID  53245129.
33. Мигель, Ян (июль 2001 г.). Удовлетворение динамических гибких ограничений и его применение к планированию ИИ (диссертация на степень доктора философии). Школа информатики Эдинбургского университета . CiteSeerX 10.1.1.9.6733 . hdl :1842/326. 
34. Дектер, Р. и Дектер, А., Поддержание убеждений в сетях с динамическими ограничениями. Архивировано 17 ноября 2012 г. на Wayback Machine в трудах AAAI-88, 37–42.
35. Повторное использование решений в задачах удовлетворения динамических ограничений, Томас Шиекс
36. Даффи, KR; Лейт, DJ (август 2013 г.), «Децентрализованное удовлетворение ограничений», IEEE/ACM Transactions on Networking, 21(4) , т. 21, стр. 1298–1308, arXiv : 1103.3240 , doi : 10.1109/TNET.2012.2222923, S2CID  11504393

Дальнейшее чтение

• Краткое введение в удовлетворение ограничений на YouTube
• Мануэль Бодирски (2021). Сложность удовлетворения ограничений бесконечной области . Cambridge University Press. https://doi.org/10.1017/9781107337534
• Стивен Минтон; Энди Филипс; Марк Д. Джонстон; Филип Лэрд (1993). «Минимизация конфликтов: эвристический метод исправления для проблем удовлетворения ограничений и планирования». Журнал исследований искусственного интеллекта . 58 (1–3): 161–205. CiteSeerX  10.1.1.308.6637 . doi :10.1016/0004-3702(92)90007-k. S2CID  14830518.
• Цанг, Эдвард (1993). Основы удовлетворения ограничений. Academic Press. ISBN  0-12-701610-4
• Чен, Хуби (декабрь 2009 г.). «Встреча логики, сложности и алгебры». ACM Computing Surveys . 42 (1): 1–32. arXiv : cs/0611018 . doi :10.1145/1592451.1592453. S2CID  11975818.
• Дехтер, Рина (2003). Обработка ограничений. Морган Кауфманн. ISBN  1-55860-890-7
• Апт, Кшиштоф (2003). Принципы программирования ограничений . Cambridge University Press. ISBN 9780521825832. ISBN  0-521-82583-0
• Лекутр, Кристоф (2009). Сети ограничений: методы и алгоритмы. ИСТЭ/Уайли. ISBN  978-1-84821-106-3
• Томас Федер, Удовлетворение ограничений: личная точка зрения, рукопись.
• Архив ограничений
• Принудительно удовлетворяемые контрольные показатели CSP модели RB Архивировано 25.01.2021 на Wayback Machine
• Тесты – XML-представление экземпляров CSP
• XCSP3 – формат на основе XML, предназначенный для представления экземпляров CSP.
• Распространение ограничений – диссертация Гвидо Така, дающая хороший обзор теории и вопросов реализации.