1

我正在 Prolog 的状态空间中研究搜索策略，我正在查看以下程序，这是著名的水壶问题，为简单起见，您有 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).

我不清楚的是如何理解这是 beadthfirst 而不是 depth first 例如，查看代码。我正在“人工智能的Prolog编程”（I.Bratko）一书中查看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 是不必要的。

其他详细信息：我尝试使用跟踪执行，但似乎不是明确的 BF，因为从“state(0,0)”开始，唯一可直接到达的状态是“state(4,0)”和“state(0, 3)"，然后在 BFS 中访问这 3 个节点，但是查看跟踪，它们不是，在 state(4,0) 之后它访问 state(4,3)。现在你能确认我走的是正确的路而且这不是 BFS 吗？但是尝试遵循 Bratko 实现我有一个问题：我应该枚举每个节点及其后继节点，我认为这对于水壶问题是不可行的。有什么提示吗？

4

1 回答 1

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).
于 2015-09-12T10:58:07.607 回答