В информатике Лучевой поиск — это эвристический , который исследует граф, расширяя перспективные узлы в ограниченном наборе. Лучевой поиск — это оптимизация поиска по первому наилучшему совпадению , которая снижает требования к памяти. Поиск по первому наилучшему совпадению — это поиск по графу, который упорядочивает все частные решения (состояния) в соответствии с некоторой эвристикой. Но при лучевом поиске в качестве кандидатов сохраняется только заранее определённое количество лучших частичных решений . Таким образом, это жадный алгоритм .

Термин лучевой поиск был введён Раджем Редди из Университета Карнеги — Меллона в 1977 году .

Подробности

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

Применение

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

Варианты

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

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

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

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

Примечания