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

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

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

Существует целое семейство алгоритмов поиска по первому наилучшему совпадению, Best-First-Search, с различными функциями оценки1. Ключевым компонентом этих алгоритмов является эвристическая функция2, обозначаемая как h (п):

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

Эвристические функции (или просто эвристики) представляют собой наиболее общую форму, в которой к алгоритму поиска подключаются дополнительные знания о задаче. Эвристики рассматриваются более подробно в разделе 4.2, а на данный момент мы будем определять их как произвольные функции, относящиеся к конкретной проблеме, с одним ограничением: если п— целевой узел, то h(n) =0. В оставшейся части настоящего раздела рассматриваются два способа использования эвристической информации для управления поиском.