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

Не путать с коммуникацией последовательных процессов .

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

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

• Вывод типа
• Загадка «Восемь королев»
• Проблема с раскраской карты
• Проблема максимального разреза
• Судоку , кроссворды , футосики , Какуро (Кросс-суммы), Нумбрикс / Хидато и многие другие логические головоломки.

Они часто сопровождаются учебными пособиями по решателям CP , ASP, Boolean SAT и SMT. В общем случае проблемы с ограничениями могут быть намного сложнее и могут быть невыразимы в некоторых из этих более простых систем. Примеры из «реальной жизни» включают автоматическое планирование , лексическое устранение неоднозначности , музыковедение , конфигурация продукта и распределение ресурсов .

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

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

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

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

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

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

Решение

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

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

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

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

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

Вычислительная сложность

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

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

Однако большой класс CSP, возникающих в результате естественных приложений, удовлетворяет дихотомии сложности, что означает, что каждый CSP внутри этого класса является либо P- , либо NP-полным . Таким образом, эти CSP предоставляют одно из крупнейших известных подмножеств NP , которое позволяет избежать промежуточных NP- проблем. Дихотомия сложности была впервые доказана Шефером для логических CSP, то есть CSP в двухэлементной области, где все доступные отношения являются логическими операторами . Этот результат был обобщен для различных классов CSP, особенно для всех CSP в конечных областях. Эта гипотеза дихотомии конечной области была впервые сформулирована Томасом Федером и Моше Варди: и наконец доказано независимо Андреем Булатовым and Dmitriy Zhuk in 2017.

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

• все первого редукции порядка $(\mathbb {Q} ,<)$,
• все редукции первого порядка счетного случайного графа ,
• все редукции первого порядка модели -компаньона класса всех C-отношений,
• все редукции первого порядка универсального однородного частичного множества ,
• все редукции первого порядка однородных неориентированных графов,
• все редукты первого порядка всех унарных структур,
• все CSP класса сложности MMSNP.

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

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

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

Каждый CSP также может рассматриваться как проблема сдерживания конъюнктивных запросов .

Функциональные проблемы

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

Варианты

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

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

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

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

Гибкие CSP

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

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

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

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

См. также

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

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

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