Поиск в пространстве состояний

Поиск в пространстве состояний (англ. state space search) — группа математических методов, предназначенных для решения задач искусственного интеллекта.

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

Допущения

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

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

Формальное определение задачи

Компоненты задачи

Во многих задачах присутствует дискретное множество состояний, в которых может находиться определённый объект или система, с правилами и условиями перехода из одного состояния в другое (например, в играх). Подобные задачи могут быть формально определены с помощью четырёх компонентов:

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

Альтернативное определение проблемы поиска в пространстве состояний включает

• множество состояний;
• выделенное подмножество состояний, называемых начальными состояниями;
• для каждого состояния — набор действий, доступных агенту в этом состоянии;
• функцию действия (action function), которая для заданного состояния и действия, доступного в этом состоянии, возвращает новое состояние;
• множество целевых состояний, часто определяемое логической функцией goal(s), которая принимает истинное значение, когда s — целевое состояние,
• критерий, определяющий качество приемлемого решения. Сюда могут входить ограничения на количество действий в решении, общую стоимость решения, требование оптимальности решения по числу или общей стоимости действий.

Граф пространства состояний

Большинство алгоритмических формулировок поиска на графах использует понятие явного графа (англ. explicit graph). Граф G = { V , E } {displaystyle G={V,E}} может быть представлен в виде матрицы смежности или списка смежности.

В алгоритмах поиска в пространстве состояний применяется понятие неявного графа (англ. implicit graph). Отличие неявного графа от явно заданного графа состоит в том, что рёбра графа не хранятся в памяти явно, а порождаются «на лету» (англ. on-the-fly) в соответствии с правилами перехода между состояниями. Определение графа пространства состояний включает в себя начальную вершину, множество целевых вершин и процедуру развёртывания вершины.

Решение задачи

Решением задачи называется путь от начального состояния до целевого состояния.

Оптимальным решением называется решение, имеющее наименьшую стоимость среди всех прочих решений.

Оценка алгоритма поиска

Качество алгоритма оценивается с помощью четырёх основных показателей:

• Полнота — свойство алгоритма всегда находить решение, если оно существует;
• Оптимальность — свойство алгоритма всегда находить решение с наименьшей стоимостью;
• Временная сложность — оценка времени работы алгоритма;
• Пространственная сложность — оценка объёма памяти, необходимого алгоритму.

Методы поиска в пространстве состояний

Методы поиска в пространстве состояний делятся на информированные и неинформированные.

Неинформированные методы (методы слепого поиска, методы грубой силы) не используют никакой информации о конкретной задаче, кроме информации о том, как отличить целевое состояние от любого другого.

Алгоритмы этой группы последовательно порождают все возможные состояния, достижимые из исходного состояния до тех пор, пока не будет найдено целевое состояние (решение). Различия между методами неинформированного поиска сводятся к последовательности просмотра состояний.

Информированные методы поиска (эвристические методы) пользуются дополнительной информацией о конкретной задаче. Дополнительная информация (эвристика) позволяет сократить перебор путём исключения заведомо бесперспективных вариантов. Такой подход ускоряет работу алгоритма по сравнению с полным перебором. Недостатком эвристических алгоритмов может быть отсутствие гарантии того, что выбрано правильное или наилучшее из всех возможных решение.