Страница 1 из 2 В настоящей главе представлены методы, которые могут использоваться агентом для выбора действий в таких вариантах среды, которые являются детерминированными, наблюдаемыми, статическими и полностью известными. В таких случаях агент может формировать последовательности из действий, позволяющих ему достичь своих целей; такой процесс называется поиском. • Прежде чем агент сможет приступить к поиску решений, он должен сформулировать цель, а затем использовать эту цель для формулировки задачи. • Задача состоит из четырех частей: начальное состояние, множество действий, функция проверки цели и функция стоимости пути. Среда задачи представлена пространством состояний, а путь через пространство состояний от начального состояния до целевого состояния представляет собой решение. • Для решения любой задачи может использоваться единый, общий алгоритм Tree-Search; конкретные варианты этого алгоритма воплощают различные стратегии. • Алгоритмы поиска оцениваются на основе полноты, оптимальности, временной и пространственной сложности. Сложность зависит от коэффициент ветвления в пространстве состояний, b, и глубины самого поверхностного решения, d. • При поиске в ширину для развертывания выбирается самый поверхностный неразвернутый узел в дереве поиска. Этот поиск является полным, оптимальным при единичных стоимостях этапов и характеризуется временной и пространственной сложностью . В связи с такой пространственной сложностью в большинстве случаев он становится практически не применимым. Поиск по критерию стоимости аналогичен поиску в ширину, но предусматривает развертывание узла с самой низкой стоимостью пути, g(п). Он является полным и оптимальным, если стоимость каждого шага превышает некоторое положительное предельное значение 8.
<< В начало < Предыдущая 1 2 Следующая > В конец >> |