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

Состояние задачи это конфигурация системы на определённом этапе поиска. Решение задачи возможно только при наличии описания конфигурации т.к. сами конфигурации выясняются только в процессе поиска.

Описание задачи осуществляется посредствам формы. Например в пятнашках это матрица 4х4.

Оператор преобразует одно описание системы в другое. Один из способов представления операторов есть импликация А® В, которая реализует правила продукции.

Таким образом для представления проблемы в пространстве состояний необходимо:

1) Определение пространства состояний по средствам какой-нибудь формы.

2) Множество операторов воздействующих на состояние.

3) Описание целевого состояния.

Среди множества представлений предпочтение отдаётся тому, которое приводит к меньшему пространству состояний. Уменьшение пространства состояний возможно введением переменных, каждая из которых может содержать бесконечное множество состояний. Выражения, которое содержат такие переменные называются схемой описания состояний.

Рассмотрим задачу, которую придумал Амарель. (1966)

В комнате подвешен банан, на высоте, не позволяющей дотянутся обезьяне. Но есть ящик, с которым обезьяна может дотянутся до него. Ящик находится в произвольном месте. Обезьяна находится в произвольной точке. Необходимо определить последовательность действий обезьяны. Вводится переменная величина, которая обобщает положение ящика, обезьяны и банана. И кроме того описывает состояние системы.

Пространство состояний описывается списком из 5 переменных. [W,U,V,P,Z]

Здесь W - положение обезьяны, V - положение ящика, Z - положение банана, U- единица, если обезьяна на ящике, ноль - если на полу. P - единица, если обезьяна достала банан, ноль, когда не достала.

ОПЕРАТОРЫ:

1)Подойти к точке А: [W,O,V,P,Z]->[A,O,V,P,Z]

2)Передвинуть ящик в точку В: [W,O,W,P,Z]->[B,O,B,P,Z]

3)Взобраться на ящик: [B,O,B,P,Z]->[W,1,W,P,Z]

4)Взять банан: [W,1,W,0,W]-> [W,1W,1,W]

Целевой список это любой список, для которого Р=1

Начальное состояние системы так же задаётся списком.

2. Алгоритмы перебора в ширину и глубину в пространстве состояний

Раскрытие вершины – применение оператора к текущему состоянию для получения смежных состояний.

Поиск в ширину в дереве решений.

Основан на ведении двух списков [OPEN] и [CLOSED]:

Поместить все узлы из множества So в список OPEN

1. Если список OPEN пустой, то решений нет.

2. Взять первую вершину из OPEN. Если она принадлежит Sq (множество конечных точек), то решение найдено. Если нет, то перенести его в вершину CLOSED

3. Раскрыть вершину n и все порождённые вершины поместить в список OPEN настроив указатели к вершине n

4. Если порожденная вершина целевая, т.е. принадлежит Sq то выдать решение с помощью указателей, иначе перейти к шагу №2

Этот алгоритм позволяет определить в первую очередь самый короткий путь к целевой вершине.