Лучевой поиск
 | Эту статью предлагается удалить. |
В информатике Лучевой поиск — это эвристический алгоритм поиска, который исследует граф, расширяя перспективные узлы в ограниченном наборе. Лучевой поиск — это оптимизация поиска по первому наилучшему совпадению, которая снижает требования к памяти. Поиск по первому наилучшему совпадению — это поиск по графу, который упорядочивает все частные решения (состояния) в соответствии с некоторой эвристикой. Но при лучевом поиске в качестве кандидатов сохраняется только заранее определённое количество лучших частичных решений[1]. Таким образом, это жадный алгоритм.
Термин лучевой поиск был введён Раджем Редди из Университета Карнеги — Меллона в 1977 году[2].
Подробности[править | править код]
Лучевой поиск использует поиск в ширину для построения своего дерева поиска. На каждом уровне дерева он генерирует всех преемников состояний на текущем уровне, сортируя их в порядке возрастания эвристической стоимости[3]. Однако он хранит только заранее определённое количество, лучших состояний на каждом уровне (называемое шириной луча). Далее разворачиваются только эти состояния. Чем больше ширина луча, тем меньше состояний удаляется. При бесконечной ширине луча никакие состояния не сокращаются, а лучевой поиск идентичен поиску в ширину. Ширина луча ограничивает объём памяти, необходимый для выполнения поиска. Поскольку целевое состояние потенциально может быть сокращено, лучевой поиск приносит в жертву полноту (гарантия того, что алгоритм завершится решением, если оно существует). Лучевой поиск не является оптимальным (то есть нет гарантии, что будет найдено лучшее решение)[4].
Применение[править | править код]
Лучевой поиск чаще всего используется для обеспечения управляемости в больших системах с недостаточным объёмом памяти для хранения всего дерева поиска[5]. Например, он использовался во многих системах машинного перевода[6]. (На современном уровне техники сейчас в основном используются методы, основанные на нейронном машинном переводе.) Чтобы выбрать лучший перевод, каждая часть обрабатывается, и появляется множество различных способов перевода слов. Лучшие переводы в соответствии с их структурой предложений сохраняются, а остальные отбрасываются. Затем переводчик оценивает переводы по заданному критерию, выбирая перевод, который лучше всего соответствует целям. Первое использование лучевого поиска было в Системе Распознавания Речи Харпи, CMU 1976[7].
Варианты[править | править код]
Лучевой поиск был выполнен полностью путём объединения его с поиском в глубину, что привело к поиску по стеку лучей[8], лучевому поиску в глубину[5] и с ограниченным поиском несоответствий[9], что приводит к лучевому поиску с использованием обратного отслеживания ограниченного несоответствия[5] (BULB[10]). Результирующие алгоритмы поиска — это алгоритмы в любое время, которые быстро находят хорошие, но, вероятно, неоптимальные решения, такие как лучевой поиск, затем возвращаются и продолжают поиск улучшенных решений до сходимости к оптимальному решению.
В контексте локального поиска мы называем локальным поиском луча конкретный алгоритм, который начинает выбирать случайно сгенерированных состояний, а затем для каждого всегда рассматривает на уровне дерева поиска новых состояний среди всех возможных преемников текущих состояний, пока не достигнет цели[11][12].
Поскольку локальный лучевой поиск часто заканчивается на локальных максимумах, обычным решением является выбор следующих состояний случайным образом с вероятностью, зависящей от эвристической оценки состояний. Этот вид поиска называется стохастическим лучевым поиском[13].
Другими вариантами являются гибкий лучевой поиск и восстанавливающий лучевой поиск[12].
Примечания[править | править код]
- ↑ FOLDOC — Компьютерный словарь. foldoc.org. Дата обращения: 11 апреля 2016. Архивировано 25 января 2020 года.
- ↑ Редди, Даббала Радж. Системы понимания речи: сводка результатов пятилетних исследований. Департамент компьютерных наук., 1977 год.
- ↑ ПОИСК В БРИТАНСКОМ МУЗЕЕ. bradley.bradley.edu. Дата обращения: 11 апреля 2016. Архивировано 6 мая 2018 года.
- ↑ Питер Норвиг. Парадигмы программирования искусственного интеллекта: Примеры использования Common LISP : [англ.]. — Морган Кауфманн, 1992-01-01. — ISBN 9781558601918. Источник. Дата обращения: 22 августа 2021. Архивировано 20 апреля 2021 года.
- ↑ 1 2 3 Дэвид Фёрси, Свен Кёниг. Ограниченное несоответствие лучевого поиска. 2005.Архивная копия. Дата обращения: 22 декабря 2007. Архивировано 16 мая 2008 года.
- ↑ Кристоф Тилльманн, Герман Ней. Переупорядочение слов и алгоритм лучевого поиска динамического программирования для статистического машинного перевода.Архивная копия. Дата обращения: 22 декабря 2007. Архивировано 18 июня 2006 года.
- ↑ Брюс Лоуэрр. Система Распознавания Речи Харпи, Дипломная работа кандидата наук, Университет Карнеги — Меллона, 1976 год
- ↑ Чжоу Ронг, Эрик Хансен. Поиск по стеку лучей: Интеграция обратного отслеживания с лучевым поиском. 2005. http://www.aaai.org/Library/ICAPS/2005/icaps05-010.php Архивная копия от 20 апреля 2021 на Wayback Machine
- ↑ CiteSeerx: 10.1.1.34.2426
- ↑ BULB — сокращение английского выражения Beam search Using Limited discrepancy Backtracking (рус. Лучевой поиск с Использованием Обратного отслеживания Ограниченного несоответствия).
- ↑ Светлана Лазебник. Алгоритмы локального поиска. Университет Северной Каролины в Чапел-Хилле, Факультет компьютерных наук. Архивировано 5 июля 2011 года.
- ↑ 1 2 Пушпак Бхаттачарья. Лучевой поиск 39-40. Индийский технологический институт, Бомбей, Факультет Компьютерных Наук и Инженерии (КНИ). Архивировано 21 ноября 2018 года.
- ↑ Джеймс Паркер. Локальный поиск. Миннесотский университет (28 сентября 2017). Дата обращения: 21 ноября 2018. Архивировано 13 октября 2017 года.
