Поиск луча
В информатике . лучевой поиск — это эвристический алгоритм поиска , который исследует граф, расширяя наиболее перспективный узел в ограниченном наборе Лучевой поиск — это модификация поиска по принципу «наилучшее первое» , которая снижает требования к памяти. Поиск по принципу «сначала лучшее» — это поиск по графу, который упорядочивает все частичные решения (состояния) в соответствии с некоторой эвристикой. Но при поиске луча в качестве кандидатов сохраняется только заранее определенное количество лучших частичных решений. [1] Таким образом, это жадный алгоритм .
Подробности
[ редактировать ]Лучевой поиск использует поиск в ширину для построения дерева поиска . На каждом уровне дерева он генерирует всех наследников состояний текущего уровня, сортируя их в порядке возрастания эвристической стоимости. [2] Однако он хранит только заранее определенное число, , лучших состояний на каждом уровне (называемый шириной луча). Далее будут расширены только эти состояния. Чем больше ширина луча, тем меньше состояний отсекается. При бесконечной ширине луча никакие состояния не отсекаются, а поиск луча идентичен поиску по принципу «сначала лучшее» . [3] И наоборот, ширина луча, равная 1, соответствует алгоритму восхождения на холм . [3] Ширина луча ограничивает объем памяти, необходимый для выполнения поиска. Поскольку целевое состояние потенциально может быть сокращено, лучевой поиск жертвует полнотой (гарантией того, что алгоритм завершится решением, если оно существует). Поиск луча не является оптимальным (то есть нет гарантии, что он найдет лучшее решение).
Использование
[ редактировать ]Лучевой поиск чаще всего используется для обеспечения управляемости в больших системах с недостаточным объемом памяти для хранения всего дерева поиска. [4] Например, он использовался во многих машинного перевода . системах [5] (Современный уровень техники в настоящее время в основном использует нейронном машинном переводе методы, основанные на , особенно большие языковые модели .) Чтобы выбрать лучший перевод, каждая часть обрабатывается, и появляется множество различных способов перевода слов. Топ лучших переводов по структуре предложений сохраняется, а остальные отбрасываются. Затем переводчик оценивает переводы по заданному критерию, выбирая тот перевод, который лучше всего соответствует поставленным целям.
История
[ редактировать ]Система распознавания речи Harpy (представлена в диссертации 1976 г.) [6] ) был первым применением того, что впоследствии стало известно как поиск луча. [7] Первоначально эта процедура называлась «локусной моделью поиска», но к 1977 году уже использовался термин «лучевой поиск». [8]
Варианты
[ редактировать ]Поиск луча был завершен за счет объединения его с поиском в глубину , что привело к поиску стека лучей. [9] и поиск луча в глубину , [4] и с ограниченным поиском несоответствий, [4] что приводит к поиску луча с использованием обратного отслеживания с ограниченным расхождением [4] (ЛАМПОЧКА). Получающиеся в результате алгоритмы поиска представляют собой алгоритмы, которые в любое время быстро находят хорошие, но, вероятно, неоптимальные решения, например поиск луча, затем возвращаются назад и продолжают находить улучшенные решения до тех пор, пока не достигнут оптимального решения.
В контексте локального поиска мы называем локальным поиском луча определенный алгоритм, который начинает выборку. случайно сгенерированные состояния, а затем для каждого уровня дерева поиска всегда учитывается новых государств среди всех возможных преемников нынешних, пока не достигнет цели. [10] [11]
Поскольку поиск локального луча часто заканчивается на локальных максимумах, общим решением является выбор следующего состояния случайным образом, с вероятностью, зависящей от эвристической оценки состояний. Этот вид поиска называется стохастическим лучевым поиском . [12]
Другими вариантами являются гибкий поиск луча и поиск восстанавливающегося луча . [11]
Ссылки
[ редактировать ]- ^ «лучевой поиск» . Бесплатный онлайн-словарь по информатике . Проверено 27 марта 2024 г.
- ^ «ПОИСК ПО БРИТАНСКОМУ МУЗЕЮ» . bradley.bradley.edu . Проверено 11 апреля 2016 г.
- ^ Jump up to: а б Норвиг, Питер (1992). Парадигмы программирования искусственного интеллекта: примеры использования Common LISP . Морган Кауфманн. п. 196. ИСБН 9781558601918 .
- ^ Jump up to: а б с д Фурси, Д.; Кениг, С. (2005). «Поиск луча с ограниченным расхождением» . Материалы 19-й международной совместной конференции по искусственному интеллекту . Морган Кауфманн. стр. 125–131.
- ^ Тильманн, К.; Ней, Х. (2003). «Переупорядочение слов и алгоритм динамического программирования для статистического машинного перевода» . Компьютерная лингвистика . 29 (1): 97–133. дои : 10.1162/089120103321337458 . S2CID 7829066 .
- ^ Лоуэр, Брюс Т. (1976). Система распознавания речи Harpy (PDF) (доктор философии). Университет Карнеги-Меллон.
- ^ Ой, Пэн Си; Мортон, Томас Э. (1988). «Поиск с фильтрацией луча в планировани膻 . Международный журнал производственных исследований . 26 (1): 35–62. дои : 10.1080/00207548808947840 . ISSN 0020-7543 .
- ^ Центр военной технической информации (1 августа 1977 г.). DTIC ADA049288: Системы понимания речи. Краткое изложение результатов пятилетних исследований в Университете Карнеги-Меллона . п. 6.
- ^ Чжоу, Ронг; Хансен, Эрик (2005). «Поиск по лучу: интеграция обратного отслеживания с поиском по лучу» . ИКАПС . стр. 90–98. Архивировано из оригинала 20 апреля 2021 г. Проверено 9 апреля 2011 г.
- ^ Светлана Лазебник . «Алгоритмы локального поиска» (PDF) . Университет Северной Каролины в Чапел-Хилл, факультет компьютерных наук. п. 15. Архивировано (PDF) из оригинала 5 июля 2011 г.
- ^ Jump up to: а б Пушпак Бхаттачарья. «Поиск луча» . Индийский технологический институт Бомбея, факультет компьютерных наук и инженерии (CSE). стр. 39–40. Архивировано из оригинала 21 ноября 2018 г.
- ^ Джеймс Паркер (28 сентября 2017 г.). «Локальный поиск» (PDF) . Университет Миннесоты. п. 17. Архивировано (PDF) из оригинала 13 октября 2017 г. Проверено 21 ноября 2018 г.