Неизвестно - Prolog

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

Оптимизационные задачи моделируются приписыванием каждой дуге пространства состояний некоторой стоимости.

Имеются две основных стратегии поиска в пространстве состояний - поиск в глубину и поиск в ширину .

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

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

Поиск в ширину всегда первым обнаруживает самое короткое решение, что не верно в отношении стратегии поиска в глубину.

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

В этой главе были введены следующие понятия:

пространство состояний

стартовая вершина, целевое условие,

решающий путь

стратегия поиска

поиск в глубину, поиск в ширину

эвристический поиск.

Литература

Поиск в глубину и поиск в ширину - базовые стратегии поиска, они описаны в любом учебнике по искусственному интеллекту, см., например, Nilsson (1971, 1980) или Winston (1984). Р. Ковальский в своей книге Kowalski (1980) показывает, как можно использовать аппарат математической логики для реализации этих принципов.

Kowalski R. (1980). Logic for Problem Solving. North-Holland.

Nilsson N. J. (1971). Problem Solving Methods in Artificial Intelligence. McGraw-Hill.

Nilsson N. J. (1980). Principles of Artificial Intelligence. Tioga; also Springer- Verlag, 1981.

Winston P. H. (1984). Artificial Intelligence (second edition). Addison-Wesley. [Имеется перевод первого издания: Уинстон П. Искусственный интеллект. - М.: Мир, 1980.]

Назад | Содержание | Вперёд

Назад | Содержание | Вперёд

Глава 12

ПОИСК С ПРЕДПОЧТЕНИЕМ: ЭВРИСТИЧЕСКИЙ ПОИСК

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

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

12. 1. Поиск с предпочтением

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

Рис. 12. 1. Построение эвристической оценки f(n) стоимости

самого дешевого пути из s в t , проходящего через n : f(n) = g(n) + h(n) .

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

Пусть f - это эвристическая оценочная функция, при помощи которой мы получаем для каждой вершины n оценку f( n) "трудности" этой вершины. Тогда наиболее перспективной вершиной-кандидатом следует считать вершину, для которой f принимает минимальное значение. Мы будем использовать здесь функцию f специального вида, приводящую к хорошо известному А*-алгоритму. Функция f( n) будет построена таким образом, чтобы давать оценку стоимости оптимального решающего пути из стартовой вершины s к одной из целевых вершин при условии, что этот путь проходит через вершину n . Давайте предположим, что такой путь существует и что t - это целевая вершина, для которой этот путь минимален. Тогда оценку f( n) можно представить в виде суммы из двух слагаемых (рис. 12.1):