Поиск государственного пространства

Класс алгоритмов поиска

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

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

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

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

При поиске в пространстве состояний пространство состояний формально представляется в виде кортежа , в котором: ${\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)}$это стоимость выполнения действия в состоянии . Во многих пространствах состояний a является константой, но это не всегда так. ${\displaystyle a}$ ${\displaystyle s}$

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

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

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

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

Осознанный поиск

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

• Информированный/эвристический поиск в глубину
• Жадный поиск по лучшему первому
• Поиск А*

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

• Государственное пространство
• Государственное космическое планирование
• Ветви и границы — метод повышения эффективности поиска в пространстве состояний путем отсечения его подмножеств.

Ссылки

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

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