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

Алгоритмы поиска на графах
A* B* Алгоритм Беллмана — Форда Двунаправленный поиск Алгоритм Дейкстры Алгоритм Джонсона Поиск в ширину Поиск в глубину Поиск с ограничением глубины Поиск по первому наилучшему совпадению Алгоритм Флойда — Уоршелла

Поиск «Лучший — первый» — это алгоритм поиска, который исследует граф путём расширения наиболее перспективных узлов, выбираемых в соответствии с указанным правилом.

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

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

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

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

Алгоритм ^[3]

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.  Иначе: если это новый путь лучше, чем предыдущий, изменяем запись на родителя.
 закончить

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

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

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

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

См. также

• Алгоритм поиска A*
• Алгоритм Дейкстры

Примечания

1. ↑ Pearl J. Heuristics: Intelligent Search Strategies for Computer Problem Solving. — Addison-Wesley, 1984. — С. 48.
2. ↑ ^{1 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.
3. ↑ http://www.macs.hw.ac.uk/~alison/ai3notes/subsubsection2_6_2_3_2.html Best First Search.
4. ↑ http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume28/coles07a-html/node11.html#modifiedbestfs Greedy Best-First Search when EHC Fails, Carnegie Mellon.

Ссылки

• http://www.macs.hw.ac.uk/~alison/ai3notes/subsubsection2_6_2_3_2.html
• Wikibooks: Artificial Intelligence: Best-First Search
• http://www.cs.utah.edu/~hal/courses/2009S_AI/Walkthrough/GreedyBFS/
• http://en.wikipedia.org/wiki/Best-first_search