Главная arrow Поиск arrow Локальный поиск
Как начинался компьютер
Компьютерная революция
Двоичный код
Разработки военных лет
Интегральные микросхемы
Микрокомпьютер
Персоны
Сеть
Язык компьютера
Развитие ПО
Гибкие системы
Средства разработки
Информатика
Вычислительная наука
Операционные системы
Искусственный интеллект
Предыстория
Поиск
Знания и рассуждения
Логика
Робототехника
 

 
Локальный лучевой поиск Печать
Стремление преодолеть ограничения, связанные с нехваткой памяти, привело к тому, что в свое время предпочтение отдавалось алгоритмам, предусматривающим хранение в памяти только одного узла, но, как оказалось, такой подход часто является слишком радикальным способом экономии памяти. В алгоритме локального лучевого поиска предусмотрено отслеживание к состояний, а не только одного состояния. Работа этого алгоритма начинается с формирования случайным образом к состояний. На каждом этапе формируются все преемники всех к состояний.

Если какой-либо из этих преемников соответствует целевому состоянию, алгоритм останавливается. В противном случае алгоритм выбирает из общего списка к наилучших преемников и повторяет цикл.

На первый взгляд может показаться, что локальный лучевой поиск с к состояниями представляет собой не что иное, как выполнение к перезапусков случайным образом, но не последовательно, а параллельно. Тем не менее в действительности эти два алгоритма являются полностью разными. При поиске с перезапуском случайным образом каждый процесс поиска осуществляется независимо от других, а в локальном лучевом поиске полезная информация передается по к параллельным потокам поиска. Например, если в одном состоянии вырабатывается несколько хороших преемников, а во всех других к-1 состояниях вырабатываются плохие преемники, то возникает такой эффект, как если бы поток, контролирующий первое состояние, сообщил другим потокам: «Идите все сюда, здесь трава зеленее!» Этот алгоритм способен быстро отказаться от бесплодных поисков и перебросить свои ресурсы туда, где достигнут наибольший прогресс.

В своей простейшей форме локальный лучевой поиск может страдать от отсутствия разнообразия между состояниями, поскольку все эти состояния способны быстро сосредоточиться в небольшом регионе пространства состояний, в результате чего этот поиск начинает ненамного отличаться от дорогостоящей версии поиска с восхождением к вершине. Этот недостаток позволяет устранить вариант, называемый стохастическим лучевым поиском, который аналогичен стохастическому поиску с восхождением к вершине.

При стохастическом лучевом поиске вместо выбора наилучших к преемников из пула преемников-кандидатов происходит выбор к преемников случайным образом, притом что вероятность выбора данного конкретного преемника представляет собой возрастающую функцию значения его оценки. Стохастический лучевой поиск имеет некоторое сходство с процессом естественного отбора, в котором «преемники» (потомки) некоторого «состояния» (организма) образуют следующее поколение в соответствии со «значением их оценки» (в соответствии с их жизненной пригодностью).