Эвристический поиск. 
Интеллектуальные системы

Стратегии поиска в глубину и в ширину целесообразно использовать для построения решающих путей в пространстве состояний тогда, когда поиск осуществляется без дополнительной информации о решаемой задаче. Иначе говоря, когда единственной информацией, имеющейся в распоряжении, являются списки вершин N={n_b п₂,…, я,.} и дуг ? = {/, /₂, I_s] пространства состояний и больше ничего. Здесь 1_к = (%, n_jk) обозначает ребро, направленное из вершины п,_к в вершину n_jk.

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

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

Дополнительная (эвристическая) информация о задаче в некоторых случаях может быть выражена численно в форме оценочной функции/(«), определенной на вершинах пространства состояний, т. е. на множестве N. Оценочная функция /(•) вершине п пространства состояний сопоставляет действительное число f (n), рассматриваемое как оценка перспективности (предпочтительности) продолжения поиска из вершины п. Чем меньше (а в некоторых задачах — чем больше) значение f (n), тем предпочтительнее (перспективнее) продолжение поиска из вершины п. Вот почему эвристический поиск иногда называют поиском с предпочтением.

В некоторых случаях эвристическая информация о задаче выражается не количественно в форме числовой оценочной функции, а качественно в форме отношения предпочтения, которое определяется на множестве вершин пространства состояний N. Если две вершины пил' являются кандидатами для продолжения поиска и находятся между собой в отношении предпочтения R, т. е. nRn', то более перспективной для достижения цели поиска следует считать вершину п.

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

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

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

• — альпинисту для скорейшего достижения вершин надо продвигаться к ней по самому крутому склону; если в какой-то момент это оказывается невозможным, то допускается минимально возможное отклонение, после чего альпинисту следует двигаться к цели из новой позиции, в которую привело его вынужденное отклонение;
• — если мы на автомобиле хотим пересечь город в направлении с севера на юг за кратчайшее время, то стараемся сохранить это направление как можно дольше, а когда условия движения вынуждают нас изменить направление, то мы стараемся отклониться как можно меньше. Следовательно, глобальный экстремум в градиентных методах достигается через последовательность локальных экстремумов.

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