Поиск в пространстве состояний - это процесс, используемый в области информатики , включая искусственный интеллект (AI), в котором рассматриваются последовательные конфигурации или состояния экземпляра с намерением найти целевое состояние с желаемым свойством.
Проблемы часто моделируются как пространство состояний , в набор из состояний , что проблема может быть в. Множество состояний образует график , где два состояния связанно , если есть операция , которая может быть выполнена для преобразования первого состояния во второе.
Поиск в пространстве состояний часто отличается от традиционных методов поиска в информатике, потому что пространство состояний неявно : типичный граф пространства состояний слишком велик для создания и хранения в памяти . Вместо этого узлы создаются по мере их исследования и обычно после этого отбрасываются. Решение для комбинаторного поиска может состоять из самого целевого состояния или из пути от некоторого начального состояния к целевому состоянию.
Представление
При поиске в пространстве состояний пространство состояний формально представлено как кортеж , в котором:
- - множество всех возможных состояний;
- набор возможных действий, не относящихся к конкретному состоянию, но ко всему пространству состояний;
- это функция, устанавливающая, какое действие возможно выполнить в определенном состоянии;
- это функция, которая возвращает состояние, достигнутое при выполнении действия в состоянии
- стоимость выполнения действия в состоянии . Во многих пространствах состояний является константой, но в целом это неверно.
Примеры алгоритмов поиска в пространстве состояний
Неинформированный поиск
Согласно Пулу и Макворту, следующие методы поиска в пространстве состояний неосведомлены , что означает, что они не имеют никакой предварительной информации о местоположении цели. [1]
- Традиционный поиск в глубину
- Поиск в ширину
- Итеративное углубление
- Поиск по самой низкой цене
Эвристический поиск
Некоторые алгоритмы учитывают информацию о местоположении целевого узла в виде эвристической функции . [2] Пул и Макворт приводят следующие примеры в качестве алгоритмов информированного поиска:
- Эвристический поиск в глубину
- Жадный поиск лучшего первого
- Поиск
Смотрите также
Рекомендации
- ^ Пул, Дэвид; Макворт, Алан. «3.5 Стратегии неосведомленного поиска‣ Глава 3 Поиск решений ‣ Искусственный интеллект: основы вычислительных агентов, 2-е издание» . artint.info . Проверено 7 декабря 2017 года .
- ^ Пул, Дэвид; Макворт, Алан. «3.6 Эвристический поиск‣ Глава 3 Поиск решений ‣ Искусственный интеллект: основы вычислительных агентов, 2-е издание» . artint.info . Проверено 7 декабря 2017 года .
- Стюарт Дж. Рассел и Питер Норвиг (1995). Искусственный интеллект: современный подход . Прентис Холл.