Поиск по сумме лучей [1] - это алгоритм поиска, который объединяет хронологическое отслеживание с возвратом (то есть поиск в глубину ) с поиском луча и аналогичен поиску луча в глубину. [2] Оба алгоритма поиска - это всегда алгоритмы, которые быстро находят хорошие, но, вероятно, неоптимальные решения, например поиск луча, затем возвращаются назад и продолжают поиск улучшенных решений до сходимости к оптимальному решению.
Реализация [ править ]
Поиск по стеку лучей использует стек лучей в качестве структуры данных для интеграции хронологического обратного отслеживания с поиском луча и может быть объединен с методом алгоритма "разделяй и властвуй" , что приводит к поиску по стеку луча "разделяй и властвуй".
Альтернативы [ править ]
Поиск луча с использованием обратного отслеживания ограниченного несоответствия [2] (BULB) - это алгоритм поиска, который сочетает поиск ограниченного несоответствия с поиском луча и, таким образом, выполняет не хронологическое обратное отслеживание , которое часто превосходит хронологическое обратное отслеживание, выполняемое поиском по сумме лучей и поиском луча в глубину.
Ссылки [ править ]
- ^ Чжоу, Ронг; Хансен, Эрик (2005). "Поиск по пучку: интеграция обратного отслеживания с поиском по пучку". CiteSeerX 10.1.1.71.4147 . Цитировать журнал требует
|journal=( помощь ) - ^ a b Фёрси, Дэвид. Кениг, Свен. «Поиск пучка ограниченного несоответствия». 2005. «Архивная копия» (PDF) . Проверено 22 декабря 2007 . CS1 maint: обескураженный параметр ( ссылка )
