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

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

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

Удовлетворение ограничений как общая проблема возникла в области искусственного интеллекта в 1970-х годах (см., например, ( Laurière 1978 )). Однако когда ограничения выражаются в виде многомерных линейных уравнений, определяющих (не)равенства, эта область возвращается к Джозефу Фурье в 19 веке: Джорджем Данцигом изобретение симплексного алгоритма для линейного программирования (частный случай математической оптимизации) в 1946 год позволил найти возможные решения задач, содержащих сотни переменных.

В 1980-х и 1990-х годах было разработано встраивание ограничений в язык программирования . Первым языком, специально разработанным со встроенной поддержкой программирования в ограничениях, был Пролог . С тех пор библиотеки программирования в ограничениях стали доступны на других языках, таких как C++ или Java (например, Choco для Java). ).

удовлетворения

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

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

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

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

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

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

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

Решение

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

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

Сложность

Основная статья: Сложность удовлетворения ограничений

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

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

Основная статья: Программирование ограничений

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

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

Основная статья: Программирование логики ограничений

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

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

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

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

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

языки программирования

Инструментарий ограничений — это способ встраивания ограничений в императивный язык программирования . Однако они используются только как внешние библиотеки для кодирования и решения задач. Подход, при котором ограничения интегрируются в императивный язык программирования, использован в языке программирования «Калейдоскоп» .

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

См. также

• Проблема удовлетворения ограничений
• Ограничение (математика)
• Вариант решения
• Проблема логической выполнимости
• Теория принятия решений
• Теории выполнимости по модулю
• Конфигурация на основе знаний

Ссылки

• Апт, Кшиштоф (2003). Принципы программирования в ограничениях . Издательство Кембриджского университета. ISBN  978-0-521-82583-2 .
• Дектер, Рина (2003). Обработка ограничений . Морган Кауфманн. ISBN  978-1-55860-890-0 .
• Динкбас, М.; Симонис, Х.; Ван Хентенрик, П. (1990). «Решение больших комбинаторных задач в логическом программировании» . Журнал логического программирования . 8 (1–2): 75–93. дои : 10.1016/0743-1066(90)90052-7 .
• Фрейдер, Юджин; Макворт, Алан, ред. (1994). Рассуждение, основанное на ограничениях . МТИ Пресс. ISBN  978-0-262-56075-7 .
• Фрювирт, Том; Слим Абденнадер (2003). Основы программирования в ограничениях . Спрингер. ISBN  978-3-540-67623-2 .
• Гесген, Ганс; Герцберг Иоахим (1992). Перспектива рассуждений, основанных на ограничениях . Спрингер. ISBN  978-3-540-55510-0 .
• Джаффар, Джоксан; Майкл Дж. Махер (1994). «Программирование логики ограничений: обзор» . Журнал логического программирования . 19/20: 503–581. дои : 10.1016/0743-1066(94)90033-7 .
• Лорьер, Жан-Луи (1978). «Язык и программа для постановки и решения комбинаторных задач». Искусственный интеллект . 10 (1): 29–127. дои : 10.1016/0004-3702(78)90029-2 .
• Лекутр, Кристоф (2009). Сети ограничений: методы и алгоритмы . ИСТЭ/Уайли. ISBN  978-1-84821-106-3 .
• Марриотт, Ким; Питер Дж. Стаки (1998). Программирование с ограничениями: Введение . МТИ Пресс. ISBN  978-0-262-13341-8 .
• Росси, Франческа; Питер ван Бик; Тоби Уолш, ред. (2006). Справочник по программированию с ограничениями . Эльзевир. ISBN  978-0-444-52726-4 . Архивировано из оригинала 4 октября 2012 г. Проверено 13 октября 2006 г.
• Цанг, Эдвард (1993). Основы удовлетворения ограничениями . Академическая пресса. ISBN  978-0-12-701610-8 .
• Ван Хентенрик, Паскаль (1989). Удовлетворение ограничений в логическом программировании . МТИ Пресс. ISBN  978-0-262-08181-8 .
• Рашиди, Хасан; Цанг, Эдвард. (2012). «Новые модели удовлетворения ограничений для задач оптимизации контейнерных терминалов» . Журнал прикладного математического моделирования . 37 (6): 3601–34. дои : 10.1016/j.apm.2012.07.042 .

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

• Учебное пособие по CSP

Видео

• Лекция доктора Мадху Шармы «Удовлетворение ограничениями» (3:47)
• Введение в проблемы удовлетворения ограничений Эдвард Цанг (7:34)
• Проблемы удовлетворения ограничений Уиллера Рамла (9:18)
• Лекция Индийского технологического института Мадраса о проблемах удовлетворения ограничений (51:59)
• Лекция о CSP (1:16:39)
• Лекция Беркли А.И. «Проблемы удовлетворения ограничений» (1:17:38)
• Аспирантура по AI 5: Удовлетворение ограничений, профессор Маусам (1:34:29)