Cодержание

1. Постановка задачи

2. Решение

Постановка задачи

Задача о кувшинах воды состоит в следующем:

В кувшин А вмещается 5 литров, а в кувшин B входит 2 литра.

При старте 5-литровый кувшин полный, вы можете лить воду

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

кувшины водой. Это делается до тех пор пока

вы не уверены, что кувшин B содержит ровно 1 литр.

две емкости

 

Решение задачи

Каждое состояние представляется парой

Aamout:Bamount

которая описывает сколько воды содержится в каждом кувшине.

Рассмотрим программу

?-op(100,yfx,':').
определить : как лево-ассоциативный оператор

Главный предикат:

solve(Current_state, Goal_state, Traversed_path, Solution_path).

где Traversed_path - список сделанных пока разливаний

solve(Goal, Goal, Path, Path).

Если текущее состояние - искомое состояние, то выводят путь к 4-ому параметру

solve(Current, Goal, Path, Solution) :- edge(Step, Current, New),

/* Найти 4 способа литья - 'Step' */

not marked(solve(New, Goal, _, _)),

/* Поиск графа требует проверки не искали ли мы этот узлел прежде */

solve(New, Goal, Path:Step, Solution).

/* Используйте рекурсию для поиска в глубину. При откате вернуться к 'pour'. */

edge(pour_a_down_drain, A:B , 0:B).

edge(pour_b_down_drain, A:B , A:0).

edge(pour_a_into_b, A:B, C:D) :-

A>0, B<2, T is A+B, (T>=2, C is T-2, D=2 ; T<2, C=0, D=T) .

edge(pour_b_into_a, A:B, C:D) :-

B0, A<5, T is A+B, (T=5, D is T-5, C=5 ; T<5, C=T, D=0) .

/*Проверяет, искался ли узел ранее. Правило

marked(X) :- asserta((marked(X):- !)), fail.

помечает узел, если это не было сделано ранее, и делает откат. Следующая проверка этого узла пройдет успешно, так как узел был уже помечен. Reset_marked разрешает рекурсии быть выполненной несколько раз.

reset_marked :- retractall(marked(_)),

asserta( (marked(X) :- asserta((marked(X):- !)), fail) ).

jug_problem(X,Y,Z) :- reset_marked, solve(X,Y,start,Z).

?-jug_problem(5:0, A:1, Answer).

Answer = start :

pour_a_down_drain:(O:0)

fill_up_a :(5:0)

pour_a_into_b :(3:2)

pour_a_down_drain :(0:2)

pour_b_into_a :(2:0)

fill_up_b :(2:2)

pour_b_into_a:(4:0)

fill_up_b: (4:2)

pour_b_into_a (5:1)

(c) M.N.Morozov, 1999.