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

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

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

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

Определение

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

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

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

• N это набор государств
• А представляет собой набор дуг, соединяющих состояния
• S непустой подмножество из N который содержит начальные состояния
• грамм непустое подмножество 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]

Конечный

Если размер пространства состояний конечен, вычисление размера пространства состояний комбинаторный проблема.^[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]

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

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

Смотрите также

• Портал компьютерного программирования

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

Рекомендации

1. Никамп, Дуэйн. "Определение пространства состояний". Математические идеи. Получено 17 ноября 2019.
2. Паперник, Норман. «Бесконечные состояния и бесконечные переходы состояний». Университет Карнеги Меллон. Получено 12 ноября 2019.
3. Никамп, Дуэйн. «Идея динамической системы». Математические идеи. Получено 12 ноября 2019.
4. Лаубенбахер, Р. Парейгис, Б. (2001). «Отношения эквивалентности на конечных динамических системах» (PDF). Успехи в прикладной математике. 26 (3): 237–251. Дои:10.1006 / aama.2000.0717.
5. Чжан, Вэйсун (1999). Поиск в пространстве состояний: алгоритмы, сложность, расширения и приложения. Springer. ISBN  978-0-387-98832-0.
6. Аббель, Питер. «Лекция 2: Неинформированный поиск». UC Berkeley CS188 Введение в ИИ. Получено 30 октября 2019.
7. Аббель, Питер. «Лекция 3: Информированный поиск». UC Berkeley CS188 Введение в ИИ. Получено 12 ноября 2019.