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

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

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

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

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

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

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

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

• ${\ Displaystyle X = \ {X_ {1}, \ ldots, X_ {n} \}}$ набор переменных,
• ${\ Displaystyle D = \ {D_ {1}, \ ldots, D_ {п} \}}$ представляет собой набор их соответствующих доменов значений, и
• ${\ 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} \ subset X}$${\ displaystyle k}$${\ displaystyle R_ {j}}$${\ displaystyle k}$${\ displaystyle D_ {j}}$${\ displaystyle v}$${\ Displaystyle \ langle t_ {j}, R_ {j} \ rangle}$${\ displaystyle t_ {j}}$${\ displaystyle R_ {j}}$

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

Решение

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

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

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

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

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

Проблемы с решением

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

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

Каждый 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
• Стивен Минтон; Энди Филипс; Марк Д. Джонстон; Филип Лэрд (1993). «Сведение к минимуму конфликтов: эвристический метод исправления ограничений-удовлетворения и задач планирования». Журнал исследований искусственного интеллекта . 58 (1–3): 161–205. CiteSeerX  10.1.1.308.6637 . DOI : 10.1016 / 0004-3702 (92) 90007-к .
• Цанг, Эдвард (1993). Основы удовлетворения ограничений . Академическая пресса. 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). Принципы программирования ограничений . Издательство Кембриджского университета. ISBN  0-521-82583-0
• Лекутр, Кристоф (2009). Сети ограничений: методы и алгоритмы . ISTE / Wiley. ISBN  978-1-84821-106-3
• Томас Федер, Удовлетворение ограничениями: личная точка зрения , рукопись.
• Архив ограничений
• Тесты принудительного выполнения CSP модели RB
• Тесты - XML-представление экземпляров CSP
• XCSP3 - формат на основе XML, предназначенный для представления экземпляров CSP.
• Распространение ограничений - Диссертация Гвидо Такка, дающая хороший обзор теории и проблем реализации