Поиск луча - Beam search

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

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

Подробности

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

Использует

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

Варианты

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

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

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

Другие варианты гибкого поиск луча и восстановление поиск луча .

использованная литература