Игра «пятнашки». Структуры и стратегии поиска в пространстве состояний

Пятнашки — это головоломка, которая представляет собой набор из 15 костяшек с числами в квадратной коробке. Костяшки расположены таким образом, что одна ячейка остается пустой:

Рисунок 2.1 — Игра «Пятнашки»

Цель игры — упорядочить костяшки по номерам, перемещая их в коробке.

ОПИСАНИЕ РЕАЛИЗАЦИИ ИГРЫ

ЭВРИСТИКИ. ОПИСАНИЕ ПРИНЦИПОВ РАБОТЫ ПРОГРАММЫ

В данной работе эвристика h (t) считается как сумма расстояний от каждой фишки до ее «конечной» клетки и значения «оценки упорядоченности», умноженного на 4 (потому что поле пятнашек 4*4).

Оценка упорядоченности считается как сумма оценок фишек. Оценка фишки, за которой следует допустимый преемник, равна 0. Например, в нашем случае, если за фишкой 1 следует фишка 2, то оценка фишки 1 равна 0. Для фишки 2 допустимым приемником будет фишка 3, для 3 — 4, для 4 — 5 и т. д.

Таким образом, программа будет находить возможных дальнейших преемников вершины, упорядочивать их по f-значениям, выбирать оптимальное и раскрывать поддерево этого преемника. И так далее, возвращаясь к поиску преемников. До тех пор, пока f-значение другого поддерева не станет меньше, либо пока не будет достигнут предел, либо пока не встретится тупиковый конец, либо пока не найдется искомый лист-узел (конечное решение), которое в нашем примере представляет собой последовательность фишек от 1 до 15.

Каждый узел представляет собой комбинацию фишек на доске, которая отображается в виде упорядоченного списка, на первом месте которого отображается позиция пустой фишки, на втором — фишки 1 и т. д.

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

Манхэттенское расстояние — это сумма расстояний по строкам и столбцам от текущего расположения костяшки до ее правильной позиции:

Рисунок 3.1 — Манхэттенское расстояние На рисунке 3.1 манхэттенское расстояние равно 4.