Поиск по первому наилучшему совпадению

Поиск «лучший — первый» (англ. best-first search) — алгоритм поиска, исследующий граф путём расширения наиболее перспективных узлов, выбираемых в соответствии с указанным правилом.

Джуда Перл (англ. Judea Pearl) описал поиск «лучший — первый», взяв в качестве оценки узла ${\displaystyle n}$ значение некоторой «эвристической функции оценки ${\displaystyle f(n)}$, которая, вообще говоря, может зависеть от природы ${\displaystyle n}$, описания цели, информации собранной поиском на данный момент и, самое главное, от каких-либо дополнительных знаний о предметной области».[1][2]

Некоторые авторы использовали поиск «лучший — первый» специально для описания поиска с эвристикой, служащей мерой близости к целевому состоянию, поэтому пути с лучшей эвристической оценкой рассматриваются первыми. Этот специфический тип поиска называется жадным поиском «лучший — первый».[2]

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

Алгоритм поиска A* (А-звездочка) является примером оптимального поиска «лучший — первый». Алгоритм «лучший — первый» часто используются для поиска пути в комбинаторном поиске.

Алгоритм

OPEN = [Начальное состояние]
пока OPEN не пусто
повторять:
 1. Удалить лучший узел из OPEN, назовем его N. 
 2. Если N целевое состояние, делаем трассировку пути назад к начальному узлу (через записи к родителям от N) и возвращаем путь.
 3. Создать список потомков узла N.
 4. Оцениваем каждого потомка, добавляем его в OPEN, и записываем N как его родителя.
закончить

В данной версии алгоритм не является полным, так как с его помощью не всегда можно найти путь между двумя узлами, даже если он есть. Например, алгоритм «застревает» в цикле, если он заходит в тупик - узел с потомком, который является его родителем. Алгоритм вернётся к своему родителю, добавит тупиковой узел потомка в список OPEN и перейдёт на него ещё раз, и так далее.

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

 OPEN = [исходное состояние]
 CLOSE = []
 пока OPEN не пусто
 повторять:
  1.  Удалить лучший узел из OPEN, назовем его N, добавить его в CLOSE. 
  2.  Если N целевое состояние, делаем трассировку пути назад к начальному узлу (через записи к родителям от N) и возвращаем путь.
  3.  Создать список потомков узла N.
  4.  Для каждого потомка повторять:
        a.  Если потомка нет в списке CLOSE: Оцениваем его, добавляем его в OPEN, и записываем N как его родителя.
        b.  Иначе: если это новый путь лучше, чем предыдущий, изменяем запись на родителя.
 закончить

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

Жадный поиск «лучший — первый»

Использование жадного алгоритма расширяет первого потомка родителей. После генерации потомков[3]:

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

Примечания

1. Pearl J. Heuristics: Intelligent Search Strategies for Computer Problem Solving. — Addison-Wesley, 1984. — С. 48.
2. Russell S. J., Norvig P. Artificial Intelligence: A Modern Approach. — 2nd. — Upper Saddle River, New Jersey: Prentice Hall, 2003. — С. 94—95 (note 3). — 1132 с. — ISBN 0-13-790395-2. Архивировано 28 февраля 2011 года..
3. Greedy Best-First Search when EHC Fails Архивная копия от 11 июня 2010 на Wayback Machine, Carnegie Mellon.

Ссылки

• Wikibooks: Artificial Intelligence: Best-First Search