Государственное пространство (информатика)

В информатике — пространство состояний это дискретное пространство, представляющее набор всех возможных конфигураций «системы». ^[1] Это полезная абстракция для рассуждений о поведении данной системы, которая широко используется в области искусственного интеллекта и теории игр .

Например, игрушечная задача «Мир вакуума» имеет дискретное конечное пространство состояний, в котором существует ограниченный набор конфигураций, в которых могут находиться вакуум и грязь. Система «счетчиков», в которой состояния представляют собой натуральные числа, начинающиеся с 1 и увеличивающиеся через некоторое время ^[2] имеет бесконечное дискретное пространство состояний. Угловое положение незатухающего маятника. ^[3] является непрерывным (и, следовательно, бесконечным) пространством состояний.

Определение

Пространства состояний полезны в информатике как простая модель машин. Формально пространство состояний можно определить как кортеж [ N , A , S , G ], где:

N — набор состояний
A — набор дуг, соединяющих состояния
S — непустое подмножество N . , содержащее начальные состояния
G — непустое подмножество N , содержащее целевые состояния.

Характеристики

	а	б	с	д	и	ж	г	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	с	д	и	ж	г	час

Допустимое состояние в пространстве состояний головоломки восьми ферзей

Пространство состояний имеет некоторые общие свойства:

сложность, где фактор ветвления важен
структуру пространства, см. также теорию графов :
- направленность дуг
- дерево
- корневой граф

Например, в Мире Вакуума коэффициент ветвления равен 4, так как пылесос после перемещения может оказаться в 1 из 4 соседних квадратов (при условии, что он не может оставаться в том же квадрате или двигаться по диагонали). Дуги Вакуумного мира двунаправлены, поскольку в любой квадрат можно попасть из любого соседнего квадрата, а пространство состояний не является деревом, поскольку в цикл можно войти, перемещаясь между любыми четырьмя соседними квадратами.

Пространства состояний могут быть бесконечными или конечными, дискретными или непрерывными.

Размер

Размер пространства состояний для данной системы — это количество возможных конфигураций пространства. ^[3]

Конечный

Если размер пространства состояний конечен, вычисление размера пространства состояний является комбинаторной проблемой. ^[4] Например, в головоломке «Восемь ферзей » пространство состояний можно вычислить, посчитав все возможные способы разместить 8 фигур на шахматной доске 8х8. Это то же самое, что выбрать 8 позиций без замены из набора 64, или

{\binom {64}{8}}=4,426,165,368

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

бесконечный

Все непрерывные пространства состояний могут быть описаны соответствующей непрерывной функцией и, следовательно, бесконечны. ^[3] Дискретные пространства состояний также могут иметь ( счетно ) бесконечный размер, например пространство состояний зависящей от времени системы «счетчиков», ^[2] аналогично системе в теории массового обслуживания, определяющей количество клиентов в линии, которая будет иметь пространство состояний {0, 1, 2, 3, ...}.

Разведка

Исследование пространства состояний — это процесс перебора возможных состояний в поисках целевого состояния. Пространство состояний Pacman , например, содержит целевое состояние всякий раз, когда все пищевые гранулы были съедены, и исследуется путем перемещения Pacman по доске. ^[5]

Поиск состояний

Состояние поиска — это сжатое представление мирового состояния в пространстве состояний и используется для исследования. Состояния поиска используются потому, что пространство состояний часто кодирует больше информации, чем необходимо для исследования этого пространства. Сжатие каждого состояния мира только до информации, необходимой для исследования, повышает эффективность за счет уменьшения количества состояний в поиске. ^[5] Например, состояние в пространстве Pacman включает информацию о направлении, в котором смотрит Pacman (вверх, вниз, влево или вправо). Поскольку изменение направления в Pacman ничего не стоит, состояния поиска для Pacman не будут включать эту информацию и уменьшат размер пространства поиска в 4 раза, по одному для каждого направления, в котором может быть обращен Pacman.

Методы

Стандартные алгоритмы поиска эффективны при исследовании пространств дискретных состояний. Следующие алгоритмы демонстрируют как полноту , так и оптимальность при поиске в пространстве состояний. ^[5]^[6]

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

См. также

Фазовое пространство для информации о фазовом состоянии (например, непрерывном пространстве состояний) в физике и математике.
Вероятностное пространство для информации о пространстве состояний вероятности.
Теория сложности игр , основанная на пространстве состояний результатов игры.
Когнитивная модель#Динамические системы для получения информации о пространстве состояний с моделью динамических систем познания.
Государственное пространственное планирование
Государство (информатика)
Искусственный интеллект
Динамические системы
Глоссарий искусственного интеллекта
Машинное обучение
Математическая оптимизация
Мультиагентная система
Теория игр
Комбинаторика

Ссылки

^ Никамп, Дуэйн. «Определение пространства состояний» . Математические идеи . Проверено 17 ноября 2019 г.
^ Перейти обратно: ^а ^б Паперник, Норман. «Бесконечные состояния и бесконечные переходы между состояниями» . Университет Карнеги-Меллон . Проверено 12 ноября 2019 г. .
^ Перейти обратно: ^а ^б ^с Никамп, Дуэйн. «Идея динамической системы» . Математические идеи . Проверено 12 ноября 2019 г. .
^ Чжан, Вэйсун (1999). Поиск в пространстве состояний: алгоритмы, сложность, расширения и приложения . Спрингер. ISBN 978-0-387-98832-0 .
^ Перейти обратно: ^а ^б ^с Аббель, Питер. «Лекция 2: Неинформированный поиск» . Калифорнийский университет в Беркли CS188: Введение в искусственный интеллект . Проверено 30 октября 2019 г.
^ Аббель, Питер. «Лекция 3: Информированный поиск» . Калифорнийский университет в Беркли CS188: Введение в искусственный интеллект . Проверено 12 ноября 2019 г. .

[MISSD-1] Никамп, Дуэйн. «Определение пространства состояний» . Математические идеи . Проверено 17 ноября 2019 г.

[CMUINF-2] Перейти обратно: ^а ^б Паперник, Норман. «Бесконечные состояния и бесконечные переходы между состояниями» . Университет Карнеги-Меллон . Проверено 12 ноября 2019 г. .

[MIDYNS-3] Перейти обратно: ^а ^б ^с Никамп, Дуэйн. «Идея динамической системы» . Математические идеи . Проверено 12 ноября 2019 г. .

[SACEA-4] Чжан, Вэйсун (1999). Поиск в пространстве состояний: алгоритмы, сложность, расширения и приложения . Спрингер. ISBN 978-0-387-98832-0 .

[BAIL2-5] Перейти обратно: ^а ^б ^с Аббель, Питер. «Лекция 2: Неинформированный поиск» . Калифорнийский университет в Беркли CS188: Введение в искусственный интеллект . Проверено 30 октября 2019 г.

[BAIL3-6] Аббель, Питер. «Лекция 3: Информированный поиск» . Калифорнийский университет в Беркли CS188: Введение в искусственный интеллект . Проверено 12 ноября 2019 г. .

[1]

[2]

[3]

[4]

[5]

[6]