2

我是 AI 和 Prolog 新手。我试图在 SWI Prolog 中实现 2 Water Jug 问题。但是，我的解决方案是返回一个global stack overflow.

我知道这个问题过去曾被问过并且有很多答案/解决方案，作为一个完整的新手，我的方法有点天真，因此我想知道我做错了什么。

问题：

有两个水壶，一个容量为 4 加仑，另一个容量为 3 加仑。我在 4 加仑的罐子里需要 2 加仑，另一个应该是空的。

这是代码：

member(X, [X|R]).
member(X, [Y|R]) :- member(X,R).

append([X|Y], Z, [X|W]) :- append(Y,Z,W).
append([], X, X).

/*                                                                                                                                            
production rules for the water jug problem                                                                                                    
*/
maneuver(X, Y, Z):-X=:=2, Y=:=0, write('done').
maneuver(X, Y, Z):-X<4, \+ member(Z, (4,Y)), append(Z, [(4,Y)], A), write('Fill 4 gallon jug\n'), maneuver(4,Y,A).
maneuver(X, Y, Z):-Y<3, \+ member(Z, (X,3)), append(Z, [(X,3)], A), write('Fill 3 gallon jug\b'), maneuver(X,3,A).
maneuver(X, Y, Z):-X>0, \+ member(Z, (0,Y)), append(Z, [(0,Y)], A), write('Empty the 4 gallon jug\n'), maneuver(0,Y,A).
maneuver(X, Y, Z):-Y>0, \+ member(Z, (X,0)), append(Z, [(X,0)], A), write('Empty the 3 gallon jug\n'), maneuver(X,0,A).
maneuver(X, Y, Z):-X+Y>=4, Y>0, \+ member(Z, (4,Y-(4-X))), append(Z, [(4,Y-(4-X))], A), write('Pour from 3 gallon jug to 4 gallon jug\n'), ma$
maneuver(X, Y, Z):-X+Y>=3, X>0, \+ member(Z, (X-(3-Y),3)), append(Z, [(X-(3-Y),3)], A), write('Pour from 4 gallon jug to 3 gallon jug\n'), ma$
maneuver(X, Y, Z):-X+Y=<4, Y>0, \+ member(Z, (X+Y, 0)), append(Z, [(X+Y, 0)], A), write('Pour the water in the 3 gallon jug into the 4 gallon$
maneuver(X, Y, Z):-X+Y=<4, Y>0, \+ member(Z, (0, X+Y)), append(Z, [(0, X+Y)], A), write('Pour the water in the 4 gallon jug into the 3 gallon$

这是输出。

Fill 4 gallon jug
Fill 3 gallon juEmpty the 4 gallon jug
Fill 4 gallon jug
Empty the 4 gallon jug
Fill 4 gallon jug
Empty the 4 gallon jug
Fill 4 gallon jug
Empty the 4 gallon jug
Fill 4 gallon jug
Empty the 4 gallon jug
Fill 4 gallon jug
Empty the 4 gallon jug
Fill 4 gallon jug
Empty the 4 gallon jug
...
4

2 回答 2

1

在 Prolog 中，输出动作“描述”几乎没有意义，因为任何将失败的动作序列都将被撤消，因此尝试任何可用的替代方案。然后我要采取的第一步是“装饰性的”：移开描述，可以从解决方案的两个相邻步骤（列表 Z）中推断出来，并添加一个解决方案参数来机动。

另一个重要的改进：你所有的步骤都重复相同的错误模式：例如

\+ member(Z, (4,Y)), append(Z, [(4,Y)], A)

制作一个“子程序”（并纠正错误，我认为这会导致循环）：

update(State, Step, Updated) :-
   \+ member(Step, State),
   append(State, [Step], Updated).
于 2013-08-04T08:02:09.430 回答
1

您的代码中有 2 个错误需要更正。

  1. 你不能直接写或参考 Y-(4-X) 有点方程，

例如：如果 X=3,Y=5。它会将其视为 5-(4-3)，但不会将其视为 3。因此，您需要使用额外的变量来获取该值。

  1. 您不需要编写附加功能，因为您只添加一个元素，您可以直接将其附加到

Z 为 [(4,Y)|Z]。

修改后的代码将是这样的：

member(X,[X|_]).
member(X,[Y|Z]):-member(X,Z).

move(X,Y,_):-X=:=2,Y=:=0,write('done'),!.
move(X,Y,Z):-X<4,\+member((4,Y),Z),write("fill 4 jug"),nl,move(4,Y,[(4,Y)|Z]).
move(X,Y,Z):-Y<3,\+member((X,3),Z),write("fill 3 jug"),nl,move(X,3,[(X,3)|z]).
move(X,Y,Z):-X>0,\+member((0,Y),Z),write("pour 4 jug"),nl,move(0,Y,[(0,Y)|Z]).
move(X,Y,Z):-Y>0,\+member((X,0),Z),write("pour 3 jug"),nl,move(X,0,[(X,0)|Z]).
move(X,Y,Z):-P is X+Y,P>=4,Y>0,K is 4-X,M is Y-K,\+member((4,M),Z),write("pour from 3jug to 4jug"),nl,move(4,M,[(4,M)|Z]).
move(X,Y,Z):-P is X+Y,P>=3,X>0,K is 3-Y,M is X-K,\+member((M,3),Z),write("pour from 4jug to 3jug"),nl,move(M,3,[(M,3)|Z]).
move(X,Y,Z):-K is X+Y,K<4,Y>0,\+member((K,0),Z),write("pour from 3jug to 4jug"),nl,move(K,0,[(K,0)|Z]).
move(X,Y,Z):-K is X+Y,K<3,X>0,\+member((0,K),Z),write("pour from 4jug to 3jug"),nl,move(0,K,[(0,K)|Z]).

如果输入是：

move(0,0,[(0,0)]).

输出是：

fill 4 jug
fill 3 jug
pour 4 jug
pour 3 jug
fill 4 jug
pour from 4jug to 3jug
pour 3 jug
pour from 4jug to 3jug
fill 4 jug
pour from 4jug to 3jug
pour 3 jug
done
于 2019-11-19T16:59:20.597 回答