Главная arrow Поиск arrow Удовлетворения ограничений
Как начинался компьютер
Компьютерная революция
Двоичный код
Разработки военных лет
Интегральные микросхемы
Микрокомпьютер
Персоны
Сеть
Язык компьютера
Развитие ПО
Гибкие системы
Средства разработки
Информатика
Вычислительная наука
Операционные системы
Искусственный интеллект
Предыстория
Поиск
Знания и рассуждения
Логика
Робототехника
 

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

Формально говоря, любая задача удовлетворения ограничений (Constraint Satisfaction Problem— CSP) определена множеством переменных, X1, X2,…, Xn, и множеством ограничений, C1, C2,…, Cm. Каждая переменная Xi имеет непустую область определения Di возможных значений. Каждое ограничение Ci включает некоторое подмножество переменных и задает допустимые комбинации значений для этого подмножества.

Состояние задачи определяется путем присваивания значений некоторым или всем этим переменным, {Xi = vi, Xj = vj,...}. Присваивание, которое не нарушает никаких ограничений, называется совместимым, или допустимым присваиванием. Полным называется такое присваивание, в котором участвует аждая переменная, а решением задачи CSP является полное присваивание, которое довлетворяет всем ограничениям. Кроме того, для некоторых задач CSP требуется найти решение, которое максимизирует целевую функцию.

Как же все это описание перевести на язык практики? Предположим, что устав от Румынии, мы рассматриваем карту Австралии, на которой показаны все ее штаты и территории, и что мы получили задание раскрасить каждый регион красный, зеленый или синий цвет таким способом, чтобы ни одна пара соседних регионов не имела одинаковый цвет. Чтобы сформулировать это задание в виде задачи CSP, определим в качестве переменных сокращенные обозначения этих регионов: WA, NT, Q, NSW, V, SA и T. Областью определения каждой переменной является множество цветов {red, green, blue}. Ограничения требуют, чтобы все пары соседних регионов имели разные цвета; например, допустимыми комбинациями для WA и NT являются следующие пары:


{{red,green),{red,blue), {green,red),{green,blue),{blue,red), {blue,green)}


(Это ограничение можно также представить более сжато в виде неравенства WA ≠ NT, при условии, что в данном алгоритме удовлетворения ограничений предусмотрен некоторый способ вычисления таких выражений.) Количество возможных решений достаточно велико; например, одним из таких решений является следующее:


{WA=red, NT= green, Q=red, NSW=green, V=red, SA=blue, T=red}


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

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

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

Пример определения задачи CSP: основные штаты и территории на карте Австралии (а); раскраска этой карты может рассматриваться как задача удовлетворения ограничений; задание остоит в том, чтобы назначить цвет каждому региону так, что ни одна пара соседних регионов е будет иметь одинаковый цвет; рассматриваемая задача раскраски карты, представленная в виде графа ограничений (б)

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

  • Начальное состояние. Пустое присваивание {}, в котором ни одной переменной не присвоено значение.
  • Функция определения преемника. Значение может быть присвоено любой переменной с неприсвоенным значением, при условии, что переменная не удет конфликтовать с другими переменными, значения которым были
  • присвоены ранее.
  • Проверка цели. Текущее присваивание является полным.
  • Стоимость пути. Постоянная стоимость (например, 1) для каждого этапа.

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

Задачи CSP простейшего вида характеризуются тем, что в них используются еременные, которые являются дискретными и имеют конечные области определения. К такому виду относится задача раскраски карты. Задача с восемью ферзями, также может рассматриваться как задача CSP с конечной областью определения, где переменные Q1,...,Q8 представляют собой позиции каждого ферзя на столбцах 1,...,8, а каждая переменная имеет область определения {1,2,3,4,5,6,7,8}.

Если максимальный размер области определения любой переменной в задаче CSP равен d, то количество возможных полных присваиваний измеряется величиной O(dn), т.е. зависит экспоненциально от количества переменных. К категории задач CSP с конечной областью определения относятся булевы задачи CSP, в которых переменные могут иметь значения либо true, либо false. Булевы задачи CSP включают в качестве частных случаев некоторые NP-полные задачи, такие как 3SAT.

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

Дискретные переменные могут также иметь бесконечные области определения, например, такие, как множество всех целых чисел или множество всех строк. В частности, при календарном планировании строительных работ дата начала каждой работы представляет собой переменную, а ее возможными значениями являются целочисленные интервалы времени в сутках, отсчитываемые от текущей даты. При решении задач с бесконечными областями определения больше нет возможности описывать ограничения, перечисляя все допустимые
комбинации значений. Вместо этого должен использоваться язык ограничений. Например, если работа Job1 которая занимает пять дней, должна предшествовать работе Job3, то для описания этого условия потребуется язык ограничений, представленных в виде алгебраических неравенств, таких как StartJob1 + 5 ≤ StartJob3.

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

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

Кроме исследования типов переменных, которые могут присутствовать в задачах GSP, полезно заняться изучением типов ограничений. Простейшим типом ограничения является унарное ограничение, которое ограничивает значение единственной вреременной. Например, может оказаться, что жители штата Южная Австралия очень не любят зеленый цвет, {green). Каждое унарное ограничение можно устранить, выполняя предварительную обработку области определения соответствующей переменной, чтобы удалить любое значение, нарушающее это ограничение. Бинарное ограничение связывает между собой две переменные. Например, бинарным ограничением вляется SA ≠ NW.

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

Одним из известных примеров таких задач являются криптоарифметические головоломки, называемые также числовыми ребусами. Обычно предъявляется требование, чтобы каждая буква в криптоарифметической головоломке редставляла отдельную цифру. В случае задачи, показанной на рисунке а, такое требование может быть выражено с помощью ограничения с шестью переменными Alldiff(F, T, U, W, R, O). Иным образом это требование может быть представлено в виде коллекций бинарных ограничений, таких как F ≠ T. Ограничения сложения для четырех столбцов этой головоломки также включают несколько переменных и могут быть записаны следующим образом:

O + O = R + 10 X1

X1 + W + W = U + 10 X2

X2 + T + T = O + 10 X3

X3 = F

где X1, X2 и X3 вспомогательные переменные, представляющие цифру (0 или 1), которая переносится в следующий столбец. Ограничения высокого порядка могут быть представлены в виде ^ гиперграфа ограничений, подобного приведенному на рисунке. Внимательный читатель заметит, что ограничение Alldiff может быть разбито на бинарные ограничения — F ≠ T, F ≠ U т.д. И действительно каждое ограничение высокого порядка с конечной областью определения можно свести к множеству бинарных ограничений, введя достаточное количество вспомогательных переменных. В связи с этим, будут рассматриваться только бинарные ограничения.

Пример криптоарифметической задачи: каждая буква обозначает отдельную цифру; задание состоит в том, чтобы найти такую замену букв цифрами, чтобы результирующее выражение суммирования было арифметически правильным, с дополнительным ограничением, что аличие ведущих нулей не допускается (а); гиперграф ограничений для той криптоарифметической задачи, на котором показано ограничение lldif f, а также ограничения сложения по столбцам; каждое ограничение обозначено квадратом, который соединен с ограничиваемыми им переменными (б)

Все ограничения, рассматривавшиеся до сих пор, были абсолютными ограничениями, нарушение которых равносильно тому, что какое-то потенциальное ешение больше не рассматривается как таковое. С другой стороны, во многих еальных задачах CSP применяются ограничения предпочтения, которые указывают, какие решения являются предпочтительными. Например, в задаче составления расписания занятий в университете может потребоваться учесть, что профессор X предпочитает проводить занятия по утрам, а профессор Y — после полудня. Расписание занятий, в котором предусмотрено проведение профессором X занятия в 14:00, все еще может рассматриваться как решение (если не окажется, что профессор X должен в это время председательствовать на заседании кафедры), но уже не будет оптимальным. Ограничения предпочтения часто можно закодировать как стоимости присваиваний отдельных переменных; например, за назначение профессору X послеполуденного интервала придется заплатить 2 пункта, которые будут учтены в суммарном значении целевой функции, в то время как тренний интервал имеет стоимость 1 пункт. При использовании такой формулировки задачи CSP с предпочтениями можно решать, используя методы поиска с птимизацией, либо основанные на поиске пути, либо локальные. Подобные задачи CSP в данной главе больше не рассматриваются, но в разделе с библиографическими заметками приведены некоторые ссылки.