Поиск в ширину (beam search): эффективный эвристический алгоритм для исследования графов. Оптимизация памяти по сравнению с best-first search. ИИ, компьютерные науки.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Эвристический алгоритм поиска
Heuristic search algorithm
В информатике, поиск с лучом (beam search) — это эвристический алгоритм поиска, исследующий граф путем расширения наиболее перспективных узлов в ограниченном множестве. Поиск с лучом является модификацией поиска в ширину по наилучшему первому, снижающей требования к памяти. Поиск в ширину по наилучшему первому — это поиск по графу, который упорядочивает все частичные решения (состояния) в соответствии с некоторой эвристикой. Однако в поиске с лучом сохраняется лишь заранее заданное количество лучших частичных решений в качестве кандидатов. Таким образом, это жадный алгоритм.
In computer science, beam search is a heuristic search algorithm that explores a graph by expanding the most promising node in a limited set. Beam search is an modification of best first search that reduces its memory requirements. Best first search is a graph search which orders all partial solutions (states) according to some heuristic. But in beam search, only a predetermined number of best partial solutions are kept as candidates. It is thus a greedy algorithm.
Подробности
Поиск по пучкам использует поиск в ширину для построения дерева поиска. На каждом уровне дерева он генерирует всех преемников состояний текущего уровня, сортируя их по возрастанию эвристической оценки. Однако он сохраняет только заранее заданное количество, , лучших состояний на каждом уровне (так называемая ширина пучка). Только эти состояния расширяются далее. Чем больше ширина пучка, тем меньше состояний отбрасывается. При бесконечной ширине пучка ни одно состояние не отбрасывается, и поиск по пучкам идентичен поиску в ширину с лучшей эвристикой. И наоборот, ширина пучка, равная 1, соответствует алгоритму подъема на холм. (В настоящее время передовые технологии в основном используют методы, основанные на нейронном машинном переводе, особенно большие языковые модели.) Для выбора наилучшего перевода каждая часть текста обрабатывается, и появляется множество различных вариантов перевода слов. Наиболее удачные переводы, согласно структуре предложения, сохраняются, а остальные отбрасываются. Затем переводчик оценивает переводы по заданному критерию, выбирая перевод, который наилучшим образом соответствует поставленным задачам.
Beam search uses breadth first search to build its search tree. At each level of the tree, it generates all successors of the states at the current level, sorting them in increasing order of heuristic cost. However, it only stores a predetermined number, , of best states at each level (called the beam width). Only those states are expanded next. The greater the beam width, the fewer states are pruned. With an infinite beam width, no states are pruned and beam search is identical to best first search. Conversely, a beam width of 1 corresponds to a hill climbing algorithm. (The state of the art now primarily uses neural machine translation based methods, especially large language models) To select the best translation, each part is processed, and many different ways of translating the words appear. The top best translations according to their sentence structures are kept, and the rest are discarded. The translator then evaluates the translations according to a given criterion, choosing the translation which best keeps the goals.
История
Система распознавания речи Harpy (представленная в диссертации 1976 года) стала первым применением метода, который впоследствии получил название "поиск луча". Хотя изначально эта процедура называлась "моделью поиска по локациям", термин "поиск луча" уже использовался к 1977 году.
The Harpy Speech Recognition System (introduced in a 1976 dissertation) was the first use of what would become known as beam search. While the procedure was originally referred to as the "locus model of search", the term "beam search" was already in use by 1977.