Искусственный интеллект. Современный подход

ЗАДАЧИ УДОВЛЕТВОРЕНИЯ ОГРАНИЧЕНИЙ

Бэтой главе показано, что, рассматривая состояния на более высоком уровне детализации, чем просто как маленькие "черные ящики", можно прийти к созданию целого ряда мощных новых методов поиска и более глубокому пониманию структуры и сложности задачи.
В главах 3 и 4 рассматривался подход, согласно которому задачи можно решать, выполняя поиск в пространстве состояний. Для реализации этого подхода состояния необходимо оценивать с помощью эвристических функций, соответствующих данной проблемной области, а также проверять для определения того, не являются ли они целевыми состояниями. Однако с точки зрения таких алгоритмов поиска каждое состояние представляет собой черный ящик с неразличимой внутренней структурой. Они представлены с помощью произвольно выбранной структуры данных, доступ к которой может осуществляться только с применением процедур, относящихся к данной проблемной области, — функции определения преемника, эвристической функции и процедуры проверки цели.
В настоящей главе рассматриваются задачи удовлетворения ограничений, в которых состояния и проверка цели соответствуют стандартному, структурированному и очень простому представлению (см. раздел 5.1). Это позволяет определять алгоритмы поиска, способные воспользоваться преимуществом такой структуры состояний, и применять для решения крупных задач эвристические функции общего назначения, а не функции, относящиеся к конкретной задаче (см. разделы 5.2, 5.3). Но, возможно, еще более важно то, что применяемое стандартное представление проверки цели раскрывает структуру самой задачи (см. раздел 5.4). Это позволяет создать методы декомпозиции задачи и понять внутреннюю связь между структурой задачи и сложностью ее решения.
ЗАДАЧИ УДОВЛЕТВОРЕНИЯ ОГРАНИЧЕНИЙ
Формально говоря, любая задача удовлетворения ограничений (Constraint Satisfaction Problem — CSP) определена множеством переменных, х1,х2,...9хП9 и множеством ограничений, Сх,С2,...,Ст. Каждая переменная х± имеет непустую область определения DL возможных значений. Каждое ограничение Ci включает некоторое подмножество переменных и задает допустимые комбинации значений для этого подмножества. Состояние задачи определяется путем присваивания значений некоторым или всем этим переменным, {Xi=vi,Xj=vj,...}. Присваивание, которое не нарушает никаких ограничений, называется совместимым, или допустимым присваиванием. Полным называется такое присваивание, в котором участвует каждая переменная, а решением задачи CSP является полное присваивание, которое удовлетворяет всем ограничениям. Кроме того, для некоторых задач CSP требуется найти решение, которое максимизирует целевую функцию.
Как же все это описание перевести на язык практики? Предположим, что устав от Румынии, мы рассматриваем карту Австралии, на которой показаны все ее штаты и территории (рис. 5.1, а), и что мы получили задание раскрасить каждый регион в красный, зеленый или синий цвет таким способом, чтобы ни одна пара соседних регионов не имела одинаковый цвет. Чтобы сформулировать это задание в виде задачи CSP, определим в качестве переменных сокращенные обозначения этих регионов: WA, NT, О, NSW, V, SA и т. Областью определения каждой переменной является множество цветов {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 удобно представить визуально в виде графа ограничений, как показано на рис. 5.1, б. Узлы этого графа соответствуют переменным задачи, а дуги — ограничениям.
Рассматривая некоторую задачу в виде задачи CSP, можно достичь нескольких важных преимуществ. Представление состояний в задаче CSP соответствует некоторому стандартному шаблону (т.е. выражается в виде множества переменных с присвоенными значениями), поэтому функцию определения преемника и проверку цели можно записать в универсальной форме, применимой ко всем задачам CSP. Более того, могут быть разработаны эффективные, универсальные эвристические функции, для создания которых не требуются дополнительные знания о конкретной проблемной области. Наконец, для упрощения процесса решения может использоваться сама структура графа ограничений, что позволяет в некоторых случаях добиться экспоненциального уменьшения сложности. Это представление задачи CSP является первым и простейшим из ряда схем представления, которые будут разрабатываться на протяжении данной книги.
Можно довольно легко показать, что любой задаче CSP может быть дана инкрементная формулировка, как и любой стандартной задаче поиска, следующим образом.
• Начальное состояние. Пустое присваивание {}, в котором ни одной переменной не присвоено значение.
• Функция определения преемника. Значение может быть присвоено любой переменной с неприсвоенным значением, при условии, что переменная не будет конфликтовать с другими переменными, значения которым были присвоены ранее.
• Проверка цели. Текущее присваивание является полным.
• Стоимость пути. Постоянная стоимость (например, 1) для каждого этапа.
Каждое решение должно представлять собой полное присваивание и поэтому должно находиться на глубине л, если имеется п переменных. Кроме того, дерево поиска распространяется только на глубину п. По этим причинам для решения задач CSP широко применяются алгоритмы поиска в глубину (см. раздел 5.2). К тому же такие задачи характерны тем, что сам путь, по которому достигается некоторое решение, не представляет интереса. Поэтому может также использоваться формулировка с полным состоянием, в которой каждое состояние представляет собой полное присваивание, удовлетворяющее или не удовлетворяющее ограничениям. На основе такой формулировки хорошо действуют методы локального поиска (см. раздел 5.3).
Задачи CSP простейшего вида характеризуются тем, что в них используются переменные, которые являются дискретными и имеют конечные области определения. К такому виду относится задача раскраски карты. Задача с восемью ферзями, описанная в главе 3, также может рассматриваться как задача CSP с конечной областью определения, где переменные Qi,...,Q8 представляют собой позиции каждого ферзя на столбцах 1,...,8, а каждая переменная имеет область определения {1,2,3,4,5,6,7,8}. Если максимальный размер области определения любой переменной в задаче CSP равен d, то количество возможных полных присваиваний измеряется величиной О(сГ), т.е. зависит экспоненциально от количества переменных. К категории задач CSP с конечной областью определения относятся булевы задачи CSP, в которых переменные могут иметь значения либо true, либо false. Булевы задачи CSP включают в качестве частных случаев некоторые NP-полные задачи, такие как 3SAT (см. главу 7). Поэтому в худшем случае нельзя рассчитывать на то, что мы сможем решать задачи CSP с конечной областью определения за время меньше экспоненциального. Но в большинстве практических приложений алгоритмы CSP общего назначения позволяют решать задачи, на несколько порядков величины более крупные по сравнению с теми, которые могут быть решены с помощью алгоритмов поиска общего назначения, представленных в главе 3.
Дискретные переменные могут также иметь бесконечные области определения, например, такие, как множество всех целых чисел или множество всех строк. В частности, при календарном планировании строительных работ дата начала каждой работы представляет собой переменную, а ее возможными значениями являются целочисленные интервалы времени в сутках, отсчитываемые от текущей даты. При решении задач с бесконечными областями определения больше нет возможности описывать ограничения, перечисляя все допустимые комбинации значений. Вместо этого должен использоваться язык ограничений. Например, если работа Job±, которая занимает пять дней, должна предшествовать работе Job3, то для описания этого условия потребуется язык ограничений, представленных в виде алгебраических неравенств, таких как StartJobx+bStartJo. Кроме того, больше нет возможности решать такие ограничения, просто перечисляя все возможные присваивания, поскольку количество подобных возможных присваиваний бесконечно велико. Для линейных ограничений с целочисленными переменными (т.е. ограничений, подобных только что приведенному, в которых каждая переменная представлена только в линейной форме) существуют специальные алгоритмы поиска решений (которые здесь не рассматриваются). Можно доказать, что не существует алгоритмов решения общих нелинейных ограничений с целочисленными переменными. В некоторых случаях задачи с целочисленными ограничениями можно свести к задачам с конечной областью определения, устанавливая пределы значений всех этих переменных. Например, в задаче планирования можно установить верхний предел, равный общей продолжительности всех работ, которые должны быть запланированы.
В реальном мире очень часто встречаются задачи удовлетворения ограничений с непрерывными областями определения, и эти задачи интенсивно изучаются в области исследования операций. Например, для планирования экспериментов на космическом телескопе Хаббл требуется очень точная привязка наблюдений по времени; начало и конец каждого наблюдения и каждого маневра представляют собой переменные со значениями из непрерывной области определения, которые должны подчиняться всевозможным астрономическим ограничениям, ограничениям предшествования и ограничениям по мощности двигателей. Одной из широко известных категорий задач CSP с непрерывной областью определения являются задачи линейного программирования, в которых ограничения должны представлять собой линейные неравенства, образующие выпуклую область. Задачи линейного программирования могут быть решены за время, которое зависит полиномиально от количества переменных. Кроме того, проводились исследования задач с другими типами ограничений и целевых функций — задачи квадратичного программирования, конического программирования второго порядка и т.д.
Кроме исследования типов переменных, которые могут присутствовать в задачах CSP, полезно заняться изучением типов ограничений. Простейшим типом ограничения является унарное ограничение, которое ограничивает значение единственной переменной. Например, может оказаться, что жители штата Южная Австралия очень не любят зеленый цвет, {green}. Каждое унарное ограничение можно устранить, выполняя предварительную обработку области определения соответствующей переменной, чтобы удалить любое значение, нарушающее это ограничение. Бинарное ограничение связывает между собой две переменные. Например, бинарным ограничением является SAЈNSW. Бинарной задачей CSP называется задача, в которой предусмотрены только бинарные ограничения; она может быть представлена в виде графа ограничений, подобного приведенному на рис. 5Л,б.
В ограничениях высокого порядка участвуют три или больше переменных. Одним из известных примеров таких задач являются криптоарифметические головоломки, называемые также числовыми ребусами (рис. 5.2, а). Обычно предъявляется требование, чтобы каждая буква в криптоарифметической головоломке представляла отдельную цифру. В случае задачи, показанной на рис. 5.2, а, такое требование может быть выражено с помощью ограничения с шестью переменными Alldiff(F, Т, Ur W, R, О). Иным образом это требование может быть представлено в виде коллекций бинарных ограничений, таких как F*T. Ограничения сложения для четырех столбцов этой головоломки также включают несколько переменных и могут быть записаны следующим образом:
О + О = R + 10 • Xi Xi + w + w = и + 10 • x2 x2 + т + T - О + 10 • хъ X3 = F
где xl9 X2 и x3 — вспомогательные переменные, представляющие цифру (0 или 1), которая переносится в следующий столбец. Ограничения высокого порядка могут быть представлены в виде гиперграфа ограничений, подобного приведенному на рис. 5.2, б. Внимательный читатель заметит, что ограничение Alldiff может быть разбито на бинарные ограничения — F*T, F*u и т.д. И действительно, в упр. 5.11 предлагается доказать, что каждое ограничение высокого порядка с конечной областью определения можно свести к множеству бинарных ограничений, введя достаточное количество вспомогательных переменных. В связи с этим в данной главе будут рассматриваться только бинарные ограничения.
Все ограничения, рассматривавшиеся до сих пор, были абсолютными ограничениями, нарушение которых равносильно тому, что какое-то потенциальное решение больше не рассматривается как таковое. С другой стороны, во многих реальных задачах CSP применяются ограничения предпочтения, которые указывают, какие решения являются предпочтительными. Например, в задаче составления расписания занятий в университете может потребоваться учесть, что профессор х предпочитает проводить занятия по утрам, а профессор У — после полудня. Расписание занятий, в котором предусмотрено проведение профессором х занятия в 14:00, все еще может рассматриваться как решение (если не окажется, что профессор X должен в это время председательствовать на заседании кафедры), но уже не будет оптимальным. Ограничения предпочтения часто можно закодировать как стоимости присваиваний отдельных переменных; например, за назначение профессору X послеполуденного интервала придется заплатить 2 пункта, которые будут учтены в суммарном значении целевой функции, в то время как утренний интервал имеет стоимость 1 пункт. При использовании такой формулировки задачи CSP с предпочтениями можно решать, используя методы поиска с оптимизацией, либо основанные на поиске пути, либо локальные. Подобные задачи CSP в данной главе больше не рассматриваются, но в разделе с библиографическими заметками приведены некоторые ссылки.