Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 42
Текст из файла (страница 42)
Однако при решении очень сложных задач часто возникают ситуации, в которых алгоритм ВМА* вынужден постоянно переключаться с одного пути решения на другой в пределах множества возможных путей решения, притом что в памяти может поместиться только небольшое подмножество этого множества.
(Такие ситуации напоминают проблему 'ж пробуксовки в системах подкачки страниц с жесткого диска.) В таком случае на повторное формирование одних и тех узлов затрачивается дополнительное время, а это означает, что задачи, которые были бы фактически разрешимыми с помощью поиска А' при наличии неограниченной памяти, становятся трудноразрешимыми для алгоритма ЯМА*. Иными словами, из-за ж ограничений в обввмв памяти некоторые задачи могут становиться трудноразрешимыми с точки зрения времени вычисления. Хотя отсутствует теория, позволяюгдая найти компромисс между затратами времени и памяти, создается впечатление, что зачастую избежать возникновения этой проблемы невозможно. Единственным способом преодоления такой ситуации становится частичный отказ от требований к оптимальности решения.
Обучение лучшим способам поиска Выше было представлено несколько стратегий поиска (поиск в ширину, жадный поиск по первому наилучшему совпадению и т.д.), которые были разработаны уче- з Грубый набросок этого алгоритма был приведен в первом издании настоящей книги.
! ~~ы ~ 4 Ию!жп~~ноо~юннь~и ~~он~к и ~и~"~г «~н~и~~~ ~~о и гпэн~ чк~ г"" 1 ~. 7 Часть П. Решение проблем 168 Средняя стоимость решения для сформированного случайным образом экземпляра головоломки "игра в восемь" составляет около 22 этапов. Коэффициент ветвления примерно равен 3. (Если пустой квадрат находится в середине коробки, то количество возможных ходов равно четырем, если находится в углу — двум, а если в середине одной из сторон — трем.) Это означает, что при исчерпывающем поиске на глубину 22 приходится рассматривать примерно 3"=3 . 1х10" состояний.
Отслеживая повторяющиеся состояния, это количество состояний можно сократить приблизительно в 170 000 раз, поскольку существует только 9 < /2=181 440 различимых состояний, которые являются достижимыми (см. упр. 3.4.) Это количество состояний уже лучше поддается контролю, но соответствующее количество для игры в пятнадцать примерно равно 10", поэтому для такой головоломки с более высокой сложностью требуется найти хорошую эвристическую функцию.
Если нужно находить кратчайшие решения с использованием поиска А", то требуется эвристическая функция, которая никогда не переоценивает количество этапов достижения цели. История исследований в области поиска таких эвристических функций для игры в пятнадцать является довольно долгой, авданном разделе рассматриваются два широко используемых кандидата на эту роль, которые описаны ниже. ° Ь, = количество фишек, стали<их не на своем месте. На рис. 4.5 все восемь фишек стоят не на своем месте, поэтому показанное слева начальное состояние имеет эвристическую оценку л,=8.
Эвристическая функция ь, является допустимой, поскольку очевидно, что каждую фишку, находя<цуюся не на своем месте, необходимо переместить по меньшей мере один раз. ° Ь, = сумма расстояний всех фишек от их целевых позиций. Поскольку фишки не могут передвигаться по диагонали, рассчитываемое расстояние представляет собой сумму горизонтальных и вертикальных расстояний. Такое расстояние иногда называют расстоянием, измеряемым в городских кварталах, или ~ манхэттенским расстоянием. Эвристическая функция Л, также является допустимой, поскольку все, что может быть сделано в одном ходе, состоит лишь в перемещении одной фишки на один этап ближе к цели.
Фишки от 1 до 8 врассматриваемом начальном состоянии соответствуют такому значению манхэттенского расстояния: Л,= 3 ь1+ 2 ь 2+ 2+ 3+ 3+ 2 =18. Как и можно было предположить, ни одна из этих функций не переоценивает истинную стоимость решения, которая равна 26. Зависимость производительности поиска от точности эвристической функции Одним из критериев, позволяющих охарактеризовать качество эвристической функции, является сь эффективный коэффициент ветвления Ь*. Если общее количество узлов, вырабатываемых в процессе поиска А' решения конкретной задачи, равно дг, а глубина решения равна с~, то Ь* представляет собой коэффициент ветвления, который должно иметь однородное дерево с глубиной <Г для того, чтобы в нем содержалось ДГ+1 узлов. Поэтому справедлива следующая формула: З< + 1 = 1 + Ь* + <Ь*1 + ...
+ <Ь*< Например, если алгоритм А* находит решение на глубине 5 с использованием 52 узлов, то эффективный коэффициент ветвления равен 1,92. Эффективный коэффи- Глава 4. Информированный поиск и исследование пространства состояний 169 циент ветвления может изменяться от одного экземпляра одной и той же задачи к другому, но обычно в случае достаточно трудных задач остается относительно постоянным. Поэтому экспериментальные измерения коэффициента )э* на небольшом множестве задач могут служить хорошим критерием обшей полезности рассматриваемой эвристической функции. Хорошо спроектированная эвристическая функция должна иметь значение 27*, близкое к 1, что позволяет быстро решать довольно большие задачи.
Для проверки эвристических функций Ь„и )зз авторы сформировали случайным образом !200 экземпляров задачи с длиной решения от 2 до 24 (по 100 экземпляров для каждого четного значения длины) и нашли их решения с помошью поиска с итеративным углублением и поиска в дереве по алгоритму А* с применением эвристических функций уз, и )зз.
Данные о среднем количестве узлов, развернутых при использовании каждой стратегии и эффективном коэффициенте ветвления, приведены в табл. 4.2. Эти результаты показывают, что эвристическая функция Лз лучше чем )з, и намного лучше по сравнению с использованием поиска с итеративным углублением. Применительно к найденным авторами решениям с длиной 14 применение поиска А' с эвристической функцией Лз становится в 30 000 раз более эффективным по сравнению с неинформированным поиском с итеративным углублением.
Таблица 42. Сравнение значений стоимости поиска и эффективного коэффициента ветвления для ал- гоРитмов ?сокисзчи-ПооРипйпд-ПиикоЬ и А* с Ь„Ьз. Данные УсРеднались по 100 экземплЯРам задачи игры в восемь применительно к различным значениям длины решения Эффективный коэффиниент ветвления Стоимость поиска !0$ А*(Ь,) А*(ьз) 108 А" (Ь,) А*(Ьз) 10 112 680 6384 47127 2,45 2,87 2,73 2,80 2,79 2,78 Интерес представляет вопрос о том, всегда ли эвристическая функция Ьз лучше чем )з,. Ответ на этот вопрос является положительным.
На основании определений этихдвух эвристических функций можно легко прийти к выводу, что для любого узла и справедливо выражение )зз (п) >)з, (и) . Таким образом, можно утверждать, что эвристика )зз тк доминирует над )з,. Доминирование напрямую связано с эффективностью: при поиске А* с использованием функции Лз никогда не происходит развертывание большего количества узлов, чем при поиске А* с использованием )з, (возможно, за исключением нескольких узлов с Е(п) =С*). Доказательство этого уг- 4 13 6 20 8 39 10 93 !2 3644035 227 14 539 16 1301 18 3056 20 7276 22 18094 24 39135 6 12 18 25 39 73 113 2!1 363 676 1219 1641 1,79 1,48 1,34 1,33 1,38 1,42 1,44 1,45 1,46 1,47 1,48 1,48 1,79 1,45 1,30 1,24 1,22 1,24 1,23 1,25 1,26 1.27 1,28 1,26 1?0 Часть 1!.
Решение проблем верждения является несложным. Напомним приведенное на с. 161 замечание, что каждый узел со значением г" (и) <С* наверняка должен быть развернут. Это аналогично утверждению, что должен быть наверняка развернут каждый узел со значением )г(п) <С*-д(п) . Но поскольку для всех узлов значение )г,, по крайней мере, не меньше значения )зп то каждый узел, который должен быть наверняка развернут в поиске А' с Ем будет также наверняка развернут при поиске с )зы а применение эвристической функции )ь может к тому же вызвать и развертывание других узлов. Поэтому всегда лучше использовать эвристическую функцию с более высокими значениями, при тех условиях, что эта функция не переоценивает длину нуги решения и что время вычисления этой эвристической функции не слишком велико.
Составление допустимых эвристических функций Выше было показано, что эвристические функции )г, (в которой используется количество стоягдих не на своем месте фишек) и )з, (в которой используется манхэттенское расстояние) являются довольно неплохими эвристическими функциями для задачи игры в восемь и что функция и, — из них наилучшая. Но на основании чего именно была предложена функция П,? Возможно ли, чтобы компьютер мог составить некоторую эвристическую функцию механически? Эвристические функции )з, и )з, представляют собой оценки оставшейся длины пути для задачи игры в восемь, но они, кроме того, возвращают идеально точные значения длины пути для упрощенных версий этой игры.
Если бы правила игры в восемь изменились таким образом, чтобы любую фишку можно было передвигать куда угодно, а не только на соседний пустой квадрат, то эвристическая функция )ь возвращала бы точное количество этапов в кратчайшем решении. Аналогичным образом, если бы любую фишку можно было перемешать на один квадрат в любом направлении, даже на занятый квадрат, то точное количество этапов в кратчайшем решении возврашала бы эвристическая функция )з,. Задача с меньшим количеством ограничений на возможные действия называется ах ослабленной задачей. св Стаимасть аптимальпага решения ослабленной задачи представляет собой допустимую эвристику для первоначальной задачи.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
