Поиск по первому наилучшему совпадению
Материал из Википедии — свободной encyclopedia
Поиск «лучший — первый» (англ. best-first search) — алгоритм поиска, исследующий граф путём расширения наиболее перспективных узлов, выбираемых в соответствии с указанным правилом.
Джуда Перл (англ. Judea Pearl) описал поиск «лучший — первый», взяв в качестве оценки узла значение некоторой «эвристической функции оценки
, которая, вообще говоря, может зависеть от природы
, описания цели, информации собранной поиском на данный момент и, самое главное, от каких-либо дополнительных знаний о предметной области».[1][2]
Некоторые авторы использовали поиск «лучший — первый» специально для описания поиска с эвристикой, служащей мерой близости к целевому состоянию, поэтому пути с лучшей эвристической оценкой рассматриваются первыми. Этот специфический тип поиска называется жадным поиском «лучший — первый».[2]
Эффективный выбор текущего лучшего кандидата для продолжения поиска может быть реализован с помощью очереди с приоритетом.
Алгоритм поиска A* (А-звездочка) является примером оптимального поиска «лучший — первый». Алгоритм «лучший — первый» часто используются для поиска пути в комбинаторном поиске.