Удовлетворение ограничений - Constraint satisfaction

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

Методы, используемые для удовлетворения ограничений, зависят от типа рассматриваемых ограничений. Часто используются ограничения в конечной области до такой степени, что проблемы удовлетворения ограничений обычно отождествляются с проблемами, основанными на ограничениях в конечной области. Такие проблемы обычно решаются с помощью поиска , в частности с помощью поиска с возвратом или локального поиска . Распространение ограничений - другие методы, используемые для решения таких задач; большинство из них в целом неполны, то есть могут решить проблему или доказать ее неудовлетворенность, но не всегда. Методы распространения ограничений также используются в сочетании с поиском, чтобы упростить решение данной проблемы. Другие рассматриваемые виды ограничений относятся к действительным или рациональным числам; решение проблем с этими ограничениями выполняется с помощью исключения переменных или симплексного алгоритма .

Удовлетворение ограничений зародилось в области искусственного интеллекта в 1970-х годах (см., Например, ( Laurière 1978 )). В 1980-х и 1990-х годах было разработано встраивание ограничений в язык программирования . Для программирования с ограничениями часто используются языки Prolog и C ++ .

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

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

В некоторых обстоятельствах могут существовать дополнительные требования: кто-то может интересоваться не только решением (и наиболее быстрым или наиболее эффективным с вычислительной точки зрения способом его достижения), но и тем, как оно было достигнуто; например, может потребоваться «простейшее» решение («простейшее» в логическом, не вычислительном смысле, которое должно быть точно определено). Это часто бывает в логических играх, таких как судоку.

На практике ограничения часто выражаются в компактной форме, вместо того, чтобы перечислять все значения переменных, которые удовлетворяли бы ограничению. Одним из наиболее часто используемых ограничений является (очевидное) ограничение, устанавливающее, что значения затронутых переменных должны быть разными.

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

Хотя арифметические уравнения и неравенства обычно не включаются в приведенное выше определение проблемы удовлетворения ограничений, они ограничивают значения переменных, которые они содержат, и поэтому могут считаться формой ограничений. Их область определения - это бесконечное множество чисел (целых, рациональных или действительных): следовательно, отношения этих ограничений также могут быть бесконечными; например, имеет бесконечное количество пар удовлетворяющих значений. Арифметические уравнения и неравенства часто не рассматриваются в рамках определения «проблемы удовлетворения ограничений», которое ограничивается конечными областями. Однако они часто используются в программировании ограничений .

Можно показать, что арифметические неравенства или уравнения, присутствующие в некоторых типах головоломок с конечной логикой, таких как Футошики или Какуро (также известные как перекрестные суммы), могут рассматриваться как неарифметические ограничения (см. Выполнение ограничений на основе шаблонов и Логические головоломки ). .

Решение

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

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

Сложность

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

Ограниченное программирование

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

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

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

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

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

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

  • Решатель ограничений Cassowary , проект с открытым исходным кодом для удовлетворения ограничений (доступный из C, Java, Python и других языков).
  • Comet , коммерческий язык программирования и инструментарий
  • Gecode , портативный набор инструментов с открытым исходным кодом, написанный на C ++, разработанный как высокопроизводительная и высокоэффективная реализация полной теоретической базы.
  • Gelisp , переносимая оболочка с открытым исходным кодом от Gecode to Lisp . http://gelisp.sourceforge.net/
  • IBM ILOG CP Optimizer : библиотеки C ++, Python , Java, .NET (проприетарные, бесплатные для академического использования ). Преемник ILOG Solver / Scheduler, который с 2006 года считался лидером на рынке коммерческого программного обеспечения для программирования с ограничениями.
  • JaCoP , программа решения ограничений Java с открытым исходным кодом.
  • OptaPlanner , еще один решатель ограничений Java с открытым исходным кодом.
  • Koalog , коммерческий решатель ограничений на основе Java.
  • logilab-constraint , решатель ограничений с открытым исходным кодом, написанный на чистом Python с алгоритмами распространения ограничений.
  • Minion , решатель ограничений с открытым исходным кодом, написанный на C ++, с небольшим языком для определения моделей / проблем.
  • ZDC, программа с открытым исходным кодом, разработанная в рамках проекта Computer-Aided Constraint Satisfaction Project для моделирования и решения проблем удовлетворения ограничений.

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

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

Ограничения также были встроены в функциональные языки программирования .

Смотрите также

Рекомендации

Внешние ссылки

Видео