Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 53
Текст из файла (страница 53)
4.8). Обсудите полученные вами результаты. Как изменяется производительность алгоритма КВРБ после добавления небольшого случайного числа к эвристическим значениям в проблемной области задачи игры в восемь? В этой главе показано, что, рассматривая состояния на более высоком уровне детализации, чем просто как маленькие "черные ящики", мож- но прийти к созданию целого ряда мощных новых методов поиска и бо- лее глубокому пониманию структуры и сложности задачи.
В главах 3 и 4 рассматривался подход, согласно которому задачи можно решать, выполняя поиск в пространстве состояний. Для реализации этого подхода состояния необходимо оценивать с помощью эвристических функций, соответствующих данной проблемной области, а также проверять для определения того, не являются ли они целевыми состояниями. Однако с точки зрения таких алгоритмов поиска каждое состояние представляет собой 'в,черный ящик с неразличимой внутренней структурой. Они представлены с помогцью произвольно выбранной структуры данных, доступ к которой может осуществляться только с применением процедур, относящихся к данной проблемной области, — функции определения преемника, эвристической функции и процедуры проверки цели.
В настоящей главе рассматриваются задачи удовлетворения ограничений, в которых состояния и проверка цели соответствуют стандартному, структурированному и очень простому 'ъ. представлению (см. раздел 5.1). Это позволяет определять алгоритмы поиска, способные воспользоваться преимуществом такой структуры состояний, и применять для решения крупных задач эвристические функции общего назначения, а не функции, относящиеся к конкретной задаче (см. разделы 5.2, 5.3).
Но, возможно, еще более важно то, что применяемое стандартное представление проверки цели раскрывает структуру самой задачи (см. раздел 5.4). Это позволяет создать методы декомпозиции задачи и понять внутреннюю связь между структурой задачи и сложностью ее решения.
210 Часть П. Решение проблем 5.1. ЗАДАЧИ УДОВЛЕТВОРЕНИЯ ОГРАНИЧЕНИЙ Формально говоря, Ъ.любая задача удовлетворения ограничений (Сопз(га(п( Ба(нбас(юп РгоЫегп — СБР) определена множеством 'в. переменных, х„,х,,...,х„, и множеством сьограиичений, С„,С„...,С. Каждая переменная Х, имеет непустую Ж область определения ()г возможных ~. значений. Ках(дое ограничение С, включает некоторое подмножество переменных и задает допустимые комбинации значений для этого подмножества. Состояние задачи определяется путем 'а.
присваивания значений некоторым или всем этим переменным, (х,=те,х)=д,,...). Присваивание, которое не нарушает никаких ограничений, называется сь совместимым, или допустимым присваиванием. Полным называется такое присваивание, в котором участвует каждая переменная, а решением задачи СЗР является полное присваивание, которое удовлетворяет всем ограничениям. Кроме того, для некоторых задач СБР требуется найти решение, которое максимизирует 'в. целевую функцию.
Как же все это описание перевести на язык практики? Предположим, что устав от Румынии, мы рассматриваем карту Австралии, на которой показаны все ее штаты и территории (рис. 5.1, а), и что мы получили задание раскрасить каждый регион в красный, зеленый или синий цвет таким способом, чтобы ни одна пара соседних регионов не имела одинаковый цвет. Чтобы сформулировать это задание в виде задачи СЗР, определим в качестве переменных сокращенные обозначения этих регионов: )уА, лгт, (2, )дди( (г, ЯА и т. Областью определения каждой переменной является множество цветов (гес), дгееп, Ь1ие). Ограничения требуют, чтобы все пары соседних регионов имели разные цвета; например, допустимыми комбинациями для (уА и )дт являются следующие пары: ((ген, дгееп), (гес),Ыие),(дгееп,гес)), (дгееп,Ыие),(Ь1ие,гес)), (Ыие,дгсеп)) (Это ограничение можно также представить более сжато в виде неравенства (уА~)ут, при условии, что в данном алгоритме удовлетворения ограничений предусмотрен некоторый способ вычисления таких выражений.) Количество возможных решений достаточно велико; например, одним из таких решений является следующее: ( Ил=гес), Нт=дгееп, (2=гес), т(дньдгееп, ангел, дА=Ы ие, т=гес)) Задачу СЗР удобно представить визуально в виде ',з.
графа ограничений, как показано на рис. 5.1, б. Узлы этого графа соответствуют переменным задачи, а дуги — ограничениям. Рассматривая некоторую задачу в виде задачи СБР, можно достичь нескольких важных преимушеств. Представление состояний в задаче СЗР соответствует некоторому стандартному шаблону (т.е. выражается в виде множества переменных с присвоенными значениями), поэтому функцию определения преемника и проверку цели можно записать в универсальной форме, применимой ко всем задачам СЗР. Более того, могут быть разработаны эффективные, универсальные эвристические функции, для создания которых не требуются дополнительные знания о конкретной проблемной области. Наконец, для упрощения процесса решения может использоваться сама структура графа ограничений, что позволяет в некоторых случаях добиться экспоненциального уменьшения сложности.
Это представление задачи СБР является первым и простейшим из ряда схем представления, которые будут разрабатываться на протяжении данной книги. 212 Часть!1. Решение проблем ферзями, описанная в главе 3, также может рассматриваться как задача СБР с конечной областью определения, где переменные а„...,д, представляют собой позиции каждого ферзя на столбцах 1,...,8, а каждая переменная имеет область определения (1, 2, 3, 4, 5, б, 7, 8). Если максимальный размер области определения любой переменной в задаче С5Р равен с(, то количество возможных полных присваиваний измеряется величиной о(сУ'), т.е.
зависит экспоненциально от количества переменных. К категории задач СБР с конечной областью определения относятся 'ж булевы задачи СЯР, в которых переменные могут иметь значения либо ение, либо га2яе. Булевы задачи С5Р включают в качестве частных случаев некоторые ЫР-полные задачи, такие как 3БАТ (см. главу 7). Поэтому в худшем случае нельзя рассчитывать на то, что мы сможем решать задачи СВР с конечной областью определения за время меньше экспоненциального. Но в большинстве практических приложений алгоритмы СБР общего назначения позволяют решать задачи, на несколько порядков величины более крупные по сравнению с теми, которые могут быть решены с помощью алгоритмов поиска общего назначения, представленных в главе 3.
Дискретные переменные могут также иметь Ъ. бесконечные области определения, например, такие, как множество всех целых чисел или множество всех строк. В частности, при календарном планировании строительных работ дата начала каждой работы представляет собой переменную, а ее возможными значениями являются целочисленные интервалы времени в сутках, отсчитываемые от текущей даты.
При решении задач с бесконечными областями определения больше нет возможности описывать ограничения, перечисляя все допустимые комбинации значений. Вместо этого должен использоваться ж язык ограничений. Например, если работа,тоЬ„которая занимает пять дней, должна предшествовать работе тоЬ,, то для описания этого условия потребуется язык ограничений, представленных в виде алгебраических неравенств, таких как Яеахс тоЬ,+5<Яеаге,тоЬ,.
Кроме того, больше нет возможности решать такие ограничения, просто перечисляя все возможные присваивания, поскольку количество подобных возможных присваиваний бесконечно велико. Для 'в, линейных ограничений с целочисленными переменными (т.е. ограничений, подобных только что приведенному, в которых каждая переменная представлена только в линейной форме) существуют специальные алгоритмы поиска решений (которые здесь не рассматриваются).
Можно доказать, что не существует алгоритмов решения общих Ж нелинейных ограничений с целочисленными переменными. В некоторых случаях задачи с целочисленными ограничениями можно свести к задачам с конечной областью определения, устанавливая пределы значений всех этих переменных. Например, в задаче планирования можно установить верхний предел, равный общей продолжительности всех работ, которые должны быть запланированы. В реальном мире очень часто встречаются задачи удовлетворения ограничений с Ъ. непрерывными областями определения, и эти задачи интенсивно изучаются в области исследования операций. Например, для планирования экспериментов на космическом телескопе Хаббл требуется очень точная привязка наблюдений по времени; начало и конец каждого наблюдения и каждого маневра представляют собой переменные со значениями из непрерывной области опре- Глава 5.
Задачи удовлетворения ограничений 213 деления, которые должны подчиняться всевозможным астрономическим ограничениям, ограничениям предшествования и ограничениям по мощности двигателей. Одной из широко известных категорий задач СЯР с непрерывной областью определения являются задачи Ъ. линейного программирования, в которых ограничения должны представлять собой линейные неравенства, образующие выпуклую область.
Задачи линейного программирования могут быть решены за время, которое зависит полиномиально от количества переменных. Кроме того, проводились исследования задач с другими типами ограничений и целевых функций — задачи квадратичного программирования, конического программирования второго порядка и т.д. Кроме исследования типов переменных, которые могут присутствовать в задачах СБР, полезно заняться изучением типов ограничений. Простейшим типом ограничения является Ж унариое ограничение, которое ограничивает значение единственной переменной. Например, может оказаться, что жители штата Южная Австралия очень не любят зеленый цвет, ( дхееп1. Каждое унарное ограничение можно устранить, выполняя предварительную обработку области определения соответствующей переменной, чтобы удалить любое значение, нарушающее это ограничение.
~ Бинарное ограничение связывает между собой две переменные. Например, бинарным ограничением является ял~дгквг Бинарной задачей СБР называется задача, в которой предусмотрены только бинарные ограничения; она может быль представлена в виде графа ограничений, подобного приведенному на рис. 5.1, б. В ограничениях высокого порядка участвуют три или больше переменных. Одним из известных примеров таких задач являются 'в.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
