Государственный космический поиск

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

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

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

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

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

При поиске в пространстве состояний пространство состояний формально представляется как кортеж , в котором: ${\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). Искусственный интеллект: современный подход . Прентис Холл.