AI-2009 Day 10 (Лекции 2009 года)

Искусственный интеллект – IV курс – День 10, лекции № 19, № 20 03.11.2009.

Эвристические методы поиска

Идея, лежащая в основе большинства эвристических алгоритмов, состоит в том, чтобы оценивать с помощью эвристической информации перспективность нераскрытых вершин пространства состояний (с точки зрения достижения цели), и выбирать для продолжения поиска наиболее перспективную вершину. Самый обычный способ использования эвристической информации – введение так называемой эвристической оценочной функции. Эта функция определяется на множестве вершин пространства состояний и принимает числовые значения. Значение эвристической оценочной функции Est(V) может интерпретироваться как перспективность раскрытия вершины (иногда – как вероятность ее расположения на решающем пути). Обычно считают, что меньшее значение Est(V) соответствует более перспективной вершине, и вершины раскрываются в порядке увеличения (точнее, неубывания) значения оценочной функции.

Алгоритм эвристического перебора

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

Для раскрытия каждый раз в цикле выбирается наиболее перспективная концевая вершина дерева перебора. Также как и в случае алгоритмов слепого поиска множество порождаемых алгоритмом вершин и указателей образует дерево, в листьях которого находятся нераскрытые вершины.

Предполагаем, что исследуемое алгоритмом пространство состояний представляет собой дерево. Тогда основные шаги алгоритма эвристического перебора (best_first_search) таковы:

Шаг 1. Поместить начальную вершину в список нераскрытых вершин Open и вычислить ее оценку.

Шаг 2. Если список Open пуст, то окончание алгоритма и выдача сообщения о неудаче поиска, в противном случае перейти к шагу 3.

Шаг 3. Выбрать из списка Open вершину с минимальной оценкой (среди вершин с одинаковой минимальной оценкой выбирается любая); перенести эту вершину (назовем ее Current) в список Closed.

Шаг 4. Если Current – целевая вершина, то окончание алгоритма и выдача решения задачи, получающегося просмотром указателей от нее к начальной вершине, в противном случае перейти к следующему шагу.

Шаг 5. Раскрыть вершину Current, построив все ее дочерние вершины. Если таких вершин нет, то перейти к шагу 2, в ином случае – к шагу 6.

Шаг 6. Для каждой дочерней вершины вычислить оценку (значение оценочной функции), поместить все дочерние вершины в список Open, и построить указатели, ведущие от этих вершин к родительской вершине Current. Перейти к шагу 2.

Конец алгоритма.

Заметим, что поиск в глубину можно рассматривать как частный случай упорядоченного поиска с оценочной функцией Est(V) = d(V) , а поиск в ширину – с функцией Est(V) = 1/d(V) , где d(V) – глубина вершины V.

Чтобы модифицировать рассмотренный алгоритм для перебора на произвольных графах-пространствах состояний, необходимо предусмотреть в нем реакцию на случай построения дочерних вершин, которые уже имеются либо в списке раскрытых, либо в списке нераскрытых вершин.

В принципе эвристическая оценочная функция может зависеть не только от внутренних, собственных свойств самого оцениваемого состояния (т.е., свойств входящих в описание состояния элементов) но и от характеристик всего пространства состояний, например, от глубины местонахождения оцениваемой вершины в дереве перебора или других свойств пути к этой вершине. Поэтому значение оценочной функции для вновь построенной дочерней вершины, входящей в список Open или Closed, может понизиться, и надо скорректировать старую оценку вершины, заменив ее на новую, меньшую. Если вновь построенная вершина с меньшей оценкой входит в список Closed, необходимо вновь поместить ее в список Open, но с меньшей оценкой. Потребуется также изменить направления указателей от всех вершин списков Open и Closed, оценка которых уменьшилась, направив их к вершине Current.

Впрочем, если оценочная функция учитывает только внутренние характеристики вершин-состояний, то для предотвращения зацикливания требуется более простая модификация алгоритма –

надо просто исключить дублирование состояний в списках Open и Closed, оставляя в них лишь по одному состоянию.

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

Est1(V) = d(V) + k(V) , где

d(V) – глубина вершины V, или число ребер дерева на пути от этой вершины к начальной вершине;

k(V) – число фишек позиции-вершины V, стоящих не на «своем» месте (фишка стоит не на «своем» месте, если ее позиция отлична от позиции в целевом состоянии).

На рис.1 показано дерево, построенное алгоритмом эвристического перебора с указанной оценочной функцией. Оценка каждой вершины приведена рядом с ней внутри кружка. Отдельно стоящие цифры, как и раньше, показывают порядок, в котором строились вершины. Двойной рамкой обведена найденная целевая вершина, она построена двенадцатой.

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

Решение задачи длиною в пять ходов найдено в результате раскрытия 6 и построения 13 вершин – это существенно меньше, чем при использовании слепого перебора (соответствующие числа были: 26 и 46, 18 и 35). Таким образом, использование эвристической информации приводит к существенному сокращению перебора.

Существует несколько критериев оценки качества работы алгоритмов перебора. Один из них называется целенаправленностью и вычисляется как P = L / N , где

L – длина найденного пути до цели (она равна глубине целевой вершины), а

N – общее число вершин, построенных в ходе перебора.

P = 1, если строятся только вершины решающего пути, в остальных случаях P < 1, вообще, эта величина тем меньше, чем больше строится бесполезных вершин. Таким образом, этот критерий показывает, насколько дерево, построенное при переборе, вытянуто, а не кустисто. К сожалению, величина P зависит от длины решающего пути, что затрудняет порой сравнение алгоритмов. Другой критерий оценки, фактор эффективного ветвления, зависит от длины решающего пути гораздо меньше.

Ясно, что алгоритм эвристического поиска с хорошо подобранной оценочной функцией обнаруживает решение задачи быстрее алгоритмов слепого перебора. Однако подбор удачной эвристической функции, существенно сокращающей поиск, – наиболее трудный момент при формализации задачи, и часто подходящая оценочная функция выявляется в результате многих экспериментов.

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

Для игры в восемь можно предложить еще одну эвристическую функцию:

Est2(V) = d(V) + s(V) .

Первое слагаемое d(V) этой функции имеет тот же смысл, что и для функции Est1. Второе слагаемое получается, если для каждой из восьми фишек подсчитать сумму двух расстояний – по вертикали и горизонтали – между клетками, где находится эта фишка в оцениваемом и целевом состояниях, а затем подсчитать общую сумму s(V) таких расстояний для всех восьми фишек (тем самым получим «суммарное расстояние» всех фишек от их целевого положения).

Например, для начальной конфигурации на рис.1 расстояние текущего положения фишки с номером 8 от ее положения в целевой конфигурации равно 1 и по вертикали, и по горизонтали, а сумма их равна 2. Общая же сумма таких расстояний для всех фишек равна 5 (фишки 3, 4, 5, 7 стоят уже на «своем» месте, поэтому их вклад в суммарное расстояние равен 0). Интуитивно ясно, и это можно показать на примерах, что новая эвристическая функция имеет большую эвристическую силу, т.е. более эффективно направляет поиск к цели.

Допустимость алгоритма эвристического перебора

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

Математическое исследование алгоритма эвристического поиска – условий, гарантирующих нахождение им решения – было проведено для эвристических оценочных функций специального вида и для более сложной задачи, чем до сих пор рассматриваемая задача поиска любого решающего пути до целевой вершины.

Предположим, что на множестве дуг пространства состояний определена функция стоимости:

с(V_A, V_B) – стоимость дуги-перехода от вершины V_A к вершине V_B .

Определим также стоимость любого пути в графе-пространстве как сумму стоимостей входящих в путь дуг. Пусть целью поиска будет не просто нахождение решающего пути, а нахождение оптимального решающего пути – решающего пути с минимальной стоимостью.

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

Est(V) = g(V) + h(V) (*)

где g(V) – оценка оптимального пути от начальной вершины до вершины V,

а h(V) – оценка оптимального пути от вершины V до целевой вершины.

Если в процессе поиска уже построена вершина V, то путь до нее найден, и его стоимость может быть вычислена. Найденный путь не обязательно оптимален (возможно, существует более дешевый, еще не найденный путь из начальной вершины в V), однако стоимость найденного пути может быть использована в качестве оценки искомого пути минимальной стоимости из начальной вершины до V, т.е. в качестве первого слагаемого g(V) эвристической функции. Второе же слагаемое h(V) может быть предложено исходя из эвристических соображений, свойственных конкретной решаемой задаче, как некоторая характеристика-оценка текущей вершины V (близости ее к цели). Таким образом, собственно эвристическая информация будет воплощена только во втором слагаемом оценочной функции.

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

Алгоритм перебора называют допустимым (или состоятельным), если для произвольного графа он всегда заканчивает свою работу построением оптимального пути к цели, при условии, что такой путь существует.

Пусть h*(V) – стоимость оптимального пути из произвольной вершины V в целевую вершину. Верна следующая теорема о допустимости А-алгоритма:

А-алгоритм, использующий некоторую эвристическую функцию вида (*), где

g(V) – стоимость пути от начальной вершины до вершины V в дереве перебора, а

h(V) – эвристическая оценка оптимального пути из вершины V в целевую вершину,

является допустимым, если h(V) h*(V) для всех вершин V пространства состояний.

А-алгоритм эвристического поиска, применяющий функцию h(V), удовлетворяющую этому условию, получил название А*-алгоритма.

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

Если взять тривиальную нижнюю грань, т.е. установить h(V) = 0 для всех вершин пространства состояний, то допустимость будет обеспечена. Однако этот случай соответствует полному отсутствию какой-нибудь эвристической информации о задаче, и оценочная функция Est не имеет никакой эвристической силы, т.е. не сокращает возникающий перебор. А*-алгоритм ведет себя при этом аналогично поиску вширь.

Точнее, при Est(V) = g(V) (где g(V) – стоимость пути от начальной вершины до вершины V ), мы получаем алгоритм, известный как алгоритм равных цен (или Алгоритм Дейкстры). Алгоритм равных цен представляет собой более общий вариант метода перебора в ширину, при котором вершины раскрываются в порядке возрастания стоимости g(V) , т.е. в первую очередь раскрывается вершина из списка нераскрытых вершин, для которой величина g имеет наименьшее значение.

Если же, кроме того, положить стоимость с(V_A, V_B) = 0 для всех дуг пространства состояний, то А*-алгоритм просто превращается в неэффективный слепой поиск вширь.

Обе предложенные для игры в восемь эвристические функции Est1(V) и Est2(V) удовлетворяют условию допустимости А*-алгоритма. Первое их слагаемое d(V) есть стоимость пути к вершине V при стоимости всех дуг с(V_A, V_B) = 1. Функции отличаются лишь вторым слагаемым, и можно показать, что значение второй функции всегда (т.е. для всех состояний), больше значения первой функции: Est1(V) Est2(V) , что равнозначно k (V) s (V) .

Действительно, во второй функции вклад каждой фишки в общую оценку-сумму s(V) либо равен 0 (фишка стоит уже на «своем» месте), либо не меньше 1 (в противном случае), в первой же функции этот вклад в k(V) соответственно либо равен 0, либо равен 1.

Из последнего неравенства следует, что условие допустимости достаточно доказать только для второй функции Est2. Справедливость нужного условия

s(V) h*(V) следует из следующего соображения. Если бы фишки не мешали друг другу и могли двигаться до «своего» места по кратчайшему пути, как если бы других фишек на квадрате не было, то сумма длин таких путей для всех фишек была бы в точности равна значению s(V) . На самом же деле фишки редко когда могут двигаться по кратчайшей траектории из-за того, что на ней расположены другие фишки, поэтому длина (стоимость) оптимального решения h*(V) будет не меньше s(V).

Заметим, что s(V) не учитывает должным образом трудность обмена местами двух соседних фишек, а поэтому ее эвристическая сила в принципе может быть повышена. В ряде случаев эвристическая сила некоторой оценочной функции может быть повышена просто путем умножения на положительную константу, большую единицы, однако часто такое повышение осуществимо только за счет отказа от допустимости алгоритма. Например, если для игры в восемь в качестве второй составляющей эвристической функции взять h(V) = 2s(V), то в ряде случаев такая функция будет убыстрять поиск и позволит решать более трудные задачи, но условие допустимости перестанет выполняться (так как для начального состояния на рис.15: h*(V) 2s(V) ).