AI-2010 Day 09 (Лекции 2010 года (rtf)), страница 3

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

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

с(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) ).

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

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

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

Упрощенные варианты эвристического перебора

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

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

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

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

8