Русская Википедия:Лучевой поиск
Шаблон:К удалению В информатике Лучевой поиск — это эвристический Шаблон:Нп5, который исследует граф, расширяя перспективные узлы в ограниченном наборе. Лучевой поиск — это оптимизация поиска по первому наилучшему совпадению, которая снижает требования к памяти. Поиск по первому наилучшему совпадению — это поиск по графу, который упорядочивает все частные решения (состояния) в соответствии с некоторой эвристикой. Но при лучевом поиске в качестве кандидатов сохраняется только заранее определённое количество лучших частичных решений[1]. Таким образом, это жадный алгоритм.
Термин лучевой поиск был введён Раджем Редди из Университета Карнеги — Меллона в 1977 году[2].
Подробности
Лучевой поиск использует поиск в ширину для построения своего дерева поиска. На каждом уровне дерева он генерирует всех преемников состояний на текущем уровне, сортируя их в порядке возрастания эвристической стоимости[3]. Однако он хранит только заранее определённое количество, <math>\beta</math> лучших состояний на каждом уровне (называемое шириной луча). Далее разворачиваются только эти состояния. Чем больше ширина луча, тем меньше состояний удаляется. При бесконечной ширине луча никакие состояния не сокращаются, а лучевой поиск идентичен поиску в ширину. Ширина луча ограничивает объём памяти, необходимый для выполнения поиска. Поскольку целевое состояние потенциально может быть сокращено, лучевой поиск приносит в жертву полноту (гарантия того, что алгоритм завершится решением, если оно существует). Лучевой поиск не является оптимальным (то есть нет гарантии, что будет найдено лучшее решение)[4].
Применение
Лучевой поиск чаще всего используется для обеспечения управляемости в больших системах с недостаточным объёмом памяти для хранения всего дерева поиска[5]. Например, он использовался во многих системах машинного перевода[6]. (На современном уровне техники сейчас в основном используются методы, основанные на нейронном машинном переводе.) Чтобы выбрать лучший перевод, каждая часть обрабатывается, и появляется множество различных способов перевода слов. Лучшие переводы в соответствии с их структурой предложений сохраняются, а остальные отбрасываются. Затем переводчик оценивает переводы по заданному критерию, выбирая перевод, который лучше всего соответствует целям. Первое использование лучевого поиска было в Системе Распознавания Речи Харпи, CMU 1976[7].
Варианты
Лучевой поиск был выполнен полностью путём объединения его с поиском в глубину, что привело к поиску по стеку лучей[8], лучевому поиску в глубину[5] и с ограниченным поиском несоответствий[9], что приводит к лучевому поиску с использованием обратного отслеживания ограниченного несоответствия[5] (BULB[10]). Результирующие алгоритмы поиска — это алгоритмы в любое время, которые быстро находят хорошие, но, вероятно, неоптимальные решения, такие как лучевой поиск, затем возвращаются и продолжают поиск улучшенных решений до сходимости к оптимальному решению.
В контексте локального поиска мы называем локальным поиском луча конкретный алгоритм, который начинает выбирать <math>\beta</math> случайно сгенерированных состояний, а затем для каждого всегда рассматривает на уровне дерева поиска <math>\beta</math> новых состояний среди всех возможных преемников текущих состояний, пока не достигнет цели[11][12].
Поскольку локальный лучевой поиск часто заканчивается на локальных максимумах, обычным решением является выбор следующих <math>\beta</math> состояний случайным образом с вероятностью, зависящей от эвристической оценки состояний. Этот вид поиска называется стохастическим лучевым поиском[13].
Другими вариантами являются гибкий лучевой поиск и восстанавливающий лучевой поиск[12].
Примечания
Шаблон:Алгоритмы поиска на графах
- ↑ Шаблон:Cite web
- ↑ Редди, Даббала Радж. Системы понимания речи: сводка результатов пятилетних исследований. Департамент компьютерных наук., 1977 год.
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite book Шаблон:Wayback
- ↑ 5,0 5,1 5,2 Дэвид Фёрси, Свен Кёниг. Ограниченное несоответствие лучевого поиска. 2005.Шаблон:Cite web
- ↑ Кристоф Тилльманн, Герман Ней. Переупорядочение слов и алгоритм лучевого поиска динамического программирования для статистического машинного перевода.Шаблон:Cite web
- ↑ Брюс Лоуэрр. Система Распознавания Речи Харпи, Дипломная работа кандидата наук, Университет Карнеги — Меллона, 1976 год
- ↑ Чжоу Ронг, Эрик Хансен. Поиск по стеку лучей: Интеграция обратного отслеживания с лучевым поиском. 2005. http://www.aaai.org/Library/ICAPS/2005/icaps05-010.php Шаблон:Wayback
- ↑ Шаблон:CiteSeerX
- ↑ BULB — сокращение английского выражения Beam search Using Limited discrepancy Backtracking (рус. Лучевой поиск с Использованием Обратного отслеживания Ограниченного несоответствия).
- ↑ Шаблон:Cite web
- ↑ 12,0 12,1 Шаблон:Cite web
- ↑ Шаблон:Cite web
