Войти
Vacuum World, задача кратчайшего пути с конечным пространством состояний A пространство состояний набор всех возможных конфигураций системы. Это полезная абстракция для рассуждений о поведении данной системы и широко используется в областях искусственного интеллекта и теории игр.
. Например, проблема игрушки Vacuum World имеет дискретное пространство конечных состояний, в котором существует ограниченный набор конфигураций, в которых могут находиться вакуум и грязь. Система «счетчиков», где состояния - это натуральные числа, начинающиеся с 1, и увеличивается с течением времени, имеет бесконечное дискретное пространство состояний. Угловое положение незатухающего маятника представляет собой непрерывное (и, следовательно, бесконечное) пространство состояний.
В теории динамических систем дискретная система, определяемая функцией ƒ, пространство состояний системы может быть моделируется как ориентированный граф, где каждое возможное состояние динамической системы представлено вершиной, и существует направленное ребро от a до b тогда и только тогда, когда ƒ (a) = b. Это известно как диаграмма состояний.
. Для непрерывной динамической системы, определяемой функцией ƒ, пространство состояний системы является изображением of.
Пространства состояний полезны в информатике как простая модель машин. Формально пространство состояний можно определить как кортеж [N, A, S, G], где:
| a | b | c | d | e | f | g | h | ||
| 8 |   | 8 | |||||||
| 7 | 7 | ||||||||
| 6 | 6 | ||||||||
| 5 | 5 | ||||||||
| 4 | 4 | ||||||||
| 3 | 3 | ||||||||
| 2 | 2 | ||||||||
| 1 | 1 | ||||||||
| a | b | c | d | e | f | g | h | ||
Пространство состояний имеет некоторые общие свойства:
Например, Вакуумный мир имеет коэффициент ветвления 4, так как пылесос может оказаться в 1 из 4 соседних квадратов после перемещения (при условии, что он не может оставаться в том же квадрате или перемещаться по диагонали). Дуги Вакуумного Мира двунаправлены, поскольку в любой квадрат можно попасть из любого соседнего квадрата, а пространство состояний не является деревом, так как можно войти в цикл, перемещаясь между любыми 4 соседними квадратами.
Пространства состояний могут быть бесконечными или конечными, дискретными или непрерывными.
Размер пространства состояний для данной системы - это количество возможных конфигураций пространства.
Если размер пространство состояний конечно, вычисление размера пространства состояний - это комбинаторная задача. Например, в головоломке «Восемь ферзей» пространство состояний может быть вычислено путем подсчета всех возможных способов разместить 8 фигур на шахматной доске 8x8. Это то же самое, что выбрать 8 позиций без замены из набора из 64 или
Это значительно больше, чем количество допустимых конфигураций королев, 92. Во многих играх эффективное пространство состояний мало по сравнению со всеми достижимыми / законными состояниями. Это свойство также наблюдается в Chess, где эффективное пространство состояний - это набор позиций, которые могут быть достигнуты разрешенными в игре ходами. Это намного меньше, чем набор позиций, которых можно достичь, размещая комбинации имеющихся шахматных фигур прямо на доске.
Все непрерывные пространства состояний могут быть описаны соответствующей непрерывной функцией и, следовательно, бесконечны. Дискретные пространства состояний могут также иметь (счетно ) бесконечный размер, например пространство состояний зависящей от времени «счетной» системы, аналогичной системе в теории массового обслуживания, определяющей количество клиентов в строке, которая будет иметь пространство состояний {0, 1, 2, 3,...}.
Исследование пространства состояний - это процесс перечисления возможных состояний в поисках состояния цели. Пространство состояний Pacman, например, содержит целевое состояние всякий раз, когда все пищевые гранулы были съедены, и исследуется путем перемещения Pacman по доске.
Состояние поиска - это сжатое представление состояния мира в пространстве состояний, которое используется для исследования. Состояния поиска используются, потому что пространство состояний часто кодирует больше информации, чем необходимо для исследования пространства. Сжатие каждого состояния мира до информации, необходимой для исследования, повышает эффективность за счет уменьшения количества состояний в поиске. Например, состояние в пространстве Pacman включает информацию о направлении, в котором смотрит Pacman (вверх, вниз, влево или вправо). Поскольку изменение направления в Pacman ничего не стоит, состояния поиска для Pacman не будут включать эту информацию и уменьшат размер области поиска в 4 раза, по одному для каждого направления, в котором может находиться Pacman.
Стандартные алгоритмы поиска эффективны при исследовании дискретных пространств состояний. Следующие алгоритмы демонстрируют как полноту, так и оптимальность при поиске в пространстве состояний.
Эти методы не распространяются естественным образом на исследование непрерывные пространства состояний. Исследование непрерывного пространства состояний в поисках заданного целевого состояния эквивалентно оптимизации произвольной непрерывной функции, что не всегда возможно, см. математическая оптимизация.
Портал компьютерного программирования 