В искусственном интеллекте и исследовании операций удовлетворение ограничений — это процесс поиска решения с помощью набора ограничений , которые накладывают условия, которым должны удовлетворять переменные . [1] Таким образом, решение — это присвоение значений переменным, которое удовлетворяет всем ограничениям, то есть точка в допустимой области .
Методы, используемые для удовлетворения ограничений, зависят от типа рассматриваемых ограничений. Часто используются ограничения на конечную область , вплоть до того, что проблемы удовлетворения ограничений обычно отождествляются с проблемами, основанными на ограничениях на конечную область. Такие проблемы обычно решаются с помощью поиска , в частности, формы возврата или локального поиска . Распространение ограничений — это еще одно семейство методов, используемых для таких проблем; большинство из них в целом неполны, то есть они могут решить проблему или доказать ее невыполнимость, но не всегда. Методы распространения ограничений также используются в сочетании с поиском, чтобы упростить решение данной проблемы. Другие рассматриваемые виды ограничений — это ограничения на действительные или рациональные числа; решение проблем с этими ограничениями выполняется с помощью исключения переменных или симплексного алгоритма .
Удовлетворение ограничений как общая проблема возникла в области искусственного интеллекта в 1970-х годах (см., например, (Laurière 1978)). Однако, когда ограничения выражаются в виде многомерных линейных уравнений, определяющих (не)равенства, область возвращается к Жозефу Фурье в 19 веке: изобретение Джорджем Данцигом симплексного алгоритма для линейного программирования (частного случая математической оптимизации) в 1946 году позволило определять допустимые решения задач, содержащих сотни переменных.
В 1980-х и 1990-х годах было разработано встраивание ограничений в язык программирования . Первым языком, специально разработанным с внутренней поддержкой программирования ограничений, был Prolog . С тех пор библиотеки программирования ограничений стали доступны и в других языках, таких как C++ или Java (например, Choco для Java [2] ).
Как изначально было определено в искусственном интеллекте, ограничения перечисляют возможные значения, которые набор переменных может принимать в данном мире. Возможный мир — это общее назначение значений переменным, представляющее способ, которым мир (реальный или воображаемый) мог бы быть. [3] Неформально, конечная область — это конечный набор произвольных элементов. Задача удовлетворения ограничений в такой области содержит набор переменных, значения которых могут быть взяты только из области, и набор ограничений, каждое из которых определяет допустимые значения для группы переменных. Решением этой проблемы является оценка переменных, которая удовлетворяет всем ограничениям. Другими словами, решение — это способ назначения значения каждой переменной таким образом, чтобы все ограничения удовлетворялись этими значениями.
В некоторых случаях могут существовать дополнительные требования: может быть интересно не только решение (и самый быстрый или самый вычислительно эффективный способ его достижения), но и то, как оно было достигнуто; например, может потребоваться «простейшее» решение («простейшее» в логическом, невычислительном смысле, который должен быть точно определен). Это часто бывает в логических играх, таких как судоку .
На практике ограничения часто выражаются в компактной форме, а не перечислением всех значений переменных, которые удовлетворяли бы ограничению. Одним из наиболее используемых ограничений является (очевидное) ограничение, устанавливающее, что значения затронутых переменных должны быть все разными.
Проблемы, которые можно выразить как проблемы удовлетворения ограничений, — это головоломка «Восемь королев» , задача решения судоку и многие другие логические головоломки, задача выполнимости булевых уравнений , задачи составления расписаний , задачи оценки ограниченной ошибки и различные задачи на графах, такие как задача раскраски графа .
Хотя обычно они не включены в приведенное выше определение проблемы удовлетворения ограничений, арифметические уравнения и неравенства ограничивают значения переменных, которые они содержат, и поэтому могут считаться формой ограничений. Их областью определения является множество чисел (целых, рациональных или действительных), которое бесконечно: поэтому отношения этих ограничений также могут быть бесконечными; например, имеет бесконечное число пар удовлетворяющих значений. Арифметические уравнения и неравенства часто не рассматриваются в определении «задачи удовлетворения ограничений», которая ограничена конечными областями. Однако они часто используются в программировании ограничений .
Можно показать, что арифметические неравенства или уравнения, присутствующие в некоторых типах конечных логических головоломок, таких как Футошики или Какуро (также известных как перекрестные суммы), можно рассматривать как неарифметические ограничения (см. Удовлетворение ограничений на основе шаблонов и логические головоломки [4] ).
Задачи удовлетворения ограничений в конечных областях обычно решаются с использованием формы поиска . Наиболее используемые методы — это варианты обратного отслеживания , распространения ограничений и локального поиска . Эти методы применяются к задачам с нелинейными ограничениями.
Алгоритм исключения переменных и симплекс-алгоритм используются для решения линейных и полиномиальных уравнений и неравенств, а также задач, содержащих переменные с бесконечной областью определения. Обычно они решаются как задачи оптимизации , в которых оптимизируемой функцией является число нарушенных ограничений.
Решение проблемы удовлетворения ограничений в конечной области является NP-полной проблемой относительно размера области. Исследования показали ряд поддающихся решению подслучаев, некоторые из которых ограничивают допустимые отношения ограничений, некоторые требуют, чтобы области ограничений сформировали дерево, возможно, в переформулированной версии проблемы. Исследования также установили связи проблемы удовлетворения ограничений с проблемами в других областях, таких как теория конечных моделей .
Программирование в ограничениях — это использование ограничений в качестве языка программирования для кодирования и решения проблем. Это часто делается путем встраивания ограничений в язык программирования , который называется основным языком. Программирование в ограничениях возникло из формализации равенств термов в Prolog II , что привело к общей структуре для встраивания ограничений в язык логического программирования . Наиболее распространенными основными языками являются Prolog , C++ и Java , но использовались и другие языки.
Программа логики ограничений — это логическая программа , которая содержит ограничения в телах предложений. Например, предложение A(X):-X>0,B(X)— это предложение, содержащее ограничение X>0в теле. Ограничения также могут присутствовать в цели. Ограничения в цели и в предложениях, используемых для доказательства цели, накапливаются в наборе, называемом хранилищем ограничений . Этот набор содержит ограничения, которые интерпретатор предположил выполнимыми, чтобы продолжить оценку. В результате, если этот набор обнаруживается невыполнимым, интерпретатор возвращается назад. Уравнения термов, используемые в логическом программировании, считаются особой формой ограничений, которую можно упростить с помощью унификации . В результате хранилище ограничений можно считать расширением концепции подстановки , которая используется в обычном логическом программировании. Наиболее распространенными видами ограничений, используемыми в программировании логики ограничений, являются ограничения по целым/рациональным/действительным числам и ограничения по конечным областям.
Также были разработаны языки программирования с параллельной логикой ограничений . Они существенно отличаются от непараллельного программирования с логикой ограничений тем, что нацелены на программирование параллельных процессов , которые могут не завершиться. Правила обработки ограничений можно рассматривать как форму программирования с параллельной логикой ограничений, но иногда они также используются в языке программирования с непараллельной логикой ограничений. Они позволяют переписывать ограничения или выводить новые на основе истинности условий.
Наборы инструментов для удовлетворения ограничений представляют собой программные библиотеки для императивных языков программирования , которые используются для кодирования и решения задачи удовлетворения ограничений.
Инструменты ограничений — это способ встраивания ограничений в императивный язык программирования . Однако они используются только как внешние библиотеки для кодирования и решения проблем. Подход, при котором ограничения интегрируются в императивный язык программирования, используется в языке программирования Kaleidoscope .
Ограничения также были встроены в языки функционального программирования .
