Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Алгоритмы поиска по графам и деревьям
Списки
похожие темы

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

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

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

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

Как правило, поиск луча возвращает первое найденное решение. Поиск луча для машинного перевода - это другой случай: по достижении настроенной максимальной глубины поиска (т. Е. Длины перевода) алгоритм оценит решения, найденные во время поиска на разных глубинах, и вернет лучшее (с наибольшей вероятностью).

Ширина луча может быть фиксированной или переменной. Один подход, в котором используется переменная ширина луча, начинается с минимальной ширины. Если решение не найдено, балку расширяют и процедуру повторяют. [4]

Использует [ редактировать ]

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

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

Поиск луча был завершен путем объединения его с поиском в глубину , что привело к поиску по сумме лучей [8] и поиску луча в глубину , [5] и с ограниченным поиском несоответствия [9], что привело к поиску луча с использованием ограниченного обратного отслеживания несоответствия. [5] (ЛАМПОЧКА). Результирующие алгоритмы поиска - это всегда алгоритмы, которые быстро находят хорошие, но, вероятно, неоптимальные решения, такие как поиск луча, затем возвращаются и продолжают находить улучшенные решения до сходимости к оптимальному решению.

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

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

Другие варианты гибкого поиск луча и восстановление поиск луча . [11]

Ссылки [ править ]

  1. ^ «FOLDOC - Вычислительный словарь» . foldoc.org . Проверено 11 апреля 2016 .
  2. ^ Редди, Д. Радж. «Системы понимания речи: сводка результатов пятилетних исследований. Департамент компьютерных наук», 1977.
  3. ^ "ПОИСК БРИТАНСКОГО МУЗЕЯ" . bradley.bradley.edu . Проверено 11 апреля 2016 .
  4. ^ Норвиг, Питер (1992-01-01). Парадигмы программирования искусственного интеллекта: примеры из общего LISP . Морган Кауфманн. ISBN 9781558601918.
  5. ^ a b c Фёрси, Дэвид. Кениг, Свен. «Поиск пучка ограниченного несоответствия». 2005. «Архивная копия» (PDF) . Архивировано из оригинального (PDF) 16 мая 2008 года . Проверено 22 декабря 2007 . CS1 maint: заархивированная копия как заголовок ( ссылка )
  6. ^ Тилльманн, Кристоф. Ней, Германн. "Переупорядочивание слов и алгоритм поиска луча динамического программирования для статистического машинного перевода". «Архивная копия» (PDF) . Архивировано из оригинального (PDF) 18 июня 2006 года . Проверено 22 декабря 2007 . CS1 maint: заархивированная копия как заголовок ( ссылка )
  7. ^ Лоуэрре, Брюс. «Система распознавания речи гарпий», д.т.н. дипломная работа, Университет Карнеги-Меллона, 1976 г.
  8. ^ Чжоу, Ронг. Хансен, Эрик. "Поиск по пучку: интеграция обратного отслеживания с поиском по пучку". 2005. http://www.aaai.org/Library/ICAPS/2005/icaps05-010.php
  9. ^ CiteSeer x :  10.1.1.34.2426
  10. ↑ Светлана Лазебник . «Алгоритмы локального поиска» (PDF) . Университет Северной Каролины в Чапел-Хилл, факультет компьютерных наук. п. 15. Архивировано (PDF) из оригинала 05.07.2011.
  11. ^ а б Пушпак Бхаттачарья. «Поиск луча» . Индийский технологический институт в Бомбее, факультет компьютерных наук и инженерии (CSE). С. 39–40. Архивировано 21 ноября 2018 года.
  12. ^ Джеймс Паркер (2017-09-28). «Локальный поиск» (PDF) . Университет Миннесоты. п. 17. Архивировано (PDF) из оригинала 13.10.2017 . Проверено 21 ноября 2018 .