ЗАДАНИЕ 4.2

Допишите оставшиеся 5 правил допустимого переливания и проверьте правильность работы программы.

4.2 Применение поиска по заданному критерию для решения головоломки "игра в восемь"

Рассмотрим головоломку «игра в восемь» Головоломка состоит из восьми скользящих фишек, пронумерованных цифрами от 1 до 8 и размещенных в коробке с размерами 3*3, с девятью ячейками. Одна из ячеек всегда пуста, и в эту пустую ячейку может быть передвинута по горизонтали или по вертикали любая соседняя фишка. Это правило можно выразить иначе: пустую ячейку можно перемещать по коробке, меняя ее местами с любой из соседних фишек. Конечной ситуацией является некоторое особое расположение фишек, как показано, например, на рис. 5.1. И нам необходимо найти путь с наименьшим числом перемещений от начальной ситуации до целевой.

рис 5.1

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

Предикаты, касающиеся конкретной проблемы, задаются в виде следующего отношения:

s(Node, Nodel, Cost)

Это отношение является истинным, если в пространстве состояний между узлами Mcde и Nodel имеется дуга со стоимостью Cost. Отношение

goal(Mode)

является истинным, если Node — целевой узел в пространстве состояний. А в отношении

h(Node, H)

переменная Н — эвристическая оценка стоимости пути с минимальной стоимостью от узла Node до целевого узла.

На рис. 5.2 рассматривает головоломка «игра в восемь» и ее представление в виде проблемы поиска пути.

Рис. 5.2

Любой из узлов в пространстве состояний представляет собой некоторую конфигурацию фишек в коробке. В данной программе эта конфигурация представлена в виде списка текущих положений фишек. Каждая позиция обозначается парой координат, X/Y. Порядок элементов в списке является следующим.

1. Текущая позиция пустого квадрата.

2. Текущая позиция фишки 1.

3. Текущая позиция фишки 2.

…

Целевая ситуация (см. рис. 5.1), в которой все фишки находятся на своих исходных клетках, определяется следующим предложением:

goal! [2/2,1/3,2/3,3/3,3/2,3/1,2/1,1/1,1/2]).

Принято считать, что пустая клетка - это "пустая" фишка, которая может передвигаться по горизонтали или г.о вертикали на место, занимаемое любой из ее соседних фишек; это означает, что "пустая" фишка и ее соседняя фишка могут поменяться местами. Рассмотрим текст программы решения задачи «игра в восемь».

s([Empty|Tiles],[Tile|Tiles1],1):-swap(Empty, Tile, Tiles, Tiles1).

% Стоимости всех дуг равны 1

% Поменять местами пустую фишку

% Empty и фишку Tile в списке Tiles

swap(Empty, Tile, [Tile | Ts], [Empty | Ts]):-

mandist(Empty, Tile, 1). % Манхэттенское расстояние равно 1

swap(Empty, Tile, [T1 | Ts], [T1 | Ts1]):-