Поиск по лучшему первому

График изучения алгоритма поиска

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

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

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

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

Алгоритм поиска A* является примером алгоритма поиска best-first, как и B* . Алгоритмы best-first часто используются для поиска пути в комбинаторном поиске . Ни A*, ни B* не являются жадным поиском best-first, поскольку они включают расстояние от начала в дополнение к предполагаемым расстояниям до цели.

Жадный BeFS

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

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

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

Процедура GBS(начало, цель) — это : отметить начало как посещенное добавить начало в очередь пока очередь не пуста делаем : current_node ← вершина очереди с минимальным расстоянием до цели удалить current_node из очереди foreach neighbor n of current_node do : если n не  среди посещенных, то : если n является целевым: вернуть n, иначе : отметить n как посещённый добавить n в очередь отказ возврата

Смотрите также

Ссылки

^ Pearl, J. Эвристика: интеллектуальные стратегии поиска для решения компьютерных проблем . Addison-Wesley, 1984. стр. 48.
^ ab Рассел, Стюарт Дж .; Норвиг, Питер. (2021). Искусственный интеллект: современный подход (4-е изд.). Хобокен: Pearson. стр. 73–74. ISBN 9780134610993. LCCN 20190474.
^ Корф, Ричард Э. (1999). "Алгоритмы поиска искусственного интеллекта". В Аталлах, Михаил Дж. (ред.). Справочник по алгоритмам и теории вычислений . CRC Press. ISBN 0849326494.
^ https://www.cs.cmu.edu/afs/cs/project/jair/pub/volume28/coles07a-html/node11.html#modifiedbestfs Жадный поиск по лучшему первому, когда EHC терпит неудачу, Carnegie Mellon

Внешние ссылки

Wikibooks: Искусственный интеллект: Поиск по первому лучшему совпадению

[1] Pearl, J. Эвристика: интеллектуальные стратегии поиска для решения компьютерных проблем . Addison-Wesley, 1984. стр. 48.

[RN03-2] Рассел, Стюарт Дж .; Норвиг, Питер. (2021). Искусственный интеллект: современный подход (4-е изд.). Хобокен: Pearson. стр. 73–74. ISBN 9780134610993. LCCN 20190474.

[3] Корф, Ричард Э. (1999). "Алгоритмы поиска искусственного интеллекта". В Аталлах, Михаил Дж. (ред.). Справочник по алгоритмам и теории вычислений . CRC Press. ISBN 0849326494.

[4] ttps://www.cs.cmu.edu/afs/cs/project/jair/pub/volume28/coles07a-html/node11.html#modifiedbestfs Жадный поиск по лучшему первому, когда EHC терпит неудачу, Carnegie Mellon