Представление задач в пространстве состояний

Описание состояний

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

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