Государственное пространство

Эта статья включает в себя список общих ссылок , но он остается в основном непроверенным, поскольку в нем отсутствуют соответствующие встроенные ссылки . Пожалуйста, помогите улучшить эту статью, добавив более точные цитаты. ( Февраль 2012 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

Вакуумный мир, задача о кратчайшем пути с конечным пространством состояний

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

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

Определение [ править ]

В теории динамических систем , дискретная система , определенное с помощью функции ƒ , пространство состояний системы может быть смоделировано в виде ориентированного графа , где каждое возможное состояние динамической системы , представленный в вершине, и есть направленное ребро из от a до b тогда и только тогда, когда ƒ ( a ) =  b . ^[4] Это известно как диаграмма состояний .

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

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

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

Свойства [ править ]

	а	б	c	d	е	ж	грамм	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	c	d	е	ж	грамм	час

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

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

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

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

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

Размер [ править ]

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

Finite [ править ]

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

${\ displaystyle {\ binom {64} {8}} = 4 426 165 368}$

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

Бесконечный [ править ]

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

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

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

Состояния поиска [ править ]

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

Методы [ править ]

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

• Поиск в ширину
• Поиск
• Единый поиск стоимости

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

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

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