Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 40
Текст из файла (страница 40)
Если бы вместо алгоритма Лгее-яеагсЛ использовался алгоритм Огар)т- ВеагсЛ, приведенный в листинге 3.6, то данное доказательство стало бы недействительным. Дело в том, что алгоритм агарЛ-яеагсЛ способен отбросить оптимальный путь к повторяющемуся состоянию, если он не бьи сформирован в первую очередь, поэтому может возвращать неоптимальные решения (см. упр. 4.4). Существуют два способа устранения этого недостатка. Первое решение состоит в том, что алгоритм Сгар)з-яеагсЛ должен быть дополнен так, чтобы он отбрасывал наиболее дорогостоящий из любых двух найденных путей к одному и тому же узлу (см. обсуждение этой темы в разделе 3.5).
Сопровождение необходимой для этого дополнительной информации связано с определенными трудностями, но гарантирует оптимальность. Второе решение состоит в обеспечении того, чтобы оптимальный путь к любому повторяющемуся состоянию всегда был первым из тех, по которым следует алгоритм, как в случае поиска по критерию стоимости.
160 Часть 11. Решение проблем Такое свойство соблюдается, если на функцию Л(п) налагается дополнительное требование, а именно требование обеспечения Ъ. преемственности эвристической функции (такое свойство называют также Ж монотонностью эвристической функции). Эвристическая функция й(п) является преемственной, если для любого узла и и для любого преемника и' узла и, сформированного в результате любого действия а, оценка стоимости достижения цели из узла п не больше чем стоимость этапа достижения узла и ' плюс оценка стоимости достижения цели из узла п ': П(п) ь с(п,а,п') + П(п') Это — форма общего Ъ. неравенства треугольника, которое указывает, что длина любой стороны треугольника не может превышать сумму длин двух других сторон.
Вданном случае треугольник образован узлами п, п' и целью, ближайшей к и. Можно довольно легко показать (упр. 4.7), что любая преемственная эвристическая функция является также допустимой. Наиболее важным следствием из определения преемственности является такой вывод: и)- поиск А" с использованием алгоритма Опар)т-Беато)тявляется оптимальным, если функция )з(п) преемственна.
Несмотря на то что требование к преемственности является более строгим, чем требование к допустимости, весьма нелегко составить такие эвристические функции, которые были бы допустимыми, но не преемственными. Все допустимые эвристические функции, рассматриваемые в данной главе, являются также преемственными. Возьмем в качестве примера функцию )з„т Известно, что обшее неравенство треугольника удовлетворяется, если длина каждой стороны измеряется с помошью расстояния по прямой, и что расстояние по прямой между и и и ' не больше чем с (и, а, п ' ) .
Поэтому эвристическая функция )з„, является преемственной. ЕШе один важный вывод из определения преемственности является таковым: если функция Л (и) преемственна, то значения функции Е(п) вдоль любого пути являются неубываюи(ими. Доказательство этого утверждения непосредственно вытекает из определения преемственности. Предположим, что узел и' — преемник узла и; в таком случае для некоторого а справедливо выражение д(п ' ) =д(п) +с(п, а, и ' ) и имеет место такая формула: Е(п') = д(п') + й(п') = д(п) + с(п,а,п') + )з(п') > д(п) + п(п) = с(п) На основании этого можно сделать вывод, что последовательность узлов, развернутых в поиске А* с использованием алгоритма Стар)т-яеакс)т, находится в неубываюшем порядке значений Е(п) . Поэтому первый целевой узел, выбранный для развертывания, должен представлять собой оптимальное решение, поскольку все дальнейшие узлы будут, по меньшей мере, столь же дорогостояшими.
Тот факт, что 1-стоимости вдоль любого пути являются неубывающими, означает также, что могут быть очерчены )ъ. контуры равных Г-стоимостей в пространстве состояний, полностью аналогичные контурам равных высот на топографической карте. Пример подобной схемы приведен на рис. 4пп Внутри контура, обозначенного как 400, все узлы имеют значения ~(п), меньшие или равные 400, и т д. В таком случае, поскольку в поиске А* развертывается периферийный узел с наименьшей ('-стоимостью, можно видеть, как поиск А* распространяется из начального узла, добавляя узлы в виде концентрических полос с возрастаюшей ('-стоимостью. Глава 4.
Информированный поиск и исследование пространства состояний 161 Рис. 4.3. Карта Румынии, на которой показаны контуры, соответствующие 0=300, т =400 и 0 =400, притом что Атад является начальным состоянием. Узлы в пределах данного конкретного контура имеют з'-стоимости, меньшие или равные значению стоимости контура При поиске по критерию стоимости (таковым является поиск А* с применением )з10) =О) эти полосы будут представлять собой "кольца" с центром в начальном состоянии.
При использовании более точных эвристических функций полосы вытягиваются в направлении целевого состояния и становятся более узко сосредоточенными вокруг оптимального пути. Если 0* представляет собой стоимость оптимального пути решения, то можно утверждать следующее: ° в поиске А* развертываются все узлы со значениями р ( п ) < с*; ° поэтому в поиске А' могут развертываться некоторые дополнительные узлы, находягциеся непосредственно на "целевом контуре" (где 01п) =с*). прежде чем будет выбран целевой узел.
На интуитивном уровне представляется очевидным, что первое найденное решение должно быть оптимальным, поскольку целевые узлы во всех последующих контурах будут иметь более высокое значение (-стоимости и поэтому более высокое значение я-стоимости (поскольку все целевые узлы имеют значения й10) =0). Кроме того, на интуитивном уровне также очевидно, что поиск А* является полным. По мере добавления полос с возрастающими значениями б мы должны в конечном итоге достичь полосы, в которой значение г будет равно стоимости пути к целевому состоянию'.
Следует отметить, что в поиске А" узлы со значением Г 1п) >С* не развертываются; например, как показано на рис. 4.2, не развертывается узел т 'зп~'. зоаха, даже несмотря на то, что является дочерним узлом корневого узла. Эту ситуацию принято обозначать так, что происходит Ъ. отсечение поддерева, находящегося ниже узла 4 Для соблюдения требования поаноты необходимо, чтобы количество узлов со стоимостью. меньшей или равной с*, было конечным; это условие соблюдастся, если стоимости всех этапов превышают некоторос коночное значение с, а коэбз4зипи сит ветвления ь является консчи ы и 162 Часть П. Решение проблем Тйглзяоаха; поскольку функция И„, является допустимой, рассматриваемый апгоритм может безопасно игнорировать это поддерево, гарантируя вместе с тем оптимальность.
Понятие отсечения (под которым подразумевается исключение из рассмотрения некоторых вариантов в связи с отсутствием необходимости их исследовать) является важным для многих областей искусственного интеллекта. Одно заключительное наблюдение состоит в том, что среди оптимальных алгоритмов такого типа (алгоритмов, которые развертывают пути поиска от корня) поиск А* является Ж оптимально эффективным для любой конкретной эвристической функции. Это означает, что не гарантируется развертывание меньшего количества узлов„чем в поиске А', с помощью какого-либо иного оптимального алгоритма (не считая той возможности, когда осуществляется выбор на равных среди узлов с й(п) = С*).
Это связано с тем, что любой алгоритм, который не развертывает все узлы со значениями й( и) <с*, подвержен риску потери оптимального решения. Те соображения, что поиск А*, как один из всех подобных алгоритмов, является действительно полным, оптимальным и оптимально эффективным, оставляют довольно приятное впечатление. Но, к сожалению, это отнюдь не означает, что поиск А* может служить ответом на все наши потребности в поиске. Сложность заключается в том, что при решении большинства задач количество узлов в пределах целевого контура пространства состояний все еше зависит экспоненциально от длины решения.
Хотя доказательство этого утверждения выходит за рамки настояшей книги, было показано, что экспоненциальный рост происходит, если ошибка эвристической функции растет не быстрее по сравнению с логарифмом фактической стоимости пути. В математических обозначениях условие субэкспоненциального роста состоит в следуюшем: )Л(л) — 12*(п) ! < 0(тод )з*(п) ) где )з* (п) — истинная стоимость достижения цели из узла гь Почти для всех практически применяемых эвристических функций эта ошибка, по меньшей мере, пропорциональна стоимости пути, и происходягций в связи с этим экспоненциальный рост в конечном итоге превосходит возможности любого компьютера. По этой причине на практике стремление находить оптимальное решение часто не оправдано. Иногда вместо этого целесообразно использовать варианты поиска А", позвозиющие быстро находить неоптимальные решения, а в других случаях — разрабатывать эвристические функции, которые являются более точными, но не строго допустимыми.
В любом случае применение хорошей эвристической функции все равно обеспечивает поразительную экономию усилий по сравнению с использованием неинформированно~о поиска. Вопрос разработки хороших эвристических функций рассматривается в разделе 4.2. Но большая продолжительность вычислений не является основным недостатком поиска А*.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
