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

Процесс решения задачи, как правило, включает два этапа: представление задачи и реализацию стратегии поиска.

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

- описание всех или только начальных состояний;

- задание операторов, отображающие одни состояния в другие;

- задание целевого состояния.

Поиск решения задачи в пространстве состояний сводится к определению последовательности операторов, отображающих начальное состояние в целевое.

Таким образом, представление задачи в пространстве состояний определяется совокупностью трех составляющих — тройкой

< S₀, F, G>

где S₀ - множество начальных состояний (может состоять из одного элемента);

F - множество операторов, отображающих одно состояние в другое;

G - множество целевых состояний.

Для описания состояний могут использоваться векторы, матрицы, графы, списки и т.д. Выбор той или иной формы описания состояний определяется из того, чтобы применение оператора, преобразующего одно состояние в другое, оказалось наиболее простым.

При этом операторы отображения (преобразования) наиболее часто представляются в виде набора правил, задающих возможность перехода из одного состояния в другое (преобразование одних состояний в другие).

Так, для рассмотренного ранее примера поиска пути на карте дорог, любое текущее состояние можно описать в виде списка городов, пройденных к текущему моменту (т.е. включенных в маршрут поиска на данный момент).

Тогда начальное состояние будет описываться списком, состоящим только из одного элемента, соответствующего начальному пункту пути:

[A]

Конечным состояниям будут соответствовать любые списки, первые элементы которых соответствуют целевой вершине, т.е. конечному пункту маршрута:

[F ¦ _ ]

Для рассмотренного выше примера конечному состоянию будут соответствовать списки:

[F ¦ [ E,B,A]]

[F ¦ [H,G,A]] и т.д.

Операторы преобразования для этого примера могут быть представлены в виде:

- набора фактов, определяющих дороги между городами;

- набора правил, определяющих возможность перемещения из одного города в другой.

Для рассмотренного примера набор фактов может быть следующим:

Дорога (a, b)