Перейти к содержанию

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

Добавить ссылки
Материал из Мегавики — свободной энциклопедии
Данная страница не проверялась участниками с соответствующими правами.

В информатике Лучевой поиск — это эвристический алгоритм поиска[англ.], который исследует граф, расширяя перспективные узлы в ограниченном наборе. Лучевой поиск — это оптимизация поиска по первому наилучшему совпадению, которая снижает требования к памяти. Поиск по первому наилучшему совпадению — это поиск по графу, который упорядочивает все частные решения (состояния) в соответствии с некоторой эвристикой. Но при лучевом поиске в качестве кандидатов сохраняется только заранее определённое количество лучших частичных решений[1]. Таким образом, это жадный алгоритм.

Термин лучевой поиск был введён Раджем Редди из Университета Карнеги — Меллона в 1977 году[2].

Подробности[править]

Лучевой поиск использует поиск в ширину для построения своего дерева поиска. На каждом уровне дерева он генерирует всех преемников состояний на текущем уровне, сортируя их в порядке возрастания эвристической стоимости[3]. Однако он хранит только заранее определённое количество, β лучших состояний на каждом уровне (называемое шириной луча). Далее разворачиваются только эти состояния. Чем больше ширина луча, тем меньше состояний удаляется. При бесконечной ширине луча никакие состояния не сокращаются, а лучевой поиск идентичен поиску в ширину. Ширина луча ограничивает объём памяти, необходимый для выполнения поиска. Поскольку целевое состояние потенциально может быть сокращено, лучевой поиск приносит в жертву полноту (гарантия того, что алгоритм завершится решением, если оно существует). Лучевой поиск не является оптимальным (то есть нет гарантии, что будет найдено лучшее решение)[4].

Применение[править]

Лучевой поиск чаще всего используется для обеспечения управляемости в больших системах с недостаточным объёмом памяти для хранения всего дерева поиска[5]. Например, он использовался во многих системах машинного перевода[6]. (На современном уровне техники сейчас в основном используются методы, основанные на нейронном машинном переводе.) Чтобы выбрать лучший перевод, каждая часть обрабатывается, и появляется множество различных способов перевода слов. Лучшие переводы в соответствии с их структурой предложений сохраняются, а остальные отбрасываются. Затем переводчик оценивает переводы по заданному критерию, выбирая перевод, который лучше всего соответствует целям. Первое использование лучевого поиска было в Системе Распознавания Речи Харпи, CMU 1976[7].

Варианты[править]

Лучевой поиск был выполнен полностью путём объединения его с поиском в глубину, что привело к поиску по стеку лучей[8], лучевому поиску в глубину[5] и с ограниченным поиском несоответствий[9], что приводит к лучевому поиску с использованием обратного отслеживания ограниченного несоответствия[5] (BULB[10]). Результирующие алгоритмы поиска — это алгоритмы в любое время, которые быстро находят хорошие, но, вероятно, неоптимальные решения, такие как лучевой поиск, затем возвращаются и продолжают поиск улучшенных решений до сходимости к оптимальному решению.

В контексте локального поиска мы называем локальным поиском луча конкретный алгоритм, который начинает выбирать β случайно сгенерированных состояний, а затем для каждого всегда рассматривает на уровне дерева поиска β новых состояний среди всех возможных преемников текущих состояний, пока не достигнет цели[11][12].

Поскольку локальный лучевой поиск часто заканчивается на локальных максимумах, обычным решением является выбор следующих β состояний случайным образом с вероятностью, зависящей от эвристической оценки состояний. Этот вид поиска называется стохастическим лучевым поиском[13].

Другими вариантами являются гибкий лучевой поиск и восстанавливающий лучевой поиск[12].

Примечания[править]

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