Поиск по первому лучшему - Best-first search

Алгоритмы поиска по графам и деревьям
Списки
похожие темы

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

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

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

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

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

Жадный BFS

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

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

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

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

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

использованная литература

  1. ^ Перл, Дж. Эвристика: стратегии интеллектуального поиска для решения компьютерных проблем . Аддисон-Уэсли, 1984. стр. 48.
  2. ^ a b Рассел, Стюарт Дж .; Норвиг, Питер (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, Карнеги Меллон

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