0

很抱歉问了这样一个愚蠢的问题，但我被困住了，我不确定是什么导致了问题。它是水桶问题，程序应该找到使用 4 加仑水桶和 3 加仑水桶将一个水桶装满 2 加仑水的路径。

我在 Swipl 中使用了跟踪，发现它在桶填充和桶清空子句（前 4 个谓词）中无限循环问题是我不确定它为什么这样做。

它可能是一些愚蠢的东西，我没有得到，但如果有人能指出我正确的方向或用一堆砖头给我一些感觉，我将非常感激。

很抱歉浪费您的时间。

 :-dynamic bucket/4.

 printIt([]).
 printIt([X,Y|Xs]) :-write("bucket("),write(X),write(Y), write(")"), printIt(Xs).

 go(X,Y) :- bucket(0,0,[0,0],X,Y),printIt([X,Y]).

 /*tests if we have been to this state before*/
 memPairs(X,Y,[X,Y|_]).
 memPairs(X,Y, [_,_|Tail]) :- memPairs(X,Y,Tail).

/*Fill the first bucket*/
bucket(X,Y,T,G1,G2) :- X<4,not(memPairs(4,Y,T)),bucket(4,Y,[4,Y|T],G1,G2).
/*fill the second bucket*/
bucket(X,Y,T,G1,G2) :- Y<3,not(memPairs(X,3,T)),bucket(X,3,[X,3|T],G1,G2).
/*if X is full and Y is not, then empty X*/
/* if X+Y is greater than or equal to 4 then fill Y from X*/
bucket(X,Y,T,G1,G2) :- (X+Y) >= 4, X>0, Z is (Y-(4-X)),not(memPairs(4,Z,T)),bucket(4,Z,[4,Z|T],G1,G2).
/*if X+Y is greater than or equal to 3, then fill X from Y*/
bucket(X,Y,T,G1,G2) :- (X+Y) >=3, Z is (X-(3-Y)), Y>0, not(memPairs(Z,3,T)),bucket(Z,3,[Z,3|T],G1,G2).
/* if it is less, then empty Y */
bucket(X,Y,T,G1,G2) :-(X+Y) =< 3,Z is (X + Y), X>0,not(memPairs(Z,0,[T])),bucket(Z,0,[Z,0|T],G1,G2).
/*if it is less than 4, empty X*/
bucket(X,Y,T,G1,G2) :-(X+Y) =< 4, Y>0, Z is (X + Y),not(memPairs(0,Z,[T])),bucket(0,Z,[0,Z|T],G1,G2).
bucket(4,Y,T,G1,G2) :- not(memPairs(0,Y,T)),bucket(0,Y,[0,Y|T],G1,G2).
/*if Y is full and X is not, then empty Y*/
bucket(X,3,T,G1,G2) :-not(memPairs(X,0,T)),bucket(X,0,[X,0|T],G1,G2).

bucket(X,2,T,G1,G2) :- not(memPairs(X,Y,[T])), bucket(2,X,[X,Y|T],G1,G2).
bucket(2,Y,T,G1,G2) :- not(memPairs(2,Y,[T])),G1,G2.

请注意，桶谓词从 0,0（空桶）开始，并在执行此操作时尝试到达 (2,0)，它会检查先前状态的列表以确保它以前不存在。实际上，memPair 可能有问题（用于检查一对值（在这种情况下的先前状态已在列表中）的自定义谓词。但树证明似乎证明我错了。

4

1 回答 1

2

您还没有对这个问题使用更简单的表示，然后您的算法就应该复杂得多。因此，我一眼就能发现一些问题——但我不确定纠正它们是否会让你的程序运行。

  • 您并不总是将相同的模式传递给 memPairs 和存储桶的递归调用，例如not(memPairs(X,Z,T)),bucket(4,Z,[4,Z|T],G1,G2).
  • not(memPairs(Z,0,[T]))应该not(memPairs(Z,0,T))

另请注意，:- dynamic bucket/4.声明是无用的。

编辑我建议以更像 Prolog 的风格重新设计你的程序：使用一对对：这里是一个工作示例

go(Actions) :- buckets([0-0], Actions).

buckets(Actions, Actions) :- Actions = [2-_|_] ; Actions = [_-2|_].
buckets([Buckets|SoFar], Steps) :-
    action(Buckets, Updated),
    \+ memberchk(Updated, SoFar),
    buckets([Updated,Buckets|SoFar], Steps).

action(B1-B2, C1-C2) :-
    B1 = 0, C1 =  3, C2 = B2 ; % fill Bucket 1
    B2 = 0, C2 =  4, C1 = B1 ; % fill Bucket 2
    B1 > 0, C1 =  0, C2 = B2 ; % empty Bucket 1
    B2 > 0, C2 =  0, C1 = B1 ; % empty Bucket 2
    B1 > 0, B2 < 4, T is min(B1, 4 - B2), C1 is B1 - T, C2 is B2 + T ; % pour Bucket 1 to 2
    B2 > 0, B1 < 3, T is min(B2, 3 - B1), C2 is B2 - T, C1 is B1 + T . % pour Bucket 2 to 1

编辑在析取周围有无用的括号，现在被删除了。

于 2013-04-29T08:38:54.457 回答