Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 41

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 41)

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

Эти алгоритмы рассматриваются ниже. Глава 4. Информированный поиск и исследование пространства состояний 163 Эвристический поиск с ограничением объема памяти Простейший способ сокращения потребностей в памяти для поиска А' состоит в применении идеи итеративного углубления в контексте эвристического поиска. Реализация этой идеи привела к созданию алгоритма А* с итеративным углублением [1(ега[]уеРеереп]пя А' — 1РА*). Основное различие между алгоритмом [РА* и стандартным алгоритмом итеративного углубления состоит в том, что применяемым условием останова развертывания служит Г-стоимость [д+]з), а не глубина; на каждой итерации этим остановочным значением является минимальная Г-стоимость любого узла, превышающая остановочное значение, достигнугое в предыдущей итерации.

Алгоритм [РА* является практически применимым для решения многих задач с единичными стоимостями этапов и позволяет избежать существенных издержек, связанных с поддержкой отсортированной очереди узлов. К сожалению, этот алгоритм характеризуется такими же сложностями, связанными с использованием стоимостей с действительными значениями, как и итеративная версия поиска по критерию стоимости, которая описана в упр. 3.11. В данном разделе кратко рассматриваются два более современных алгоритма с ограничением памяти, получивших названия КВ ЕБ и МА*.

сеРекурсивиьш поиск по первому наилучшему совпадению [Кесц)з]уе Вез(-Епзг Беагсй — КВЕБ) — это простой рекурсивный алгоритм, в котором предпринимаются попытки имитировать работу стандартного поиска по первому наилучшему совпадению, но с использованием только линейного пространства. Этот алгоритм приведен в листинге 4.1. Он имеет структуру, аналогичную структуре рекурсивного поиска в глубину, но вместо бесконечного следования вниз цо текущему пути данный алгоритм контролирует Г-значение наилучшего альтернативного пути, доступного из любого предка текущего узла. Если текугций узел превышает данный предел, то текущий этап рекурсии отменяется и рекурсия продолжается с альтернативного пути.

После отмены данного этапа рекурсии в алгоритме КВРБ происходит замена Г-значения каждого узла вдоль данного пути наилучшим Г-значением его дочернего узла. Благодаря этому в алгоритме КВРБ запоминается Г-значение наилучшего листового узла из забытого поддерева и поэтому в некоторый последующий момент времени может быть принято решение о том, стоит ли снова развертывать это поддерево. На рис. 4.4 показано, каке помощью алгоритма КВЕБ происходит поиск пути в Бухарест. Лнетннг 4.1.

Алгоритм рекурсивного поиска по первому наилучшему совпадению Еипсваоп Неситяьче-Вевг-Вьтят-Яеатси(ргоЬ1еш) гавигпп реыение геяи1т или индикатор неудачи Еа11иге ВВГЯ(ргоЫет, Ма)ее-поде(гпЕЫа1-Ятате[ргоЫеш]), ) ЕипсЕЕоп ВВВЯ(ртоЫет, поде, Е 11тдт) гевигпя решение геяи1т или индикатор неудачи Еа11иге и новый предел Е-стоимости Е 11т1т ЕЕ Соа1-Теят[ргоЫеш] (Ятате [поде] ) еЬеп гееигп узел поде яиссеяяотя +- Ехрапд(пес(е, ргоЫет) ЕЕ множество узлов-преемников яиссеяяогя пусто ЕЬеп гевпгп Еа11иге, Еог еасЬ я Еп яиссеяяогя До Е[я] < — шах(д(я)+Ь(я),Е[поде]) гереае Ьеят е- узел с наименьшим Е-значением в множестве яиссеяяогя ЕЕ е[ьеяс] > е 11тдг еиеп гееигп Еа11иге, е[ьеяс] Глава 4.

Информированный поиск и исследование пространства состояний 165 Алгоритм КВЕВ является немного более эффективным по сравнению с !РА', но все еше страдает от недостатка, связанного со слишком частым повторным формированием узлов. В примере, приведенном на рис. 4.4, алгоритм КВЕБ вначале следует по пути через узел нзлшзсиЫ1сеа, затем "меняет решение" и пытается пройти через узел еадахав, после этого снова возвращается к отвергнутому ранее решению.

Такие смены решения происходят в связи с тем, что при каждом развертывании текущего наилучшего пути велика вероятность того, что его Г-значение увеличится, поскольку функция )2 обычно становится менее оптимистической по мере того, как происходит развертывание узлов, более близких к цели. После того как возникает такая ситуация, особенно в больших пространствах поиска, путь, который был вторым после наилучшего, может сам стать наилучшим путем, поэтому в алгоритме поиска приходится выполнять возврат, чтобы проследовать по нему.

Каждое изменение решения соответствует одной итерации алгоритма !РА* и может потребовать многих повторных развертываний забытых узлов для воссоздания наилучшего пути и развертывания пути еще на один узел. Как и алгоритм поиска А", КВЕЯ является оптимальным алгоритмом, если эвристическая функция )2(п) допустима. Его пространственная сложность равна О(йс1), но охарактеризовать временную сложность довольно трудно: она зависит и от точности эвристической функции, и от того, насколько часто происходила смена наилучшего пути по мере развертывания узлов.

И алгоритм ! РА*, и алгоритм КВЕЯ подвержены потенциальному экспоненциальному увеличению сложности, связанной с поиском в графах (см. раздел 3.5), поскольку эти алгоритмы не позволяют определять наличие повторяющихся состояний, отличных от тех, которые находятся в текущем пути. Поэтому данные алгоритмы способны много раз исследовать одно и то же состояние. Алгоритмы 1РА* и КВЕБ страдают от того недостатка, что в них используется слишком мало памяти. Между итерациями алгоритм 1РА* сохраняет только единственное число — текущий предел Г-стоимости.

Алгоритм КВЕЯ сохраняет в памяти больше информации, но количество используемой в нем памяти измеряется лишь значением 0(бс1): даже если бы было доступно больше памяти, алгоритм КВЕ5 не способен ею воспользоваться. Поэтому представляется более разумным использование всей доступной памяти. Двумя алгоритмами, которые осуществляют это требование, являются поиск 'а. МА' (Мешогу-Ьоипдег) А* — поиск А" с ограничением памяти) и 'э. ЯМА' (5ппр!Ейед МА*— упрошенный поиск МА*). В данном разделе будет описан алгоритм 5МА", который действительно является более простым, чем другие алгоритмы этого типа. Алгоритм БМА* действует полностью аналогично поиску А*, развертывая наилучшие листовые узлы до тех пока, пока не будет исчерпана доступная память.

С этого момента он не может добавить новый узел к дереву поиска, не уничтожив старый. В алгоритме БМА* всегда уничтожается наихудший листовой узел (тот, который имеет наибольшее Езначение). Как и в алгоритме КВЕБ, после это~о в алгоритме 5 МА' значение забытого (уничтоженного) узла резервируется в его родительском узле.

Благодаря этому предок забытого поддерева позволяет определить качество наилучшего пути в этом поддереве. Поскольку имеется данная информация, в алгоритме БМА* поддерево восстанавливается, только если обнаруживается, что все другие пути выглядят менее многообещающими по сравнению с забытым путем. Иными словами, если все потомки узла и забыты, то неизвестно, каким 166 Часть!1. Решение проблем путем можно следовать от и, но все еще можно получить представление о том, есть ли смысл куда-либо следовать от и. Полный алгоритм слишком сложен для того, чтобы его можно было воспроизвести в данной книге', но заслуживает упоминания один его нюанс. Как уже было сказано выше, в алгоритме ЯМА* развертывается наилучший листовой узел и удаляется наихудший листовой узел.

А что происходит, если все листовые узлы имеют одинаковое Г-значение? В таком случае может оказаться, что алгоритм выбирает для улаления и развертывания один и тот же узел. В алгоритме ВМА* эта проблема решается путем развертывания самого нового наилучшего листового узла и удаления самого старого наихудшего листового узла. Эти два узла могут оказаться одним и тем же узлом, только если существует лишь один листовой узел; в таком случае текущее дерево поиска должно представлять собой единственный путь от корня до листового узла, заполняющий всю память.

Это означает, что если данный листовой узел не является целевым узлом, то решение не достижимо при доступном объеме памяти, даже если этот узел находится в оптимальном пути решения. Поэтому такой узел может быть отброшен точно так же, как и в том случае, если он не имеет преемников. Алгоритм ЯМА' является полным, если существует какое-либо достижимое решение, иными словами, если с(, глубина самого поверхностного целевого узла, меньше чем объем памяти (выраженный в хранимых узлах). Этот алгоритм оптимален, если достижимо какое-либо оптимальное решение; в противном случае он возвращает наилучшее достижимое решение. С точки зрения практики алгоритм ЯМА' вполне может оказаться наилучшим алгоритмом общего назначения для поиска оптимальных решений, особенно если пространство состояний представляет собой граф, стоимости этапов не одинаковы, а операция формирования узлов является более дорогостоящей в сравнении с дополнительными издержками сопровождения открытых и закрытых списков.

Характеристики

Список файлов книги