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

Поиск в пространстве состояний это процесс, используемый в области Информатика, включая искусственный интеллект (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]. Пул и Макворт приводят следующие примеры в качестве алгоритмов информированного поиска:

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

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

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

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

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

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