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

Введение

Одной из важных задач искусственного интеллекта (ИИ) является задача удовлетворения ограничений (УО) (constraint satisfaction problem). Теория УО предлагает удобный аппарат и простую формальную схему для представления и решения комбинаторных задач ИИ.

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

Проблема существования решений задачи УО является NP-полной.

Тесно связано с теорией УО программирование в ограничениях, которое является парадигмой программирования для декларативного описания и эффективного решения комбинаторных задач. Многие классические комбинаторные задачи, такие как известная теорема Ферма, задача выполнимости (SAT) из пропозициональной логики, задача раскраски графа и задача изоморфизма графов из теории графов могут формулироваться в виде задач УО (ЗУО). Остановимся подробнее на одной из давно поставленных задач в математике - задаче о раскраске графа, частным случаем которой является известная задача о раскраске карты. Формулировка задачи о раскраске в виде задачи УО ставит в соответствие вершинам раскрашиваемого графа переменные, возможные цвета представляют собой домены (области определения) переменных, а ограничения-неравенства между смежными вершинами являются ограничениями задачи.

Разумеется, здесь невозможно подробно описать все аспекты и направления теории удовлетворения ограничений и программирования в ограничениях, поэтому более полную информацию и библиографию можно найти в переводной монографии Рассел С., Норвиг П., в которой освещаются вопросы УО и в обзоре О.А.Щербины.

Обзор основных направлений программирования в ограничениях до 2000 г. сделан в работе Ушакова и Телермана (2000).

История

Коснемся вначале терминологии и истории возникновения методов УО. Montanari предложил использовать модели УО для описания ряда комбинаторных задач, возникающих при компьютерной обработке изображений, и назвал эти задачи УО «сетями ограничений» (networks of constraints). Это связано с тем, что систему ограничений можно представить в виде неориентированного графа с вершинами-переменными и ребрами, соответствующими ограничениям между двумя переменными. По мнению Dechter, сети ограничений являются графовым представлением, используемым для поиска стратегий решения задач УО. Достаточно быстро этот подход был использован для решения гораздо более широкого класса задач. В научной литературе используются оба этих термина сети ограничений и задачи удовлетворения ограничений.

Более формально, задача удовлетворения ограничений (УО) представляет собой кортеж $P = <X,D,C>$, где $X$ - множество переменных, $D$ - множество доменов значений переменных, $C$ - множество ограничений.

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

Приведем ряд примеров, иллюстрирующих постановки задач УО в других областях математики.

Задачи оптимизации и задачи УО

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

Пример 1. Наиболее тривиальным алгебраическим примером задачи УО является задача решения системы уравнений. Дана система линейных уравнений над конечным полем $F$. Имеет ли она решение? Ясно, что в этом примере каждое отдельное уравнение является ограничением, причем переменные уравнения образуют диапазон, а множество всех кортежей, соответствующих решениям уравнения, образует отношение ограничения.

Пример 2. Задача стандартной пропозициональной 3-выполнимости (3-SAT) определяется заданием формулы пропозициональной логики, состоящей из конъюнкции дизъюнктов, причем каждый дизъюнкт содержит 3 литерала (литерал - это переменная или ее отрицание), и ответом на вопрос, имеются ли значения переменных, которые делают формулу истинной. Пусть $\Phi = {\phi _{\rm{1}}} \wedge \ldots \wedge {\phi _n}$ - такая формула, где ${\phi _i}$ - дизъюнкты. Задача выполнимости для $\Phi$ может быть выражена в виде задачи УО $\left( {X,\,\left\{ {0,\,1} \right\},\,C} \right)$, где $X$ - множество всех переменных в формуле, а $C$ - множество ограничений $\left\{ {\left( {{s_1},\,{\rho _1}} \right), \ldots ,\,\left( {{s_n},\,{\rho _n}} \right)} \right\}$, где каждое ограничение $\left( {{s_k},\,{\rho _k}} \right)$ построено следующим образом: ${s_k}$ - список переменных, входящих в ${\phi _k}$, а ${\rho _k}$ состоит из всех кортежей, которые делают дизъюнкт ${\phi _k}$ истинным $\left( {k = 1,\, \ldots ,\,n} \right)$.

Решения этой задачи УО - присвоения значений переменным, которые делают формулу $\Phi$ истинной. Значит, любая задача 3-выполнимости может быть выражена в виде задачи УО.

Задача УО может быть также преобразована в задачу выполнимости SAT. Для данной ЗУО построим задачу выполнимости SAT следующим образом. Введем переменных . Переменные принимают значение «истина» тогда и только тогда, когда переменной присвоено значение . Для каждой переменной добавляются клаузы (дизъюнкты) для всех пар значений одной и той же переменной, чтобы гарантировать невозможность одновременного принятия переменной двух различных значений. Добавляется дизъюнкт , чтобы гарантировать, что переменной присвоено хотя бы одно значение.

Пример 3. Любая конкретная задача УО может быть выражена в логической форме. Действительно, используя стандартное соответствие между отношениями и предикатами, можно переписать задачу УО в виде формулы первого порядка , где предикаты на и означает предикат , примененный к кортежу переменных . Вопрос состоит в том, является ли эта формула выполнимой. Эта задача обычно используется в теории баз данных, поскольку она соответствует оценке конъюнктивного запроса, как показано в следующем примере.

Пример 4. Реляционная база данных может быть рассмотрена как конечное множество таблиц. Таблица состоит из схемы и конкретных данных, где схема конечное множество атрибутов, причем каждый атрибут имеет соответствующее ему множество возможных значений, называемое доменом. Конкретные данные это конечное множество строк, где каждая строка отображение, ставящее в соответствие каждому атрибуту схемы значение из ее домена. Стандартной задачей для реляционных баз данных является задача оценки конъюнктивного запроса, в которой спрашивается, имеет ли решение конъюнктивный запрос, т.е. запрос вида , где атомарные формулы. Конъюнктивный запрос над реляционной базой данных соответствует конкретному примеру задачи УО, что достигается простой заменой терминов: «атрибуты» заменяются на «переменные», «таблицы» - на «ограничения», «схема» - на «диапазон», «конкретные данные» на «отношение ограничения», а «строки» - на «кортежи». Значит, конъюнктивный запрос эквивалентен конкретному примеру задачи УО, переменные которой – это атрибуты запроса. Для каждой атомарной формулы в запросе найдется ограничение такое, что диапазон ограничения - это список переменных формулы и отношение ограничения - это множество моделей .

Литература

• Рассел С. Искусственный интеллект: современный подход. 2е изд.: Пер. с англ. / С. Рассел, П. Норвиг М.: Вильямс, 2006. 1408 с.
• Щербина О.А. Удовлетворение ограничений и программирование в ограничениях, препринт, 2012.
• 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.