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