Поиск в пространстве состояний - State space search

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

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

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

Представление

При поиске в пространстве состояний пространство состояний формально представлено как кортеж ${\displaystyle S:\langle S,A,Action(s),Result(s,a),Cost(s,a)\rangle }$, в котором:

• ${\displaystyle S}$ это набор всех возможных состояний;
• ${\displaystyle A}$ набор возможных действий, не относящихся к конкретному состоянию, но ко всему пространству состояний;
• ${\displaystyle Action(s)}$ это функция, устанавливающая, какое действие можно выполнить в определенном состоянии;
• ${\displaystyle Result(s,a)}$ это функция, возвращающая состояние, достигнутое при выполнении действия ${\displaystyle a}$ в состоянии ${\displaystyle s}$
• ${\displaystyle Cost(s,a)}$ стоимость выполнения действия ${\displaystyle a}$ в состоянии ${\displaystyle s}$. Во многих пространствах состояний это константа, но в целом это неверно.

Примеры алгоритмов поиска в пространстве состояний

Неинформированный поиск

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

• Традиционный поиск в глубину
• Поиск в ширину
• Итеративное углубление
• Поиск по самой низкой цене

Эвристический поиск

Некоторые алгоритмы учитывают информацию о расположении целевого узла в виде эвристическая функция^[2]. Пул и Макворт приводят следующие примеры в качестве алгоритмов информированного поиска:

• Эвристический поиск в глубину
• Жадный поиск лучшего первого
• Поиск

Смотрите также

• Государственное пространство
• Государственная планировка пространства

Рекомендации

1. Пул, Дэвид; Макворт, Алан. «3.5 Стратегии неинформированного поиска‣ Глава 3 Поиск решений ‣ Искусственный интеллект: основы вычислительных агентов, 2-е издание». artint.info. Получено 7 декабря 2017.
2. Пул, Дэвид; Макворт, Алан. «3.6 Эвристический поиск‣ Глава 3 Поиск решений ‣ Искусственный интеллект: основы вычислительных агентов, 2-е издание». artint.info. Получено 7 декабря 2017.

• Стюарт Дж. Рассел и Питер Норвиг (1995). Искусственный интеллект: современный подход. Прентис Холл.