Лучевой поиск

Лучевой поиск использует поиск в ширину для построения своего дерева поиска. На каждом уровне дерева он генерирует всех преемников состояний на текущем уровне, сортируя их в порядке возрастания эвристической стоимости^[3]. Однако он хранит только заранее определённое количество, ${\displaystyle \beta }$ лучших состояний на каждом уровне (называемое шириной луча). Далее разворачиваются только эти состояния. Чем больше ширина луча, тем меньше состояний удаляется. При бесконечной ширине луча никакие состояния не сокращаются, а лучевой поиск идентичен поиску в ширину. Ширина луча ограничивает объём памяти, необходимый для выполнения поиска. Поскольку целевое состояние потенциально может быть сокращено, лучевой поиск приносит в жертву полноту (гарантия того, что алгоритм завершится решением, если оно существует). Лучевой поиск не является оптимальным (то есть нет гарантии, что будет найдено лучшее решение)^[4].

Лучевой поиск чаще всего используется для обеспечения управляемости в больших системах с недостаточным объёмом памяти для хранения всего дерева поиска^[5]. Например, он использовался во многих системах машинного перевода^[6]. (На современном уровне техники сейчас в основном используются методы, основанные на нейронном машинном переводе.) Чтобы выбрать лучший перевод, каждая часть обрабатывается, и появляется множество различных способов перевода слов. Лучшие переводы в соответствии с их структурой предложений сохраняются, а остальные отбрасываются. Затем переводчик оценивает переводы по заданному критерию, выбирая перевод, который лучше всего соответствует целям. Первое использование лучевого поиска было в Системе Распознавания Речи Харпи, CMU 1976^[7].

Лучевой поиск был выполнен полностью путём объединения его с поиском в глубину, что привело к поиску по стеку лучей^[8], лучевому поиску в глубину^[5] и с ограниченным поиском несоответствий^[9], что приводит к лучевому поиску с использованием обратного отслеживания ограниченного несоответствия^[5] (BULB^[10]). Результирующие алгоритмы поиска — это алгоритмы в любое время, которые быстро находят хорошие, но, вероятно, неоптимальные решения, такие как лучевой поиск, затем возвращаются и продолжают поиск улучшенных решений до сходимости к оптимальному решению.

В контексте локального поиска мы называем локальным поиском луча конкретный алгоритм, который начинает выбирать ${\displaystyle \beta }$ случайно сгенерированных состояний, а затем для каждого всегда рассматривает на уровне дерева поиска ${\displaystyle \beta }$ новых состояний среди всех возможных преемников текущих состояний, пока не достигнет цели^[11][12].

Поскольку локальный лучевой поиск часто заканчивается на локальных максимумах, обычным решением является выбор следующих ${\displaystyle \beta }$ состояний случайным образом с вероятностью, зависящей от эвристической оценки состояний. Этот вид поиска называется стохастическим лучевым поиском^[13].

Другими вариантами являются гибкий лучевой поиск и восстанавливающий лучевой поиск^[12].