Эвристический поиск

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

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

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

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

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

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

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

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

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

Лучшими свойствами обладает другая форма эвристического поиска, которая получила наименование сначала наилучший (best-first search). Так же, как и в варианте восхождения на гору, в нашем распоряжении имеется оценочная функция, с помощью которой можно сравнивать состояния в пространстве состояний. Основное же отличие нового метода от ранее рассмотренного состоит в том, что сравниваются не только те состояния, в которые возможен переход из текущего, но и все, до которых "можно достать".

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