Поиск стека лучей - Beam stack search

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

Выполнение

Поиск стека лучей использует стек лучей как структура данных для интеграции хронологического обратного отслеживания с поиском луча и может быть объединен с разделяй и властвуй алгоритм метод, приводящий к поиску по стеку лучей по принципу "разделяй и властвуй".

Альтернативы

Поиск луча с использованием обратного отслеживания ограниченного несоответствия[2] (BULB) - это алгоритм поиска, который объединяет поиск ограниченного несоответствия с поиском луча и, таким образом, выполняет не хронологический возврат, который часто превосходит хронологический поиск с возвратом, выполняемый поиском по сумме лучей и поиском по глубине.

Рекомендации

  1. ^ Чжоу, Ронг; Хансен, Эрик (2005). "Поиск пучка в стеке: интеграция обратного отслеживания с поиском пучка". CiteSeerX  10.1.1.71.4147. Цитировать журнал требует | журнал = (помощь)
  2. ^ а б Фурси, Дэвид. Кениг, Свен. «Поиск луча ограниченного несоответствия». 2005 г. «Архивная копия» (PDF). Получено 2007-12-22.