Удовлетворение ограничений: методы и применение в искусственном интеллекте и исследованиях операций.

Введение

В искусственном интеллекте и исследованиях операций, удовлетворение ограничений – это процесс поиска решения посредством набора ограничений, которые накладывают условия, которым должны удовлетворять переменные. Следовательно, решение – это присваивание значений переменным, удовлетворяющих всем ограничениям, то есть точка в допустимой области. Методы, используемые при решении задач удовлетворения ограничений, зависят от типа рассматриваемых ограничений. Часто используются ограничения на конечном домене, настолько, что задачи удовлетворения ограничений обычно отождествляются с задачами, основанными на ограничениях на конечном домене. Такие задачи обычно решаются методами поиска, в частности, с помощью возврата с отслеживанием (backtracking) или локального поиска. Распространение ограничений – это еще одно семейство методов, применяемых к таким задачам; большинство из них являются неполными в общем случае, то есть они могут решить задачу или доказать её неразрешимость, но не всегда. Методы распространения ограничений также используются совместно с поиском для упрощения решаемой задачи. Другие рассматриваемые типы ограничений относятся к действительным или рациональным числам; решение задач с такими ограничениями осуществляется с помощью исключения переменных или симплекс-метода. Удовлетворение ограничениями как общая задача возникло в области искусственного интеллекта в 1970-х годах (см., например). Однако, когда ограничения выражаются в виде многомерных линейных уравнений, определяющих равенства или неравенства, эта область восходит к работам Жозефа Фурье в XIX веке: изобретение Джорджем Данцигом симплекс-метода для линейного программирования (частного случая математической оптимизации) в 1946 году позволило находить допустимые решения для задач, содержащих сотни переменных. В 1980-х и 1990-х годах была разработана возможность встраивания ограничений в языки программирования. Первым языком, специально разработанным со встроенной поддержкой программирования с ограничениями, был Prolog. С тех пор библиотеки программирования с ограничениями стали доступны и на других языках, таких как C++ или Java (например, Choco для Java).

In artificial intelligence and operations research, constraint satisfaction is the process of finding a solution through
a set of constraints that impose conditions that the variables must satisfy. A solution is therefore an assignment of values to the variables that satisfies all constraints—that is, a point in the feasible region. The techniques used in constraint satisfaction depend on the kind of constraints being considered. Often used are constraints on a finite domain, to the point that constraint satisfaction problems are typically identified with problems based on constraints on a finite domain. Such problems are usually solved via search, in particular a form of backtracking or local search. Constraint propagation is another family of methods used on such problems; most of them are incomplete in general, that is, they may solve the problem or prove it unsatisfiable, but not always. Constraint propagation methods are also used in conjunction with search to make a given problem simpler to solve. Other considered kinds of constraints are on real or rational numbers; solving problems on these constraints is done via variable elimination or the simplex algorithm. Constraint satisfaction as a general problem originated in the field of artificial intelligence in the 1970s (see for example ). However, when the constraints are expressed as multivariate linear equations defining (in)equalities, the field goes back to Joseph Fourier in the 19th century: George Dantzig's invention of the simplex algorithm for linear programming (a special case of mathematical optimization) in 1946 has allowed determining feasible solutions to problems containing hundreds of variables. During the 1980s and 1990s, embedding of constraints into a programming language was developed. The first language devised expressly with intrinsic support for constraint programming was Prolog. Since then, constraint programming libraries have become available in other languages, such as C++ or Java (e. g., Choco for Java).

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

Как первоначально определено в искусственном интеллекте, ограничения перечисляют возможные значения, которые набор переменных может принимать в заданном мире. Возможный мир – это полное присваивание значений переменным, представляющее собой один из способов, которым мир (реальный или воображаемый) может существовать. Неформально, конечный домен – это конечный набор произвольных элементов. Задача удовлетворения ограничений на таком домене содержит набор переменных, значения которых могут быть взяты только из этого домена, и набор ограничений, каждое из которых определяет допустимые значения для группы переменных. Решение этой задачи – это присваивание значений переменным, удовлетворяющее всем ограничениям. Иными словами, решение – это способ присвоить значение каждой переменной таким образом, чтобы все ограничения были выполнены этими значениями. В некоторых случаях могут существовать дополнительные требования: может быть интересно не только само решение (и самый быстрый или наиболее вычислительно эффективный способ его достижения), но и то, как оно было получено; например, может потребоваться «наиболее простое» решение («простое» в логическом, а не вычислительном смысле, которое должно быть точно определено). Это часто встречается в логических играх, таких как Судоку. На практике ограничения часто выражаются в компактной форме, а не перечисляются все значения переменных, удовлетворяющие ограничению. Одним из наиболее часто используемых ограничений является (очевидное) требование, что значения затронутых переменных должны быть все различными. Примерами задач, которые можно сформулировать как задачи удовлетворения ограничений, являются задача о восьми ферзях, задача решения Судоку и многие другие логические головоломки, задача булевой выполнимости, задачи планирования, задачи оценки с ограниченной погрешностью и различные задачи на графах, такие как задача раскраски графа. Хотя обычно они не включаются в определение задачи удовлетворения ограничений, арифметические уравнения и неравенства ограничивают значения содержащихся в них переменных и, следовательно, могут рассматриваться как форма ограничений. Их область определения – множество чисел (целых, рациональных или действительных), которое бесконечно: поэтому и сами отношения, задаваемые этими ограничениями, могут быть бесконечными; например, уравнение имеет бесконечное количество пар удовлетворяющих значений. Арифметические уравнения и неравенства часто не рассматриваются в рамках определения «задачи удовлетворения ограничений», которая ограничена конечными доменами. Однако они часто используются в программировании с ограничениями. Можно показать, что арифметические неравенства или уравнения, присутствующие в некоторых типах конечных логических головоломок, таких как Футошики или Какуро (также известные как «кросс-суммы»), могут быть обработаны как неарифметические ограничения (см. «Удовлетворение ограничений на основе шаблонов и логические головоломки»).

As originally defined in artificial intelligence, constraints enumerate the possible values a set of variables may take in a given world. A possible world is a total assignment of values to variables representing a way the world (real or imaginary) could be. Informally, a finite domain is a finite set of arbitrary elements. A constraint satisfaction problem on such domain contains a set of variables whose values can only be taken from the domain, and a set of constraints, each constraint specifying the allowed values for a group of variables. A solution to this problem is an evaluation of the variables that satisfies all constraints. In other words, a solution is a way for assigning a value to each variable in such a way that all constraints are satisfied by these values. In some circumstances, there may exist additional requirements: one may be interested not only in the solution (and in the fastest or most computationally efficient way to reach it) but in how it was reached; e. g. one may want the "simplest" solution ("simplest" in a logical, non computational sense that has to be precisely defined). This is often the case in logic games such as Sudoku. In practice, constraints are often expressed in compact form, rather than enumerating all the values of the variables that would satisfy the constraint. One of the most used constraints is the (obvious) one establishing that the values of the affected variables must be all different. Problems that can be expressed as constraint satisfaction problems are the eight queens puzzle, the Sudoku solving problem and many other logic puzzles, the Boolean satisfiability problem, scheduling problems, bounded error estimation problems and various problems on graphs such as the graph coloring problem. While usually not included in the above definition of a constraint satisfaction problem, arithmetic equations and inequalities bound the values of the variables they contain and can therefore be considered a form of constraints. Their domain is the set of numbers (either integer, rational, or real), which is infinite: therefore, the relations of these constraints may be infinite as well; for example, has an infinite number of pairs of satisfying values. Arithmetic equations and inequalities are often not considered within the definition of a "constraint satisfaction problem", which is limited to finite domains. They are however used often in constraint programming. It can be shown that the arithmetic inequalities or equations present in some types of finite logic puzzles such as Futoshiki or Kakuro (also known as Cross Sums) can be dealt with as non arithmetic constraints (see Pattern Based Constraint Satisfaction and Logic Puzzles).

Решение

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

Сложность

Решение задачи об удовлетворении ограничениям на конечном домене является NP-полной задачей по отношению к размеру домена. Исследования выявили ряд разрешимых частных случаев, некоторые из которых ограничивают допустимые типы ограничений, а другие требуют, чтобы области действия ограничений образовывали дерево, возможно, в переформулированной версии задачи. Также установлены связи между задачей об удовлетворении ограничениям и задачами в других областях, таких как теория конечных моделей.

Программирование ограничений

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

Программирование с логикой ограничений

Логическая программа с ограничениями — это логическая программа, содержащая ограничения в телах клауз. Например, клауза A(X): X>0, B(X) содержит ограничение X>0 в теле. Ограничения могут также присутствовать в цели. Ограничения из цели и клауз, используемых для доказательства цели, накапливаются в набор, называемый хранилищем ограничений. Этот набор содержит ограничения, которые интерпретатор предполагает выполнимыми для продолжения вычислений. Следовательно, если этот набор обнаруживается невыполнимым, интерпретатор осуществляет возврат (backtrack). Уравнения термов, используемые в логическом программировании, рассматриваются как частный случай ограничений, которые могут быть упрощены с помощью унификации. Таким образом, хранилище ограничений можно рассматривать как расширение концепции подстановки, используемой в обычном логическом программировании. Наиболее распространенными видами ограничений, используемых в программировании с ограничениями логики, являются ограничения на целые, рациональные и вещественные числа, а также ограничения на конечные области. Также были разработаны языки конкурентного программирования с ограничениями логики. Они существенно отличаются от неконкурентного программирования с ограничениями логики тем, что предназначены для программирования конкурентных процессов, которые могут не завершаться. Правила обработки ограничений можно рассматривать как форму конкурентного программирования с ограничениями логики, но они также иногда используются в рамках неконкурентного языка программирования с ограничениями логики. Они позволяют переписывать ограничения или выводить новые на основе истинности условий.

Другие языки программирования с ограничениями

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