Пролог - поиск воды в кувшине

Question

Я изучаю стратегии поиска в пространстве состояний в Прологе, я смотрю на следующую программу, это знаменитая проблема с водяными кувшинами, для простоты у вас есть 2 кувшина (4 и 3 литра), которые вы можете заполнить, опорожнить и переносите воду в другой кувшин, пока первый не опустеет или второй не наполнится. Цель состоит в том, чтобы иметь 2 литра (кувшины не имеют никакого измерения). Эта реализация должна быть шире в первую очередь.

go:-solution(S).

solution(ActionList):-init(I),nl,write(init),tab(4),write(I),
                      nl,solution(I,[],ActionList),!.

solution(State,VisitedStates,[]) :- final(State).

solution(State,VisitedStates, [Action|Rest]) :- applicable(Action,State) ,
                                        apply(Action,State,NewState),
                    \+visited(NewState,VisitedStates), write(Action), tab(4) , write(NewState), nl,
                    solution(NewState,[State|VisitedStates],Rest).

visited(State,[VisitedState|OtherVisitedStates]) :-   sameState(State,VisitedState).

visited(State,[VisitedState|OtherVisitedStates]) :- visited(State,OtherVisitedStates).
sameState(S,S).


init(state(0,0)).
final(state(2,X)).
applicable(emptyA,state(Qa,Qb)) :- Qa > 0.
applicable(emptyB,state(Qa,Qb)) :- Qb > 0.
applicable(fillA,state(Qa,Qb)) :- Qa < 4.
applicable(fillB,state(Qa,Qb)) :- Qb < 3.
applicable(emptyAinB,state(Qa,Qb)) :- Qa > 0 , Qtot is Qa + Qb , Qtot =< 3.
applicable(emptyBinA,state(Qa,Qb)) :- Qb > 0, Qtot is Qa + Qb , Qtot =< 4.
applicable(fillAwithB,state(Qa,Qb)) :- Qa < 4, Qtrasf is 4 - Qa , Qtrasf =< Qb.
applicable(fillBwithA,state(Qa,Qb)) :- Qb < 3, Qtrasf is 3 - Qb , Qtrasf=<Qa.

apply(emptyA,state(Qa,Qb),state(0,Qb)).
apply(emptyB,state(Qa,Qb),state(Qa,0)).
apply(fillA,state(Qa,Qb),state(4,Qb)).
apply(fillB,state(Qa,Qb),state(Qa,3)).
apply(emptyAinB,state(Qa,Qb),state(0,Qtot)) :- Qtot is Qa+Qb.
apply(emptyBinA,state(Qa,Qb),state(Qtot,0)) :- Qtot is Qa+Qb.
apply(fillAwithB,state(Qa,Qb),state(4,NewQb)) :- NewQb is Qb-(4-Qa).
apply(fillAwithB,state(Qa,Qb),state(NewQa,3)) :- NewQa is Qa-(3-Qb).

Что мне не понятно, так это как понять, что лучше, а не глубину, например, глядя на код. Я смотрю на реализацию BF в книге "Прологическое программирование для искусственного интеллекта" (И. Братко), и она мне кажется другой, поскольку она сохраняет все альтернативные кандидаты (узел или состояния в моем случае) с их путем (как должно быть в теории). Другая проблема: BF сначала должен найти кратчайший путь, но это ответ моей программы:

init    state(0,0)
fillA    state(4,0)
fillB    state(4,3)
emptyA    state(0,3)
emptyBinA    state(3,0)
fillB    state(3,3)
fillAwithB    state(4,2)
emptyA    state(0,2)
emptyBinA    state(2,0)

очевидно, это не самый короткий путь, операции 2 и 4 излишни.

Дополнительные детали: я попытался выполнить с помощью trace и, похоже, не является BF окончательно, поскольку, начиная с "state(0,0)", доступны только состояния, доступные непосредственно: "state(4,0)" и "state(0,3)", затем в BFS эти 3 узла должны быть посещены, но, глядя на трассу, они не становятся, после состояния (4,0) он посещает состояние (4,3). Теперь вы можете подтвердить, что я на верном пути, а это не BFS? но пытаясь следовать реализации Bratko, у меня есть проблема: я должен перечислить каждый узел с его преемником, я думаю, что это неосуществимо с проблемой кувшина с водой. Есть намеки?

Answer 1

Нашел решение, основанное на реализации BFS Bratko и представлении состояния, предоставленном logtalk. Это мой последний код, я подтвердил, что это BFS с трассировкой.

go:-start(Start),solve(Start,Solution),reverse(Solution,L),print(L).

solve( Start, Solution)  :-
  breadthfirst( [ [Start] ], Solution).

% breadthfirst( [ Path1, Path2, ...], Solution):
%   Solution is an extension to a goal of one of paths

breadthfirst( [ [Node | Path] | _], [Node | Path])  :-
  goal( Node).

breadthfirst( [Path | Paths], Solution)  :-
  extend( Path, NewPaths),
  append( Paths, NewPaths, Paths1),
  breadthfirst( Paths1, Solution).

extend( [Node | Path], NewPaths)  :-
 bagof( [NewNode, Node | Path],
     ( next_state( Node, NewNode),  \+member( NewNode, [Node | Path] ) ),
     NewPaths),
  !.

extend( Path, [] ).              % bagof failed: Node has no successor


% states are represented by the compound term (4-gallon jug, 3-gallon jug);
% in the initial state both jugs are empty:

start((0, 0)).

% the goal state is to measure 2 gallons of water:
goal((2, _)).
goal((_, 2)).

% fill up the 4-gallon jug if it is not already filled:
next_state((X, Y), (4, Y)) :- X < 4.

% fill up the 3-gallon jug if it is not already filled:
next_state((X, Y), (X, 3)) :- Y < 3.

% if there is water in the 3-gallon jug Y > 0) and there is room in the 4-gallon jug (X < 4) THEN use it to fill up
% the 4-gallon jug until it is full (4-gallon jug = 4 in the new state) and leave the rest in the 3-gallon jug:
next_state((X, Y), (4, Z)) :- Y > 0, X < 4,
                  Aux is X + Y, Aux >= 4,
                  Z is Y - (4 - X).

% if there is water in the 4-gallon jug (X > 0) and there is room in the 3-gallon jug (Y < 3) THEN use it to fill up
% the 3-gallon jug until it is full (3-gallon jug = 3 in the new state) and leave the rest in the 4-gallon jug:
next_state((X, Y), (Z, 3)) :- X > 0, Y < 3,
                  Aux is X + Y, Aux >= 3,
                  Z is X - (3 - Y).

% there is something in the 3-gallon jug (Y > 0) and together with the amount in the 4-gallon jug it fits in the
% 4-gallon jug (Aux is X + Y, Aux =< 4) THEN fill it all (Y is 0 in the new state) into the 4-gallon jug (Z is Y + X):
next_state((X, Y),(Z, 0)) :- Y > 0,
                 Aux is X + Y, Aux =< 4,
                 Z is Y + X.

% there is something in the 4-gallon jug (X > 0) and together with the amount in the 3-gallon jug it fits in the
% 3-gallon jug (Aux is X + Y, Aux =< 3) THEN fill it all (X is 0 in the new state) into the 3-gallon jug (Z is Y + X):
next_state((X, Y),(0, Z)) :- X > 0,
                 Aux is X + Y, Aux =< 3,
                 Z is Y + X.

% empty the 4-gallon jug IF it is not already empty (X > 0):
next_state((X, Y), (0, Y)) :- X > 0.

% empty the 3-gallon jug IF it is not already empty (Y > 0):
next_state((X, Y), (X, 0)) :- Y > 0.

print([]).
print([H|T]):-write(H),nl,print(T).

Только один последний маленький вопрос, я хотел бы сохранить действие, выполненное для достижения каждого состояния, но я не знаю, как это сделать. Например, если состояние (0,0), следующее состояние может быть (0,3) с действием "fillB", как я могу сохранить это действие? Я не хотел бы изменять реализацию BFS и просто помещать это в представление состояния, например (0,3,fillB), не должно работать, потому что одному действию соответствует более одного состояния, поэтому проверка членства новое состояние на пути не удастся.

РЕДАКТИРОВАТЬ

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

action((_,Y),(4,Y),fill1).
action((X,_),(X,3),fill2).
action((_,Y),(4,Z),put(2,1)):-Y\=Z.
action((X,_),(Z,3),put(1,2)):-X\=Z.
action((X,_),(Z,0),put(2,1)):-X\=Z.
action((_,Y),(0,Z),put(2,1)):-Y\=Z.
action((_,Y),(0,Y),empty1).
action((X,_),(X,0),empty2).

И переопределил предикат печати:

print([],_).
print([H|T],0):-write(start),tab(4),write(H),nl,print(T,H).
print([H|T],Prev):-action(Prev,H,X),write(X),tab(4),write(H),nl,print(T,H).