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

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

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

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

Представительство [ править ]

При поиске в пространстве состояний пространство состояний формально представляется как кортеж. $S:\langle S,A,Action(s),Result(s,a),Cost(s,a)\rangle$ , в котором:

$S$ – множество всех возможных состояний;
$A$ — совокупность возможных действий, не относящихся к конкретному состоянию, а относительно всего пространства состояний;
$Action(s)$ — функция, определяющая, какое действие возможно выполнить в определенном состоянии;
$Result(s,a)$ это функция, которая возвращает состояние, достигнутое при выполнении действия $a$ в штате $s$
$Cost(s,a)$ это стоимость выполнения действия $a$ в штате $s$ . Во многих пространствах состояний a является константой, но это не всегда так.

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

Неосведомленный поиск [ править ]

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

Информированный поиск [ править ]

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

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

См. также [ править ]

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

Ссылки [ править ]

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

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

Эта искусственному интеллекту статья, посвященная , незавершена . Вы можете помочь Википедии, расширив ее .

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

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

[1]

[2]