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