Обзор исследований в области искусственного интеллекта


Обзор исследований в области искусственного интеллекта - стр. 9


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

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

Основной алгоритм, реализующий идею восхождения на гору, можно сформулировать следующим образом.

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

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

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

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


Начало  Назад  Вперед