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

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

Термин лучевой поиск был введён Раджем Редди из Университета Карнеги — Меллона в 1977 году<ref>Редди, Даббала Радж. Системы понимания речи: сводка результатов пятилетних исследований. Департамент компьютерных наук., 1977 год.</ref>.

Подробности

Лучевой поиск использует поиск в ширину для построения своего дерева поиска. На каждом уровне дерева он генерирует всех преемников состояний на текущем уровне, сортируя их в порядке возрастания эвристической стоимости<ref>Шаблон:Cite web</ref>. Однако он хранит только заранее определённое количество, [math]\displaystyle{ \beta }[/math] лучших состояний на каждом уровне (называемое шириной луча). Далее разворачиваются только эти состояния. Чем больше ширина луча, тем меньше состояний удаляется. При бесконечной ширине луча никакие состояния не сокращаются, а лучевой поиск идентичен поиску в ширину. Ширина луча ограничивает объём памяти, необходимый для выполнения поиска. Поскольку целевое состояние потенциально может быть сокращено, лучевой поиск приносит в жертву полноту (гарантия того, что алгоритм завершится решением, если оно существует). Лучевой поиск не является оптимальным (то есть нет гарантии, что будет найдено лучшее решение)<ref>Шаблон:Cite book Шаблон:Wayback</ref>.

Применение

Лучевой поиск чаще всего используется для обеспечения управляемости в больших системах с недостаточным объёмом памяти для хранения всего дерева поиска<ref name="furcy">Дэвид Фёрси, Свен Кёниг. Ограниченное несоответствие лучевого поиска. 2005.Шаблон:Cite web</ref>. Например, он использовался во многих системах машинного перевода<ref>Кристоф Тилльманн, Герман Ней. Переупорядочение слов и алгоритм лучевого поиска динамического программирования для статистического машинного перевода.Шаблон:Cite web</ref>. (На современном уровне техники сейчас в основном используются методы, основанные на нейронном машинном переводе.) Чтобы выбрать лучший перевод, каждая часть обрабатывается, и появляется множество различных способов перевода слов. Лучшие переводы в соответствии с их структурой предложений сохраняются, а остальные отбрасываются. Затем переводчик оценивает переводы по заданному критерию, выбирая перевод, который лучше всего соответствует целям. Первое использование лучевого поиска было в Системе Распознавания Речи Харпи, CMU 1976<ref>Брюс Лоуэрр. Система Распознавания Речи Харпи, Дипломная работа кандидата наук, Университет Карнеги — Меллона, 1976 год</ref>.

Варианты

Лучевой поиск был выполнен полностью путём объединения его с поиском в глубину, что привело к поиску по стеку лучей<ref>Чжоу Ронг, Эрик Хансен. Поиск по стеку лучей: Интеграция обратного отслеживания с лучевым поиском. 2005. http://www.aaai.org/Library/ICAPS/2005/icaps05-010.php Шаблон:Wayback</ref>, лучевому поиску в глубину<ref name="furcy"/> и с ограниченным поиском несоответствий<ref>Шаблон:CiteSeerX</ref>, что приводит к лучевому поиску с использованием обратного отслеживания ограниченного несоответствия<ref name="furcy"/> (BULB<ref>BULB — сокращение английского выражения Beam search Using Limited discrepancy Backtracking (рус. Лучевой поиск с Использованием Обратного отслеживания Ограниченного несоответствия).</ref>). Результирующие алгоритмы поиска — это алгоритмы в любое время, которые быстро находят хорошие, но, вероятно, неоптимальные решения, такие как лучевой поиск, затем возвращаются и продолжают поиск улучшенных решений до сходимости к оптимальному решению.

В контексте локального поиска мы называем локальным поиском луча конкретный алгоритм, который начинает выбирать [math]\displaystyle{ \beta }[/math] случайно сгенерированных состояний, а затем для каждого всегда рассматривает на уровне дерева поиска [math]\displaystyle{ \beta }[/math] новых состояний среди всех возможных преемников текущих состояний, пока не достигнет цели<ref>Шаблон:Cite web</ref><ref name="iitb">Шаблон:Cite web</ref>.

Поскольку локальный лучевой поиск часто заканчивается на локальных максимумах, обычным решением является выбор следующих [math]\displaystyle{ \beta }[/math] состояний случайным образом с вероятностью, зависящей от эвристической оценки состояний. Этот вид поиска называется стохастическим лучевым поиском<ref>Шаблон:Cite web</ref>.

Другими вариантами являются гибкий лучевой поиск и восстанавливающий лучевой поиск<ref name="iitb"/>.