Поиск А: минимизация суммарной оценки стоимости решения
Наиболее широко известная разновидность поиска по первому наилучшему совпадению называется поиском А* (читается как "А звездочка"). В нем применяется оценка узлов, объединяющая в себе д(п), стоимость достижения данного узла, и h (п), стоимость прохождения от данного узла до цели:
f(n) = д(п) + h(n)
Поскольку функция д(п) позволяет определить стоимость пути от начального узла до узла л, а функция я (л) определяет оценку стоимости наименее дорогостоящего пути от узла л до цели, то справедлива следующая формула:
f{n) = оценка стоимости наименее дорогостоящего пути решения, проходящего через узел п
Таким образом, при осуществлении попытки найти наименее дорогостоящее решение, по-видимому, разумнее всего вначале попытаться проверить узел с наименьшим значением д(л) +л (л). Как оказалось, данная стратегия является больше чем просто разумной: если эвристическая функция п{п) удовлетворяет некоторым условиям, то поиск А* становится и полным, и оптимальным.
Анализ оптимальности поиска А* является несложным, если этот метод используется в сочетании с алгоритмом Tree-Search. В таком случае поиск А* является оптимальным, при условии, что h (л) представляет собой допустимую эвристическую функцию, т.е. при условии, что h (л) никогда не переоценивает стоимость достижения цели. Допустимые эвристические функции являются по своей сути оптимистическими функциями, поскольку возвращают значения стоимости решения задачи, меньшие по сравнению с фактическими значениями стоимости. А поскольку д (л) — точная стоимость достижения узла л, из этого непосредственно следует, что функция f (л) никогда не переоценивает истинную стоимость достижения решения через узел л.
Очевидным примером допустимой эвристической функции является функция определения расстояния по прямой hSLD, которая уже использовалась в данной главе для поиска пути в Бухарест. Расстояние по прямой является допустимым, поскольку кратчайший путь между любыми двумя точками лежит на прямой; это означает, что длина прямого пути по определению не может представлять собой переоценку длины пути. На рис. 4.2 показан процесс поиска А* пути в Бухарест с помощью дерева. Значения д вычисляются на основании стоимостей этапов, показанных на рис. 3.1, а значения hSLD приведены в табл. 4.1. Следует, в частности, отметить, что узел Bucharest впервые появляется в периферии на этапе, показанном на рис. 4.2, д, но не выбирается для развертывания, поскольку его f-стоимость (450) выше, чем стоимость узла Pitesti (417). Иными словами эту ситуацию можно описать так, что может существовать решение, при котором путь проходит через город Питешти со стоимостью, достигающей 417, поэтому алгоритм не останавливается на решении со стоимостью 450. Данный пример может служить общим свидетельством того, что с?= поиск А* с использованием алгоритма Tree-Search является оптимальным, если функция h(n) допустима. Предположим, что на периферии поиска появился неоптимальный целевой узел G2, а стоимость оптимального решения равна С*. В таком случае, поскольку узел G2 неоптимален, a h(G2) =0 (это выражение справедливо для любого целевого узла), можно вывести следующую формулу:
fiGb) = g(Gfe) + hiGb) = g(Gfe) > С*
Теперь рассмотрим периферийный узел л, который находится в оптимальном пути решения, например узел Pi testi в примере, приведенном в предыдущем абзаце. (Если решение существует, то всегда должен быть такой узел.) Если функция л (л) не переоценивает стоимость завершения этого пути решения, то справедлива следующая формула:
f(n) = g(n) + h(n) < С*
Таким образом, доказано, что f (л)
Такое свойство соблюдается, если на функцию л (л) налагается дополнительное требование, а именно требование обеспечения преемственности эвристической функции (такое свойство называют также монотонностью эвристической функции). Эвристическая функция я (л) является преемственной, если для любого узла л и для любого преемника л1 узла л, сформированного в результате любого действия а, оценка стоимости достижения цели из узла л не больше чем стоимость этапа достижения узла л1 плюс оценка стоимости достижения цели из узла л1:
h(n) < с{п,а,пу ) +22(п')
Это — форма общего неравенства треугольника, которое указывает, что длина любой стороны треугольника не может превышать сумму длин двух других сторон. В данном случае треугольник образован узлами л, л' и целью, ближайшей к л. Можно довольно легко показать (упр. 4.7), что любая преемственная эвристическая функция является также допустимой. Наиболее важным следствием из определения преемственности является такой вывод: с?= поиск Л* с использованием алгоритма Graph-Search является оптимальным, если функция я (л) преемственна.
Несмотря на то что требование к преемственности является более строгим, чем требование к допустимости, весьма нелегко составить такие эвристические функции, которые были бы допустимыми, но не преемственными. Все допустимые эвристические функции, рассматриваемые в данной главе, являются также преемственными. Возьмем в качестве примера функцию hSLD. Известно, что общее неравенство треугольника удовлетворяется, если длина каждой стороны измеряется с помощью расстояния по прямой, и что расстояние по прямой между лил' не больше чем с (л, а, л ' ). Поэтому эвристическая функция hSLD является преемственной.
Еще один важный вывод из определения преемственности является таковым:
если функция я (л) преемственна, то значения функции f (л) вдоль любого пути являются неубывающими. Доказательство этого утверждения непосредственно вытекает из определения преемственности. Предположим, что узел л' — преемник узла л; в таком случае для некоторого а справедливо выражение д(л' ) =g{n) +с{п, а, п* ) и имеет место такая формула:
f(n') = д(п') + 22(л') = д(п) + с(п,а,п') + h(n') > д(п) + 22(12) = f(n)
На основании этого можно сделать вывод, что последовательность узлов, развернутых в поиске А* с использованием алгоритма Graph-Search, находится в неубывающем порядке значений f{n). Поэтому первый целевой узел, выбранный для развертывания, должен представлять собой оптимальное решение, поскольку все дальнейшие узлы будут, по меньшей мере, столь же дорогостоящими.
Тот факт, что f-стоимости вдоль любого пути являются неубывающими, означает также, что могут быть очерчены контуры равных f-стоимостей в пространстве состояний, полностью аналогичные контурам равных высот на топографической карте. Пример подобной схемы приведен на рис. 4.3. Внутри контура, обозначенного как 400, все узлы имеют значения f (л), меньшие или равные 400, и т.д. В таком случае, поскольку в поиске А* развертывается периферийный узел с наименьшей f-стоимостью, можно видеть, как поиск А* распространяется из начального узла, добавляя узлы в виде концентрических полос с возрастающей f-стоимостью.
При поиске по критерию стоимости (таковым является поиск А* с применением я (л) =0) эти полосы будут представлять собой "кольца" с центром в начальном состоянии. При использовании более точных эвристических функций полосы вытягиваются в направлении целевого состояния и становятся более узко сосредоточенными вокруг оптимального пути. Если С* представляет собой стоимость оптимального пути решения, то можно утверждать следующее:
• в поиске А* развертываются все узлы со значениями f (п) <С*;
• поэтому в поиске А* могут развертываться некоторые дополнительные узлы, находящиеся непосредственно на "целевом контуре" (где f(n) =С*), прежде чем будет выбран целевой узел.
На интуитивном уровне представляется очевидным, что первое найденное решение должно быть оптимальным, поскольку целевые узлы во всех последующих контурах будут иметь более высокое значение f-стоимости и поэтому более высокое значение g-стоимости (поскольку все целевые узлы имеют значения h(n) =0). Кроме того, на интуитивном уровне также очевидно, что поиск А* является полным. По мере добавления полос с возрастающими значениями f мы должны в конечном итоге достичь полосы, в которой значение f будет равно стоимости пути к целевому состоянию4.
Следует отметить, что в поиске А* узлы со значением f (л) >С* не развертываются; например, как показано на рис. 4.2, не развертывается узел Timisoara, даже несмотря на то, что является дочерним узлом корневого узла. Эту ситуацию принято обозначать так, что происходит отсечение поддерева, находящегося ниже узла Timisoara] поскольку функция hSLD является допустимой, рассматриваемый алгоритм может безопасно игнорировать это поддерево, гарантируя вместе с тем оптимальность. Понятие отсечения (под которым подразумевается исключение из рассмотрения некоторых вариантов в связи с отсутствием необходимости их исследовать) является важным для многих областей искусственного интеллекта.
Одно заключительное наблюдение состоит в том, что среди оптимальных алгоритмов такого типа (алгоритмов, которые развертывают пути поиска от корня) поиск А* является оптимально эффективным для любой конкретной эвристической функции. Это означает, что не гарантируется развертывание меньшего количества узлов, чем в поиске А*, с помощью какого-либо иного оптимального алгоритма (не считая той возможности, когда осуществляется выбор на равных среди узлов с f (л) =С*). Это связано с тем, что любой алгоритм, который не развертывает все узлы со значениями f (л) <С*, подвержен риску потери оптимального решения.
Те соображения, что поиск А*, как один из всех подобных алгоритмов, является действительно полным, оптимальным и оптимально эффективным, оставляют довольно приятное впечатление. Но, к сожалению, это отнюдь не означает, что поиск А* может служить ответом на все наши потребности в поиске. Сложность заключается в том, что при решении большинства задач количество узлов в пределах целевого контура пространства состояний все еще зависит экспоненциально от длины решения. Хотя доказательство этого утверждения выходит за рамки настоящей книги, было показано, что экспоненциальный рост происходит, если ошибка эвристической функции растет не быстрее по сравнению с логарифмом фактической стоимости пути. В математических обозначениях условие субэкспоненциального роста состоит в следующем:
\h(n) - h*(п)| < O(log h*(n))
где л* (л) — истинная стоимость достижения цели из узла л. Почти для всех практически применяемых эвристических функций эта ошибка, по меньшей мере, пропорциональна стоимости пути, и происходящий в связи с этим экспоненциальный рост в конечном итоге превосходит возможности любого компьютера. По этой причине на практике стремление находить оптимальное решение часто не оправдано. Иногда вместо этого целесообразно использовать варианты поиска А*, позволяющие быстро находить неоптимальные решения, а в других случаях — разрабатывать эвристические функции, которые являются более точными, но не строго допустимыми. В любом случае применение хорошей эвристической функции все равно обеспечивает поразительную экономию усилий по сравнению с использованием неинформированного поиска. Вопрос разработки хороших эвристических функций рассматривается в разделе 4.2.
Но большая продолжительность вычислений не является основным недостатком поиска А*. Поскольку при поиске А* все сформированные узлы хранятся в памяти (как и во всех алгоритмах Graph-Search), фактически ресурсы пространства исчерпываются задолго до того, как исчерпываются ресурсы времени. По этой причине поиск А* не является практически применимым при решении многих крупномасштабных задач. Разработанные недавно алгоритмы позволяют преодолеть эту проблему пространства, не жертвуя оптимальностью или полнотой, за счет небольшого увеличения времени выполнения. Эти алгоритмы рассматриваются ниже.