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