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

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

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

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

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

При поиске в пространстве состояний пространство состояний формально представлено как кортеж ${ displaystyle S: langle S, A, действие (я), результат (s, a), стоимость (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]. Пул и Макворт приводят следующие примеры в качестве алгоритмов информированного поиска:

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

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

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

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

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

Этот искусственный интеллект -связанная статья является заглушка. Вы можете помочь Википедии расширяя это.

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

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

[1]

[2]