Графическое представление пространства состояний

При первом способе представления задачи считается заданным пространство состояний X. Среди состояний выделены начальные состояния (обычно одно) и целевые состояния (может несколько) или, если целевые состояния не заданы явно, указаны целевые условия. Заданными считаются также операции перехода — разрешенные операции — из одного состояния в другое. Пусть А — начальное состояние, Z— одно из конечных состояний. Тогда задача в замкнутой форме (постановка задачи) имеет следующий вид: построить последовательность разрешенных операций, переводящих состояние, А в состояние Z.

Представим пространство состояний в виде ориентированности графа следующим способом. Считаем, что вершины графа соответствуют состояниям из множества X, а ребра графа соответствуют разрешенным операциям из заданного конечного набора {О, О_ъ…, О,}. Ребро графа направляем из вершины Uв вершину V, если среди разрешенных операций перехода имеется такая, которая переводит состояние U в состояние V. Тогда решение исходной задачи сводится к построению на графе, который представляет пространство состояний, пути, ведущего из начальной вершины А в одну из конечных вершин Z. Такой путь называется решающим путем.

Для иллюстрации представления задачи, формализованной первым способом, в виде ориентированного графа рассмотрим игру «Восемь». Она полностью аналогична игре «Пятнадцать». Игра «Восемь» имеет квадратное игровое поле размером 3×3.

и 8 квадратных фишек, пронумерованных числами от одного до восьми.

Фишки размешаются в клетках игрового поля в некотором порядке, при этом одна клетка игрового поля оказывается незаполненной (пустой), например:

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

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

Так что разрешенных операций оказывается всего четыре: движение пустой клетки вправо, влево, вниз и вверх. Обозначим эти операции R, L, Z), U соответственно.

Под состоянием в этой задаче будем понимать матрицу размерности 3×3. Ее элементами могут быть только цифры 0, 1,2, 3, 4, 5, 6, 7, 8. Все элементы различны. Цифра 0 соответствует пустой позиции игрового поля, остальные располагаются в матрице соответственно фишкам с теми же номерами. Так что движению пустой клетки на игровом поле соответствует такое же движение цифры 0 в матрице: она попросту меняется местами с той или иной цифрой. В формализованном виде постановка задачи теперь имеет следующий вид: найти такую последовательность.

операций /?, L, D, (/движения цифры 0, переводящих начальное состояние в конечное состояние.

Фрагмент ориентированного графа, представляющего пространство состояний в данной задаче, приведен на рис. 1. На этом фрагменте графа пространства состояний игры «Восемь» можно увидеть решающий путь, ведущий из начального состояния в конечное состояние. Этот путь состоит из выделенных дуг графа.