Главная arrow книги arrow Копия Глава 4. arrow Агенты, выполняющие поиск в оперативном режиме
Агенты, выполняющие поиск в оперативном режиме

Листинг 4.5. Агент, выполняющий поиск в оперативном режиме, который проводит исследование с использованием поиска в глубину. Этот агент может применяться только в пространствах двунаправленного поиска

Рекомендуем читателю провести трассировку хода выполнения процедуры Online-DFS-Agent применительно к лабиринту, показанному на рис. 4.12. Можно довольно легко убедиться в том, что в наихудшем случае агент в конечном итоге пройдет по каждой связи в данном пространстве состояний точно два раза. При решении задачи обследования такая организация работы является оптимальной; а при решении задачи поиска целей, с другой стороны, коэффициент конкурентоспособности может оказаться сколь угодно неэффективным, если агент будет отправляться в длительные экскурсии, притом что целевое состояние находится непосредственно рядом с начальным состоянием. Такая проблема решается с использованием варианта метода итеративного углубления для работы в оперативном режиме; в среде, представляющей собой однородное дерево, коэффициент конкурентоспособности подобного агента равен небольшой константе.

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