Главная arrow книги arrow Копия Глава 3. Решение проблем посредством поиска arrow Резюме
Резюме

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

•    Прежде чем агент сможет приступить к поиску решений, он должен сформулировать цель, а затем использовать эту цель для формулировки задачи.

•    Задача состоит из четырех частей: начальное состояние, множество действий, функция проверки цели и функция стоимости пути. Среда задачи представлена пространством состояний, а путь через пространство состояний от начального состояния до целевого состояния представляет собой решение.

•    Для решения любой задачи может использоваться единый, общий алгоритм Tree-Search; конкретные варианты этого алгоритма воплощают различные стратегии.

•    Алгоритмы поиска оцениваются на основе полноты, оптимальности, временной и пространственной сложности. Сложность зависит от коэффициент ветвления в пространстве состояний, b, и глубины самого поверхностного решения, d.

•    При поиске в ширину для развертывания выбирается самый поверхностный неразвернутый узел в дереве поиска. Этот поиск является полным, оптимальным при единичных стоимостях этапов и характеризуется временной и пространственной сложностью . В связи с такой пространственной сложностью в большинстве случаев он становится практически не применимым. Поиск по критерию стоимости аналогичен поиску в ширину, но предусматривает развертывание узла с самой низкой стоимостью пути, g(п). Он является полным и оптимальным, если стоимость каждого шага превышает некоторое положительное предельное значение 8.