Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Алгоритмы поиска по графам и деревьям
Списки
похожие темы

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

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

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

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

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

Жадный BFS [ править ]

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

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

См. Также [ править ]

  • Поиск луча
  • Алгоритм поиска A *
  • Алгоритм Дейкстры

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

  1. ^ Перл, Дж. Эвристика: стратегии интеллектуального поиска для решения компьютерных проблем . Эддисон-Уэсли, 1984. стр. 48.
  2. ^ Б Рассел, Стюарт Дж ; Норвиг, Питер (2003), Искусственный интеллект: современный подход (2-е изд.), Верхняя Сэдл-Ривер, Нью-Джерси: Prentice Hall, ISBN 0-13-790395-2. С. 94 и 95 (примечание 3).
  3. ^ Корф, Ричард Э. (1999). «Алгоритмы поиска с искусственным интеллектом». В Аталлах, Михаил Дж. (Ред.). Справочник по алгоритмам и теории вычислений . CRC Press. ISBN 0849326494.
  4. ^ https://www.cs.cmu.edu/afs/cs/project/jair/pub/volume28/coles07a-html/node11.html#modifiedbestfs Жадный поиск лучшего первого при сбое EHC, Карнеги Меллон

Внешние ссылки [ править ]

  • Викиучебники: Искусственный интеллект: поиск лучшего первого