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

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

•    При жадном поиске по первому наилучшему совпадению развертываются узлы с минимальным значением п(п). Этот поиск не оптимален, но часто является эффективным.

•    При поиске А* развертываются узлы с минимальным значением f(n) =g(n) +h(n). Алгоритм А* является полным и оптимальным, при условии, что гарантирована допустимость (для алгоритма Tree-Search) или преемственность (для алгоритма Graph-Search) функции п{п). Пространственная сложность алгоритма А* все еще остается слишком высокой.

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