Поиск по принципу «лучшее в первую очередь»
Поиск по принципу «сначала лучший» — это класс поисковых алгоритмов , который исследует граф , расширяя наиболее перспективный узел, выбранный в соответствии с заданным правилом.
Джудея Перл описал поиск по принципу «лучший первый» как оценку перспективности узла n с помощью «эвристической функции оценки». что, вообще говоря, может зависеть от описания n , описания цели, информации, собранной поиском до этого момента, и, самое главное, от каких-либо дополнительных знаний о проблемной области». [1] [2]
Некоторые авторы использовали термин «поиск по первому лучшему» для обозначения поиска с эвристикой , которая пытается предсказать, насколько близок конец пути к решению (или цели), так что пути, которые считаются более близкими к решение (или цель) распространяется в первую очередь. Этот конкретный тип поиска называется жадным поиском по принципу «наилучшее первое». [2] или чистый эвристический поиск . [3]
Эффективный выбор текущего лучшего кандидата на расширение обычно реализуется с использованием очереди приоритетов .
Алгоритм поиска A* является примером алгоритма поиска по принципу «сначала лучшее», как и B* . Алгоритмы Best-First часто используются для поиска пути в комбинаторном поиске . Ни A*, ни B* не являются жадным поиском по принципу «лучший первый», поскольку они включают расстояние от начала в дополнение к предполагаемым расстояниям до цели.
Жадный BeFS [ править ]
Используя жадный алгоритм , разверните первого наследника родителя. После создания преемника: [4]
- Если эвристика преемника лучше, чем у его родителя, преемник устанавливается в начале очереди (родитель повторно вставляется непосредственно за ним), и цикл перезапускается.
- В противном случае преемник вставляется в очередь (в место, определяемое его эвристическим значением). Процедура оценит оставшихся преемников (если таковые имеются) родителя.
Ниже приведен пример псевдокода этого алгоритма, где очередь представляет собой приоритетную очередь, которая упорядочивает узлы на основе их эвристического расстояния от цели. Эта реализация отслеживает посещенные узлы и поэтому может использоваться для неориентированных графов . Его можно изменить, чтобы получить путь.
процедура GBS(начало, цель : )
отметить начало как посещенное
добавить начало в очередь
пока очередь не , пуста сделайте :
current_node ← вершина очереди с минимальным расстоянием до цели
удалить current_node из очереди
foreach сосед n текущего_узла do :
если n не посещен , то :
если n является целью:
вернуть н
еще :
отметить как посещенный
добавить в очередь
возврат неудачный
См. также [ править ]
Ссылки [ править ]
- ^ Перл, Дж. Эвристика: стратегии интеллектуального поиска для решения компьютерных проблем . Аддисон-Уэсли, 1984. с. 48.
- ^ Перейти обратно: а б Рассел, Стюарт Дж .; Норвиг, Питер. (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, Карнеги-Меллон