Поиск по принципу «лучшее в первую очередь»
Поиск по принципу «сначала лучший» — это класс алгоритмов поиска , который исследует граф , расширяя наиболее перспективный узел, выбранный в соответствии с заданным правилом.
Джудея Перл описал поиск по принципу «лучший первый» как оценку перспективности узла n с помощью «эвристической функции оценки». что, вообще говоря, может зависеть от описания n , описания цели, информации, собранной поиском до этого момента, и, самое главное, от каких-либо дополнительных знаний о проблемной области». [ 1 ] [ 2 ]
Некоторые авторы использовали термин «поиск по первому лучшему» для обозначения поиска с эвристикой , которая пытается предсказать, насколько близок конец пути к решению (или цели), так что пути, которые считаются более близкими к решение (или цель) распространяется в первую очередь. Этот конкретный тип поиска называется жадным поиском по принципу «наилучшее первое». [ 2 ] или чистый эвристический поиск . [ 3 ]
Эффективный выбор текущего лучшего кандидата на расширение обычно реализуется с использованием очереди приоритетов .
Алгоритм поиска A* является примером алгоритма поиска по принципу «сначала лучшее», как и B* . Алгоритмы Best-First часто используются для поиска пути в комбинаторном поиске . Ни A*, ни B* не являются жадным поиском по принципу «лучший первый», поскольку они включают расстояние от начала в дополнение к предполагаемым расстояниям до цели.
Жадный BeFS
[ редактировать ]Используя жадный алгоритм , разверните первого наследника родителя. После создания преемника: [ 4 ]
- Если эвристика преемника лучше, чем у его родителя, преемник устанавливается в начале очереди (родитель повторно вставляется непосредственно за ним), и цикл перезапускается.
- В противном случае преемник вставляется в очередь (в место, определяемое его эвристическим значением). Процедура оценит оставшихся преемников (если таковые имеются) родителя.
Ниже приведен пример псевдокода этого алгоритма, где очередь представляет собой приоритетную очередь, которая упорядочивает узлы на основе их эвристического расстояния от цели. Эта реализация отслеживает посещенные узлы и поэтому может использоваться для неориентированных графов . Его можно изменить, чтобы получить путь.
procedure GBS(start, target) is:
mark start as visited
add start to queue
while queue is not empty do:
current_node ← vertex of queue with min distance to target
remove current_node from queue
foreach neighbor n of current_node do:
if n not in visited then:
if n is target:
return n
else:
mark n as visited
add n to queue
return failure
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Перл, Дж. Эвристика: стратегии интеллектуального поиска для решения компьютерных проблем . Аддисон-Уэсли, 1984. с. 48.
- ^ Jump up to: а б Рассел, Стюарт Дж .; Норвиг, Питер. (2021). Искусственный интеллект: современный подход (4-е изд.). Хобокен: Пирсон. стр. 73–74. ISBN 9780134610993 . LCCN 20190474 .
- ^ Корф, Ричард Э. (1999). «Алгоритмы поиска искусственного интеллекта». В Аталле Михаил Дж. (ред.). Справочник по алгоритмам и теории вычислений . ЦРК Пресс. ISBN 0849326494 .
- ^ https://www.cs.cmu.edu/afs/cs/project/jair/pub/volume28/coles07a-html/node11.html#modifiedbestfs Жадный поиск по принципу «лучшее в первую очередь» при сбое EHC, Карнеги-Меллон