Задачи удовлетворения ограничений: обзор и методы решения

Введение

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

Set of objects whose state must satisfy limits

Constraint satisfaction problems (CSPs) are mathematical questions defined as a set of objects whose state must satisfy a number of constraints or limitations. CSPs represent the entities in a problem as a homogeneous collection of finite constraints over variables, which is solved by constraint satisfaction methods. CSPs are the subject of research in both artificial intelligence and operations research, since the regularity in their formulation provides a common basis to analyze and solve problems of many seemingly unrelated families. CSPs often exhibit high complexity, requiring a combination of heuristics and combinatorial search methods to be solved in a reasonable time. Constraint programming (CP) is the field of research that specifically focuses on tackling these kinds of problems. Additionally, the Boolean satisfiability problem (SAT), satisfiability modulo theories (SMT), mixed integer programming (MIP) and answer set programming (ASP) are all fields of research focusing on the resolution of particular forms of the constraint satisfaction problem. Examples of problems that can be modeled as a constraint satisfaction problem include:

Type inference
Eight queens puzzle
Map coloring problem
Maximum cut problem
Sudoku, crosswords, futoshiki, Kakuro (Cross Sums), Numbrix/Hidato and many other logic puzzles

These are often provided with tutorials of CP, ASP, Boolean SAT and SMT solvers. In the general case, constraint problems can be much harder, and may not be expressible in some of these simpler systems. "Real life" examples include automated planning, lexical disambiguation, musicology, product configuration and resource allocation. The existence of a solution to a CSP can be viewed as a decision problem. This can be decided by finding a solution, or failing to find a solution after exhaustive search (stochastic algorithms typically never reach an exhaustive conclusion, while directed searches often do, on sufficiently small problems). In some cases the CSP might be known to have solutions beforehand, through some other mathematical inference process.

Вывод типов
Задача восьми ферзей
Задача раскраски карты
Задача о максимальном разрезе
Судоку, кроссворды, футошики, Какуро (Кросс-суммы), Numbrix/Hidato и многие другие логические головоломки.

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

Решение

Проблемы удовлетворения ограничений на конечных доменах обычно решаются с помощью поиска. Наиболее часто используемыми техниками являются варианты обратного отслеживания, распространения ограничений и локального поиска. Эти техники также часто комбинируются, как, например, в методе VLNS, а текущие исследования включают в себя и другие технологии, такие как линейное программирование. Обратное отслеживание – это рекурсивный алгоритм, поддерживающий частичное назначение переменных. Изначально все переменные не назначены. На каждом шаге выбирается переменная, и ей поочередно присваиваются все возможные значения. Для каждого значения проверяется согласованность частичного назначения с ограничениями; в случае согласованности выполняется рекурсивный вызов. Когда все значения опробованы, алгоритм осуществляет возврат (backtracks). В этом базовом алгоритме обратного отслеживания согласованность определяется как удовлетворение всех ограничений, переменные которых все назначены. Существует несколько вариантов обратного отслеживания. Backmarking повышает эффективность проверки согласованности. Backjumping позволяет сохранить часть поиска, осуществляя возврат "более чем на одну переменную" в некоторых случаях. Обучение ограничениям выводит и сохраняет новые ограничения, которые впоследствии могут быть использованы для исключения части поиска. Look-ahead также часто используется в обратном отслеживании для попытки предвидеть последствия выбора переменной или значения, тем самым иногда заранее определяя, является ли подзадача выполнимой или невыполнимой. Методы распространения ограничений – это методы, используемые для модификации задачи удовлетворения ограничений. Точнее, это методы, обеспечивающие форму локальной согласованности, которая представляет собой условия, связанные с согласованностью группы переменных и/или ограничений. Распространение ограничений имеет различные применения. Во-первых, оно преобразует задачу в эквивалентную, но обычно более простую для решения. Во-вторых, оно может доказать выполнимость или невыполнимость задачи. Это не гарантируется в общем случае, однако всегда происходит для некоторых форм распространения ограничений и/или для определенных типов задач. Наиболее известными и используемыми формами локальной согласованности являются согласованность дуг, гипер-согласованность дуг и согласованность путей. Наиболее популярным методом распространения ограничений является алгоритм AC-3, обеспечивающий согласованность дуг. Методы локального поиска – это неполные алгоритмы выполнимости. Они могут найти решение задачи, но могут оказаться безуспешными даже в случае выполнимой задачи. Они работают путем итеративного улучшения полного назначения переменных. На каждом шаге изменяется небольшое число переменных, с общей целью увеличения количества удовлетворяемых ограничений. Алгоритм min-conflicts – это алгоритм локального поиска, специфичный для задач CSP, и основан на этом принципе. На практике локальный поиск хорошо работает, когда на эти изменения также влияют случайные выборы. Разработана интеграция поиска с локальным поиском, что привело к созданию гибридных алгоритмов.

Constraint satisfaction problems on finite domains are typically solved using a form of search. The most used techniques are variants of backtracking, constraint propagation, and local search. These techniques are also often combined, as in the VLNS method, and current research involves other technologies such as linear programming. Backtracking is a recursive algorithm. It maintains a partial assignment of the variables. Initially, all variables are unassigned. At each step, a variable is chosen, and all possible values are assigned to it in turn. For each value, the consistency of the partial assignment with the constraints is checked; in case of consistency, a recursive call is performed. When all values have been tried, the algorithm backtracks. In this basic backtracking algorithm, consistency is defined as the satisfaction of all constraints whose variables are all assigned. Several variants of backtracking exist. Backmarking improves the efficiency of checking consistency. Backjumping allows saving part of the search by backtracking "more than one variable" in some cases. Constraint learning infers and saves new constraints that can be later used to avoid part of the search. Look ahead is also often used in backtracking to attempt to foresee the effects of choosing a variable or a value, thus sometimes determining in advance when a subproblem is satisfiable or unsatisfiable. Constraint propagation techniques are methods used to modify a constraint satisfaction problem. More precisely, they are methods that enforce a form of local consistency, which are conditions related to the consistency of a group of variables and/or constraints. Constraint propagation has various uses. First, it turns a problem into one that is equivalent but is usually simpler to solve. Second, it may prove satisfiability or unsatisfiability of problems. This is not guaranteed to happen in general; however, it always happens for some forms of constraint propagation and/or for certain kinds of problems. The most known and used forms of local consistency are arc consistency, hyper arc consistency, and path consistency. The most popular constraint propagation method is the AC 3 algorithm, which enforces arc consistency. Local search methods are incomplete satisfiability algorithms. They may find a solution of a problem, but they may fail even if the problem is satisfiable. They work by iteratively improving a complete assignment over the variables. At each step, a small number of variables are changed in value, with the overall aim of increasing the number of constraints satisfied by this assignment. The min conflicts algorithm is a local search algorithm specific for CSPs and is based on that principle. In practice, local search appears to work well when these changes are also affected by random choices. An integration of search with local search has been developed, leading to hybrid algorithms.

Проблемы принятия решений

CSP также изучаются в теории вычислительной сложности и теории конечных моделей. Важная теорема о дихотомии утверждает, что для каждого набора отношений множество всех задач CSP, представимых только отношениями из этого набора, либо находится в классе P, либо является NP-полным. Таким образом, CSP предоставляют одно из крупнейших известных подмножеств NP, избегающее NP-полных задач промежуточной сложности, существование которых было показано теоремой Ладнера при условии, что P ≠ NP. Теорема о дихотомии Шефера рассматривает случай, когда все доступные отношения являются булевыми операциями, то есть для области определения размера 2. Теорема о дихотомии Шефера впоследствии была обобщена на более широкий класс отношений, а полная теорема о дихотомии была впервые сформулирована как гипотеза Федера — Варди и окончательно доказана независимо Андреем Булатовым и Дмитрием Жуком. Большинство известных разрешимых классов задач CSP — это те, у которых гиперграф ограничений имеет ограниченную древесную ширину (и нет ограничений на набор отношений ограничений), или ограничения имеют произвольную форму, но существуют существенные не унарные полиморфизмы набора отношений ограничений. Каждую задачу CSP также можно рассматривать как задачу включения конъюнктивных запросов.

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

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

Варианты

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

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

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

Гибкие CSP

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

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

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