Задача удовлетворения ограничений

Зада́чи удовлетворе́ния ограниче́ний (ЗУО, англ. Constraint satisfaction problem, CSP) — класс математических проблем, определённых как совокупность объектов, состояние которых должно удовлетворять ряду ограничений. ЗУО представляет сущности проблемы как однородный набор ограничений, накладываемых на переменные, которые решаются методами удолетворения ограничений. ЗУО является предметом интенсивных исследований как в области искусственного интеллекта, так и в исследовании операций, поскольку закономерности в формулировке этих задач составляют общую основу для анализа и решения проблем во многих не связанных друг с другом областях. ЗУО часто имеют высокую сложность, что требует сочетания эвристических и комбинаторных методов поиска для быстрого решения. Примеры просто формулируемых задач, которые могут рассматриваться как задачи удовлетворения ограничений: задача о восьми ферзях, теорема о четырёх красках, судоку.

В общем случае проблема удовлетворения ограничений может быть сложнее и не сводиться к этим простым системам.

Формальное определение

Формально задача удовлетворения ограничений определяется тройкой $\langle X,D,C\rangle$, где $X$ — множество переменных, $D$ — область значений и $C$ — множество ограничений. Каждое ограничение, в свою очередь, является парой $\langle t,R\rangle$ (обычно представляются матрицей), где $t$ — кортеж из $n$ переменных, а $R$ — $n$-местное отношение на $D$. Оценка переменной — это функция, отображающая множество переменных в область значений: $v:X\rightarrow D$. Оценка $v$ удовлетворяет ограничению $\langle (x_{1},\ldots ,x_{n}),R\rangle$, если $(v(x_{1}),\ldots ,v(x_{n}))\in R$. Решение — это оценка, которая удовлетворяет всем ограничениям.

Решение

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

Поиск с возвратом — это рекурсивный алгоритм. Он поддерживает частичное определение переменных. Первоначально все переменные не определены. На каждом шаге выбирается переменная и последовательно перебираются все её возможные значения. Каждое значение из последовательности согласуется с ограничениями; при несоответствии значения ограничениям рекурсивный вызов не выполняется. Когда все значения были просмотрены, алгоритм возвращается. В этом простом алгоритме с возвратом под согласованием понимается удовлетворение всех ограничений, все переменные которых были определены. Существует несколько вариантов возврата. Поиск с возвратом повышает эффективность проверки соответствия. Поиск с возвратом позволяет в некоторых случаях ускорить поиск за счёт исключения «более чем одной переменной».

Теоретические аспекты задачи удовлетворения ограничений

Проблемы решения

Задачи удовлетворения ограничений также изучаются в теории сложности вычислений и теории конечных моделей. Важный вопрос заключается в том, что для каждого набора отношений, множество всех задач удовлетворения ограничений, которое может быть представлено только с помощью отношений из этого набора, является P- или NP-полной задачей. Если такая дихотомическая теорема справедлива, то задачи удовлетворения ограничений обеспечивают одно из самых больших известных подмножеств сложности NP, которое позволяет избежать промежуточных задач NP-сложности, существование которой было продемонстрировано в теореме Ладнера в предположении, что P ≠ NP. Дихотомическая теорема Шефера рассматривает случай, когда все имеющиеся отношения являются логическими операторами, то есть множество значений имеет размер 2. Дихотомическая теорема Шефера была обобщена на более широкий класс отношений.

Литература

• Рассел С. Искусственный интеллект: современный подход. 2е изд.: Пер. с англ. / С. Рассел, П. Норвиг М.: Вильямс, 2006. 1408 с.
• Щербина О.А. Удовлетворение ограничений и программирование в ограничениях // Интеллектуальные системы. 2011. 15 (N 1-4). С. 53-170
• Dechter R. Constraint Processing / R. Dechter. Morgan Kaufmann, 2003. 481 p.
• Montanari U. Networks of constraints: Fundamental properties and applications to picture processing // Information Sciences. 1974. 7(2). P. 95-132.
• Ушаков Д.М., Телерман В.В. Системы программирования в ограничениях (обзор) // Системная информатика: Сб. науч. тр. Новосибирск: Наука, 2000. Вып.7: Проблемы теории и методологии создания параллельных и распределенных систем. С. 275-310.
• Tsang Edward Foundations of Constraint Satisfaction. — Academic Press, 1993. ISBN 0-12-701610-4
• (December 2009) «A Rendezvous of Logic, Complexity, and Algebra». ACM Computing Surveys (ACM) 42 (1): 1–32. DOI:10.1145/1592451.1592453.
• Dechter Rina Constraint processing. — Morgan Kaufmann, 2003. ISBN 1-55860-890-7
• Apt Krzysztof Principles of constraint programming. — Cambridge University Press, 2003. ISBN 0-521-82583-0
• Lecoutre Christophe Constraint Networks: Techniques and Algorithms. — ISTE/Wiley, 2009. ISBN 978-1-84821-106-3
• Tomás Feder, Constraint satisfaction: a personal perspective Архивировано из первоисточника 19 січня 2021., manuscript.

Одним из источников, использованных при создании данной статьи, является статья из википроекта «Руниверсалис» («Руни», руни.рф) под названием «Задача удовлетворения ограничений», расположенная по адресу: — https://руни.рф/index.php/Задача_удовлетворения_ограничений Материал указанной статьи полностью или частично использован в Циклопедии по лицензии CC BY-SA. Всем участникам Руниверсалиса предлагается прочитать «Обращение к участникам Руниверсалиса» основателя Циклопедии и «Почему Циклопедия?».