В информатике пространство состояний — это дискретное пространство, представляющее набор всех возможных конфигураций «системы». [1] Это полезная абстракция для рассуждений о поведении данной системы, которая широко используется в областях искусственного интеллекта и теории игр .
Например, игрушечная задача Vacuum World имеет дискретное конечное пространство состояний, в котором существует ограниченный набор конфигураций, в которых могут находиться вакуум и грязь. Система «счетчика», где состояния — это натуральные числа, начинающиеся с 1 и увеличивающиеся со временем [2], имеет бесконечное дискретное пространство состояний. Угловое положение незатухающего маятника [3] — это непрерывное (и, следовательно, бесконечное) пространство состояний.
Пространства состояний полезны в информатике как простая модель машин. Формально пространство состояний можно определить как кортеж [ N , A , S , G ], где:
Пространство состояний имеет некоторые общие свойства:
Например, у Vacuum World коэффициент ветвления равен 4, так как пылесос может оказаться в 1 из 4 смежных квадратов после перемещения (предполагая, что он не может оставаться в том же квадрате или двигаться по диагонали). Дуги Vacuum World двунаправлены, так как из любого смежного квадрата можно попасть в любой квадрат, а пространство состояний не является деревом, так как можно войти в цикл, перемещаясь между любыми 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]
Эти методы не распространяются естественным образом на исследование непрерывных пространств состояний. Исследование непрерывного пространства состояний в поисках заданного целевого состояния эквивалентно оптимизации произвольной непрерывной функции , что не всегда возможно, см. математическую оптимизацию .
