AI-2009 Day 10 (Лекции 2009 года), страница 2

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

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

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

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

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

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

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

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

4