Поиск стека лучей

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

Выполнение

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

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

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

Ссылки

^ Чжоу, Ронг; Хансен, Эрик А. (2005). «Поиск по лучу: интеграция обратного отслеживания с поиском по лучу» (PDF) . CiteSeer ^х: 10.1.1.71.4147 .
^ Jump up to: ^а ^б Фурси, Дэвид. Кениг, Свен. «Лучевой поиск с ограниченным несоответствием». 2005. «Архивная копия» (PDF) . Проверено 22 декабря 2007 г.

[1] Чжоу, Ронг; Хансен, Эрик А. (2005). «Поиск по лучу: интеграция обратного отслеживания с поиском по лучу» (PDF) . CiteSeer ^х: 10.1.1.71.4147 .

[furcy-2] Jump up to: ^а ^б Фурси, Дэвид. Кениг, Свен. «Лучевой поиск с ограниченным несоответствием». 2005. «Архивная копия» (PDF) . Проверено 22 декабря 2007 г.

[1]

[2]