Создаем искусственный интеллект. Урок 5. Поиск решений задач в пространстве состояний. А-алгоритм.

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

,

где - оценка стоимости пути из начальной вершины в вершину n; – оценка стоимости кратчайшего пути из вершины n в целевую вершину.

Алгоритм, базирующийся на использовании оценочной функции , называется А-алгоритмом. Оценки в ходе поиска не меняют своих значений. Оценки также не меняют своих значений и всегда равны реальным затратам , если поиск пути выполняется на дереве состояний. Однако при поиске пути на графе состояний оценки  могут меняться. Следовательно, в общем случае оценки  меняют свои значения в процессе поиска. Это приводит к тому, что вершины из  списка CLOSED могут перемещаться обратно в список OPEN:

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

Procedure A_Search;

Begin

       Поместить начальную вершину s в список OPEN: f(s)=ĥ(s);

       CLOSED := ’пустой список’;

       While OPEN <> ’пустой список’ Do Begin

            n := first(OPEN);

            If n = ‘целевая вершина’ Then Выход(УСПЕХ);

Переместить n из списка OPEN в CLOSED;

Раскрыть вершину n, для всех её дочерних вершин  вычислить

оценку ;

Поместить дочерние вершины, которых нет в списках OPEN, сравнить

оценки  и если < то связать с вершиной  новую оценку  и указатель на вершину n;

Если вершина  содержится в списке CLOSED и  <

то связать с вершиной  новую оценку переместить её в список OPEN и установить указатель на n;

Упорядочить список OPEN по возрастанию значения ;

       End;

       Выход(НЕУДАЧА);

End.

Укажем свойства А-алгоритма. Если для всех вершин ĥ(n)=0,то А-алгоритм будет соответствовать алгоритму равных цен. В этом случае гарантируется нахождения оптимального пути, но эффективность поиска будет низкой, и если пространство поиска будет бесконечно, то поиск просто не осуществим.

А-алгоритм не дает гарантии, что найденный путь будет оптимальным. Путь может быть не оптимальным в случае, если оценка затрат на пути из вершины n в целевую вершину будет преувеличена (переоценена), т.е. если ĥ(n)>h(n) Сказанное можно пояснить с помощью рисунка:

Рисунок – граф состояний с переоценкой затрат h(n)

, а рядом с ребрами – стоимости перехода . При раскрытии вершины

А-алгоритм обеспечит поиск оптимально пути, если выполняется условие: ĥ(n)≤h(n).

Алгоритм, учитывающий данное, называют А* - алгоритмом или гарантирующим алгоритмом. А* - алгоритм недооценивает затраты на пути из промежуточной вершины в целевую вершину или оценивает их правильно, но никогда не переоценивает.

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

Эффективность поиска с помощью А* - алгоритма может снижаться из-за того, что вершина, находящаяся в списке CLOSED, может попадать обратно с список OPEN и затем повторно закрываться. Следующий пример демонстрирует случай многократного раскрытия вершин.

Рисунок - Граф состояний с многократно раскрываемыми вершинами.

Состояние списков OPEN и CLOSED показаны в таблице. Каждая строка таблицы соответствует очередному шагу работы алгоритма. Числа рядом с именами вершин соответствует значениям оценочной функции f(n). Из таблицы следует, что вершина А раскрывается четыре раза, вершина В – 3 раза, вершина С – 2 раза.

Таблица – Выполнение А*-алгоритма:

Если условие монотонности соблюдается для всех дочерних вершин, то можно доказать, что в тот момент, когда раскрывается некоторая вершина n, оптимальный путь к ней уже найден. Следовательно, оценочная функция f(n) для данной вершины в дальнейшем не меняет своих значений, и никакие вершины из списка CLOSED в список OPEN не возвращаются.

Ранее отмечалось, что А* - алгоритм недооценивает затраты h(n). Условие монотонности означает, что недооценка на пути к цели становится все меньше или, в крайнем случае, не изменяется. Действительно, если обозначить недооценку через û(n), то

û(n) = h(n) – ĥ(n), û(n)≥0.

Из условия монотонности следует, что , т.е. недооценка h(n) в родительских вершинах больше или равно недооценкам h(n) в дочерних вершинах. На графе, изображенном на рисунке граф состояний с многократно раскрываемыми вершинами, условие монотонности не выполняется для начальной вершины. Например, h(S) > h(D) + c(S,D), т.е. 14 > 10 + 1.

Если ĥ(n) = h(n), то информированность является полной. В этом случает никакого поиска не происходит и приближение к цели идет по оптимальному пути.

Таким образом, свойства А-алгоритма существенно зависят от условий, которым удовлетворяет или не удовлетворяет эвристическая часть оценочной функции f(n):

1. А-алгоритм соответствует алгоритму равных цен, если h(n) = 0;

2. А-алгоритм гарантирует оптимальное решение, если ĥ(n) ≤ h(n); в этом случае он называется А* - алгоритмом;

3. А- алгоритм обеспечивает однократное раскрытие вершин, если выполняется условие монотонности ;

4. Алгоритм * эвристически более сильный, чем алгоритм * при ;

5. А*- алгоритм полностью информирован, если ĥ(n) = h(n);

6. При ĥ(n) > h(n) А-алгоритм не гарантирует получение оптимального решения, однако часто решение получается быстро.

 Рассмотренные алгоритмы поиска в пространстве состояний можно систематизировать с помощью таблицы.

Поиск решений в пространстве состояний может выполняться в нескольких направлениях: из начального состояния в целевое состояние (поиск, управляемый данными); из целевого состояния в начальное состояние (поиск, управляемый целью, или обратный поиск); одновременно в двух направлениях (комбинированный поиск). Так как поисковые графы (деревья) для практических задач велики, то двунаправленный поиск может быть эффективнее однонаправленного. Поиск решений в пространстве состояний – комбинаторная задача. Решение получается на основе перебора всех состояний. Однако для многих практических задач полный перебор невозможен. Были предложены различные меры для оценки сложности решаемой задачи. Одна из них – это степень разветвления вершин графа состояния. Она равна среднему числу дочерних вершин, приходящихся на одно состояние задачи. Если рассматривать дерево состояний, то можно вывести формулу, устанавливающую зависимость общего числа состояний N от степени разветвления В и глубины дерева L: