Просмотр кода страницы Лучевой поиск

<noinclude>{{к удалению|2021-08-28}}</noinclude>
В [[Информатика|информатике]] '''Лучевой поиск''' — это [[Эвристический алгоритм|эвристический]] {{нп5|алгоритм поиска|||Search algorithm}}, который исследует граф, расширяя перспективные узлы в ограниченном наборе. Лучевой поиск — это оптимизация [[Поиск по первому наилучшему совпадению|поиска по первому наилучшему совпадению]], которая снижает требования к памяти. Поиск по первому наилучшему совпадению — это поиск по графу, который упорядочивает все частные решения (состояния) в соответствии с некоторой эвристикой. Но при лучевом поиске в качестве кандидатов сохраняется только заранее определённое количество лучших частичных решений<ref>{{Cite web|url=http://foldoc.org/index.cgi?query=beam+search&action=Search|title='''''FOLDOC — Компьютерный словарь'''''|website=foldoc.org|access-date=2016-04-11|archive-date=2020-01-25|archive-url=https://web.archive.org/web/20200125061837/http://foldoc.org/index.cgi?query=beam+search&action=Search|deadlink=no}}</ref>. Таким образом, это [[жадный алгоритм]].

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

== Подробности ==
Лучевой поиск использует [[поиск в ширину]] для построения своего [[Обход дерева|дерева поиска]]. На каждом уровне дерева он генерирует всех преемников состояний на текущем уровне, сортируя их в порядке возрастания эвристической стоимости<ref>{{Cite web|url=http://bradley.bradley.edu/~chris/searches.html|title='''''ПОИСК В БРИТАНСКОМ МУЗЕЕ'''''|website=bradley.bradley.edu|access-date=2016-04-11|archive-date=2018-05-06|archive-url=https://web.archive.org/web/20180506103828/http://bradley.bradley.edu/~chris/searches.html|deadlink=no}}</ref>. Однако он хранит только заранее определённое количество,  <math>\beta</math> лучших состояний на каждом уровне (называемое шириной луча). Далее разворачиваются только эти состояния. Чем больше ширина луча, тем меньше состояний удаляется. При бесконечной ширине луча никакие состояния не сокращаются, а лучевой поиск идентичен поиску в ширину. Ширина луча ограничивает объём памяти, необходимый для выполнения поиска. Поскольку целевое состояние потенциально может быть сокращено, лучевой поиск приносит в жертву полноту (гарантия того, что алгоритм завершится решением, если оно существует). Лучевой поиск не является оптимальным (то есть нет гарантии, что будет найдено лучшее решение)<ref>{{Cite book|url=https://books.google.com/books?id=X4mhySvjqUAC|title='''''Парадигмы программирования искусственного интеллекта: Примеры использования Common LISP'''''|author=[[Норвиг, Питер|Питер Норвиг]]|date=1992-01-01|publisher=Морган Кауфманн|isbn=9781558601918|language=en}} {{Wayback|url=https://books.google.com/books?id=X4mhySvjqUAC |date=20210420205523 }}</ref>.

== Применение ==
Лучевой поиск чаще всего используется для обеспечения управляемости в больших системах с недостаточным объёмом памяти для хранения всего дерева поиска<ref name="furcy">Дэвид Фёрси, Свен Кёниг. '''''Ограниченное несоответствие лучевого поиска'''''. 2005.{{cite web|url=http://www.ijcai.org/papers/0596.pdf
|title=Архивная копия|access-date=2007-12-22|archive-url=https://web.archive.org/web/20080516202406/http://www.ijcai.org/papers/0596.pdf|archive-date=2008-05-16}}</ref>. Например, он использовался во многих системах [[Машинный перевод|машинного перевода]]<ref>Кристоф Тилльманн, Герман Ней. '''''Переупорядочение слов и алгоритм лучевого поиска динамического программирования для статистического машинного перевода'''''.{{cite web|url=http://acl.ldc.upenn.edu/J/J03/J03-1005.pdf|title=Архивная копия|access-date=2007-12-22|archive-url=https://web.archive.org/web/20060618020933/http://acl.ldc.upenn.edu/J/J03/J03-1005.pdf
|archive-date=2006-06-18}}</ref>. (На современном уровне техники сейчас в основном используются методы, основанные на [[Нейронный машинный перевод|нейронном машинном переводе]].) Чтобы выбрать лучший перевод, каждая часть обрабатывается, и появляется множество различных способов перевода слов. Лучшие переводы в соответствии с их структурой предложений сохраняются, а остальные отбрасываются. Затем переводчик оценивает переводы по заданному критерию, выбирая перевод, который лучше всего соответствует целям. Первое использование лучевого поиска было в Системе Распознавания Речи Харпи, CMU 1976<ref>Брюс Лоуэрр. '''''Система Распознавания Речи Харпи''''',  Дипломная работа кандидата наук, Университет Карнеги — Меллона, 1976 год</ref>.

== Варианты ==
Лучевой поиск был выполнен [[Полная теория|полностью]] путём объединения его с [[Поиск в глубину|поиском в глубину]], что привело к ''поиску по стеку лучей''<ref>Чжоу Ронг, Эрик Хансен. '''''Поиск по стеку лучей: Интеграция обратного отслеживания с лучевым поиском'''''. 2005. http://www.aaai.org/Library/ICAPS/2005/icaps05-010.php {{Wayback|url=http://www.aaai.org/Library/ICAPS/2005/icaps05-010.php |date=20210420205518 }}</ref>, ''лучевому поиску в глубину''<ref name="furcy"/> и с ограниченным поиском несоответствий<ref>{{CiteSeerX|10.1.1.34.2426}}</ref>, что приводит к ''лучевому поиску с использованием обратного отслеживания ограниченного несоответствия''<ref name="furcy"/> (BULB<ref>'''BULB''' — сокращение [[Английский язык|английского]] выражения  '''''B'''eam search '''U'''sing '''L'''imited discrepancy '''B'''acktracking'' 
([[Русский язык|рус.]] ''Лучевой поиск с Использованием Обратного отслеживания Ограниченного несоответствия'').</ref>). Результирующие алгоритмы поиска — это ''алгоритмы в любое время'', которые быстро находят хорошие, но, вероятно, неоптимальные решения, такие как лучевой поиск, затем возвращаются и продолжают поиск улучшенных решений до сходимости к оптимальному решению.

В контексте [[Локальный поиск (оптимизация)|локального поиска]] мы называем ''локальным поиском луча'' конкретный алгоритм, который начинает выбирать <math>\beta</math> случайно сгенерированных состояний, а затем для каждого всегда рассматривает на уровне дерева поиска <math>\beta</math> новых состояний среди всех возможных преемников текущих состояний, пока не достигнет цели<ref>{{cite web|url=https://www.cs.unc.edu/~lazebnik/fall10/lec06_local_search.pdf
|title=Алгоритмы локального поиска|publisher=[[Университет Северной Каролины в Чапел-Хилле]], Факультет компьютерных наук|author=Светлана Лазебник|author-link=Svetlana Lazebnik|archive-url=https://web.archive.org/web/20110705070334/http://www.cs.unc.edu/~lazebnik/fall10/lec06_local_search.pdf|archive-date=2011-07-05}}</ref><ref name="iitb">{{cite web|url=https://www.cse.iitb.ac.in/~cs344/2011/slides/cs344-beam-search-2feb11.pptx|title=Лучевой поиск
|publisher=Индийский технологический институт, Бомбей, Факультет Компьютерных Наук и Инженерии (КНИ)|pages=39-40|author=Пушпак Бхаттачарья|archive-url=https://web.archive.org/web/20181121123057/https://www.cse.iitb.ac.in/~cs344/2011/slides/cs344-beam-search-2feb11.pptx|archive-date=2018-11-21}}</ref>.

Поскольку локальный лучевой поиск часто заканчивается на локальных максимумах, обычным решением является выбор следующих <math>\beta</math> состояний случайным образом с вероятностью, зависящей от эвристической оценки состояний. Этот вид поиска называется ''стохастическим лучевым поиском''<ref>{{cite web
|url=http://www-users.cselabs.umn.edu/classes/Fall-2017/csci4511/slides/week4/9.28.17.pdf|title=Локальный поиск|author=Джеймс Паркер|publisher=[[Миннесотский университет]]|date=2017-09-28|archive-url=https://web.archive.org/web/20171013150401/http://www-users.cselabs.umn.edu/classes/Fall-2017/csci4511/slides/week4/9.28.17.pdf|archive-date=2017-10-13|access-date=2018-11-21}}</ref>.

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

== Примечания ==
{{примечания}}

{{Алгоритмы поиска на графах}}

[[Категория:Алгоритмы поиска]]