|
Лучевой поискВ информатике Лучевой поиск — это эвристический алгоритм поиска[англ.], который исследует граф, расширяя перспективные узлы в ограниченном наборе. Лучевой поиск — это оптимизация поиска по первому наилучшему совпадению, которая снижает требования к памяти. Поиск по первому наилучшему совпадению — это поиск по графу, который упорядочивает все частные решения (состояния) в соответствии с некоторой эвристикой. Но при лучевом поиске в качестве кандидатов сохраняется только заранее определённое количество лучших частичных решений[1]. Таким образом, это жадный алгоритм. Термин лучевой поиск был введён Раджем Редди из Университета Карнеги — Меллона в 1977 году[2]. ПодробностиЛучевой поиск использует поиск в ширину для построения своего дерева поиска. На каждом уровне дерева он генерирует всех преемников состояний на текущем уровне, сортируя их в порядке возрастания эвристической стоимости[3]. Однако он хранит только заранее определённое количество, лучших состояний на каждом уровне (называемое шириной луча). Далее разворачиваются только эти состояния. Чем больше ширина луча, тем меньше состояний удаляется. При бесконечной ширине луча никакие состояния не сокращаются, а лучевой поиск идентичен поиску в ширину. Ширина луча ограничивает объём памяти, необходимый для выполнения поиска. Поскольку целевое состояние потенциально может быть сокращено, лучевой поиск приносит в жертву полноту (гарантия того, что алгоритм завершится решением, если оно существует). Лучевой поиск не является оптимальным (то есть нет гарантии, что будет найдено лучшее решение)[4]. ПрименениеЛучевой поиск чаще всего используется для обеспечения управляемости в больших системах с недостаточным объёмом памяти для хранения всего дерева поиска[5]. Например, он использовался во многих системах машинного перевода[6]. (На современном уровне техники сейчас в основном используются методы, основанные на нейронном машинном переводе.) Чтобы выбрать лучший перевод, каждая часть обрабатывается, и появляется множество различных способов перевода слов. Лучшие переводы в соответствии с их структурой предложений сохраняются, а остальные отбрасываются. Затем переводчик оценивает переводы по заданному критерию, выбирая перевод, который лучше всего соответствует целям. Первое использование лучевого поиска было в Системе Распознавания Речи Харпи, CMU 1976[7]. ВариантыЛучевой поиск был выполнен полностью путём объединения его с поиском в глубину, что привело к поиску по стеку лучей[8], лучевому поиску в глубину[5] и с ограниченным поиском несоответствий[9], что приводит к лучевому поиску с использованием обратного отслеживания ограниченного несоответствия[5] (BULB[10]). Результирующие алгоритмы поиска — это алгоритмы в любое время, которые быстро находят хорошие, но, вероятно, неоптимальные решения, такие как лучевой поиск, затем возвращаются и продолжают поиск улучшенных решений до сходимости к оптимальному решению. В контексте локального поиска мы называем локальным поиском луча конкретный алгоритм, который начинает выбирать случайно сгенерированных состояний, а затем для каждого всегда рассматривает на уровне дерева поиска новых состояний среди всех возможных преемников текущих состояний, пока не достигнет цели[11][12]. Поскольку локальный лучевой поиск часто заканчивается на локальных максимумах, обычным решением является выбор следующих состояний случайным образом с вероятностью, зависящей от эвристической оценки состояний. Этот вид поиска называется стохастическим лучевым поиском[13]. Другими вариантами являются гибкий лучевой поиск и восстанавливающий лучевой поиск[12]. Примечания
|
