Prolog - 广度优先搜索水壶 [英] Prolog - breadth first search for water jug
问题描述
我正在 Prolog 中研究状态空间中的搜索策略，我正在查看以下程序，是著名的水壶问题，为了简单起见，您有 2 个水壶(4 升和 3 升)，您可以填写, 倒空并将水转移到另一个水罐中，直到第一个水罐已空或第二个水罐已满.目标是有 2 升(水壶没有任何量度).这种实现应该是广度优先.
I'm studying search strategies in the state space in Prolog, I'm looking at the following program, is the famous water jugs problem, to keep it simple you have 2 jugs (4 and 3 litres), you can fill, empty and transfer the water into the other jug until the first is empty or the second is full. The goal is to have 2 litres (the jugs don't have any measuring). This implementation should be a breadth first.
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).
我不清楚的是，例如，查看代码时如何理解是珠峰优先而不是深度优先.我正在研究人工智能的 Prolog 编程"(I.Bratko)一书中的 BF 实现，这对我来说似乎不同，因为它保留了所有备选候选(在我的情况下为节点或状态)及其路径(如理论上应该是).另一个问题:BF 应该先找到最短路径，但这是我程序的响应:
What is not clear to me is how to understand that is beadthfirst and not depth first for example, looking at the code. I'm looking at the implementation of BF in the book "Prolog programming for Artificial Intelligence" (I.Bratko) and it seems different to me as it keep all the alternatives candidates (node or states in my case) with their path (as should be in theory). Another issue: BF should find the shortest path first, but this the response of my program:
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 是不必要的.
clearly it's not the shortest path, operations 2 and 4 are unnecessarily.
附加细节:我尝试使用跟踪执行，但似乎不是明确的 BF，因为从state(0,0)"开始，唯一可直接到达的状态是state(4,0)"和state(0,3)"，然后在 BFS 中，这 3 个节点将被访问，但是从跟踪来看，它们不是，在 state(4,0) 之后它访问 state(4,3).现在你能确认我走对了，这不是 BFS 吗?但是在尝试遵循 Bratko 实现时，我遇到了一个问题:我应该枚举每个节点及其后继节点，我认为这对于水壶问题是不可行的.有什么提示吗?
Additional details: I tried to execute with trace, and seems not to be a BF definitively, as starting from "state(0,0)" the only states directly reachable are "state(4,0)" and "state(0,3)", then in a BFS these 3 nodes as to be visited, but looking at the trace, they're not, after state(4,0) it visit state(4,3). Now can you confirm I am on the right way and this is not a BFS? but trying to follow the Bratko implementation I have a problem: I should enumerate every node with its successor, I think it's not feasible with the water jug problem. Any hints?
推荐答案
找到了一个解决方案，基于 BFS 的 Bratko 实现和 logtalk.这是我的最终代码，我验证了这是一个带有跟踪的 BFS.
Found a solution, based on the Bratko implementation of BFS and the representation of the state provided by logtalk. This is my final code, I verified that is a BFS with trace.
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)不应该工作，因为多个状态对应于一个动作，因此路径中新状态的成员资格检查将失败.
Only one last little question, I'd like to store the action performed to reach each state, but I don't know how to do it. For example if the state is (0,0), the next state could be (0,3) with action "fillB", how could I store this action? I'd like to don't modify the BFS implementation and simply putting this into the state representation, for example (0,3,fillB) shouldn't work because more than one state correspond to an action, so the membership check of the new state in the path will fail.
编辑
可以从解决方案的两个相邻状态中检索执行的操作，所以我只是在代码中添加了以下几行:
Action performed can be retrieved from two adjacent states of the solution so I just added this lines to the code:
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).
并重新定义了打印谓词:
And redefined the print predicate:
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).
这篇关于Prolog - 广度优先搜索水壶的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
