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

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

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

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

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

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

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

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

Альтернативное определение задачи поиска в пространстве состояний^[1] включает:

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

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

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

В алгоритмах поиска в пространстве состояний применяется понятие неявного графа. Отличием неявного графа является то, что рёбра не хранятся явно в памяти, а порождаются «на лету» согласно правилам перехода между состояниями. Определение графа пространства состояний включает начальную вершину, множество целевых вершин и процедуру развёртывания вершины^[2].

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

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

Оптимальным решением будет такое решение, для которого стоимость наименьшая по сравнению с другими возможными решениями.

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

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

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

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

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

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

↑ ¹ ² David Poole and Alan Mackworth. 3.2 State Spaces (англ.). Artificial Intelligence — foundations of computational agents. Дата обращения: 5 декабря 2015. Архивировано 25 ноября 2015 года.
↑ Edelkamp Stefan, Schrödl Stefan. Heuristic search: theory and applications : [англ.]. — Morgan Kaufmann Publishers, 2012. — P. 712. — ISBN 978-0-12-372512-7.

Рассел Стюарт, Норвиг Питер. Искусственный интеллект: современный подход. — 2-е. — Москва : Вильямс, 2006. — P. 1408. — ISBN 5-8459-0887-6.

Толковый словарь по искусственному интеллекту

[ArtInt_48-1] ¹ ² David Poole and Alan Mackworth. 3.2 State Spaces (англ.). Artificial Intelligence — foundations of computational agents. Дата обращения: 5 декабря 2015. Архивировано 25 ноября 2015 года.

[hsta-2] Edelkamp Stefan, Schrödl Stefan. Heuristic search: theory and applications : [англ.]. — Morgan Kaufmann Publishers, 2012. — P. 712. — ISBN 978-0-12-372512-7.

[1]

[2]

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

Допущения

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

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

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

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

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

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

Примечания

Литература

Ссылки

Категории