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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Джуда Перл (англ. Judea Pearl) описал поиск «лучший — первый», взяв в качестве оценки узла n значение некоторой «эвристической функции оценки f(n), которая, вообще говоря, может зависеть от природы 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. 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. Greedy Best-First Search when EHC Fails, Carnegie Mellon.

Ссылки[править | править вики-текст]