Главная arrow книги arrow Копия Глава 4. arrow Локальный поиск в оперативном режиме
Локальный поиск в оперативном режиме

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

Вместо перезапуска случайным образом для исследования среды может быть предусмотрено использование случайного блуждания (random walk). В методе случайного блуждания просто выбирается случайным образом одно из действий, доступных из текущего состояния; предпочтение отдается действиям, которые еще не были опробованы. Легко доказать, что метод случайного блуждания позволяет агенту в конечном итоге найти цель или выполнить свою задачу исследования, при условии, что пространство является конечным15. С другой стороны, этот процесс может оказаться очень продолжительным. На рис. 4.14 показана среда, в которой для поиска цели с помощью метода случайного блуждания может потребоваться количество этапов, измеряемое экспоненциальной зависимостью, поскольку на каждом этапе вероятность шага назад вдвое превышает вероятность шага вперед. Безусловно, что этот пример является надуманным, но существует много реальных пространств состояний, топология которых способствует возникновению "ловушек" такого рода при случайном блуждании.

Рис. 4.14. Среда, в которой применение метода случайного блуждания для поиска цели требует выполнения такого количества этапов, которое определяется экспоненциальной зависимостью