2015-10-22
481
минимум(_x,_y,_x):-_x=<_y,!.
Минимум(_x,_y,_y).
принадлежит(_x,[_x|_]):-!.
принадлежит(_x,[_y|_l]):-!,принадлежит(_x,_l),!.
%1->2
Перелить(_в_первом,_во_втором,_в_третьем, _пройденные):-
Объемы(_объем1,_объем2,_объем3),
_в_первом>0,
_свободно is _объем2-_во_втором,
_свободно>0,
Минимум(_в_первом,_свободно, _количество),
_стало_в_первом is _в_первом-_количество,
_стало_во_втором is _во_втором+_количество,
_новое=сост(_стало_в_первом,_стало_во_втором,_в_третьем),
Not(принадлежит(_новое,_пройденные)),
перелить(_стало_в_первом,_стало_во_втором,_в_третьем,[_новое|_пройденные]).
ЗАДАНИЕ 4.1
Допишите оставшиеся правила допустимого переливания. Проверьте правильность работы программы, задав вопрос?-решение.
Другой вариант решения той же задачи:
Объемы(8,5,3).
Исходное(состояние(8,0,0)).
Цель(состояние(4,4,0)).
решение:-исходное(_s),перелить([_s]).
перелить([_s|_p]):- цель(_s),отобразить_решение([_s|_p]).
перелить([состояние(_1,_2,_3)|_p]):-
Допустимо(_1,_2,_3,_n1,_n2,_n3),g
Not(принадлежит(состояние(_n1,_n2,_n3),
[состояние(_1,_2,_3)|_p])),
перелить([состояние(_n1,_n2,_n3),
состояние(_1,_2,_3)|_p]).
перелито(_1,_2,_f,_n1,_n2):- минимум(_1,_f,_k), _n1 is _1 - _k,_n2 is _2 + _k.
минимум(_x,_y,_x):-_x=<_y,!.
Минимум(_x,_y,_y).
принадлежит(_x,[_x|_]):-!.
принадлежит(_x,[_y|_l]):-!,принадлежит(_x,_l),!.
отобразить_решение([]):-!.
отобразить_решение([_x|_l]):-отобразить_решение(_l),!,write(_x),nl.
%1->2
Допустимо(_1,_2,_3,_n1,_n2,_3):-
_1>0,объемы(_v1,_v2,_v3),
_f is _v2-_2,
_f>0,
Перелито(_1,_2,_f,_n1,_n2).
ЗАДАНИЕ 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]):-
