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