农夫的难题——递归规则和累加器打破了我的方法

Question

我几个小时前开始学习 Prolog，但我一直在努力为 Farmer 问题实施求解器。我知道网上有很多例子，但出于学习的目的，我想了解为什么我的代码不起作用，该方法是否有效，以及 正确的方法是什么原因是这样的问题.

见下面的代码。我所做的是：

定义指示状态是否有效的规则（安全、来自农民的观点:) )
定义指示转换是否有效且安全的规则
定义代表有效行程的规则

到目前为止我取得的成就是：

如果我通过提供潜在的解决方案测试 trip 规则，它的行为正确
如果我质疑 trip 规则，它仅找到解决方案 如果我将问题缩短为三个步骤，例如行程(状态(s,s,s,s),状态(s,n,s,s),R)

我想我找到问题了，如果我错了请指正：如果解决方案需要超过3个步骤，最后行规则至少计算两次，并且在第一次递归执行后 PreviousStates 累加器不为空。当 unifying? 探索的答案时， not(member(Next,PreviousStates)) 然后失败，因为Next 状态包含的变量将匹配 PreviousStates 列表头部的内容。

那么，我的问题是：

我的结论正确吗？如果不是，真正的问题是什么？
如果我前一点是对的，我该如何解决呢？也许我错了，但我采取的方法对我来说似乎很合乎逻辑。我哪里失败了？我是否必须完全改变解决问题的方法？

在此先感谢您的帮助！

%Define what are the unsafe states for the Farmer, Goat, Cabbage and Wolf
unsafeState(F,G,C,W) :-
    (C=G, not(C=F));
    (G=W, not(G=F)).
safeState(F,G,C,W) :- not(unsafeState(F,G,C,W)).

%Define what are the valid and safe transitions
isSafeTransition(state(F,F,C,W),state(Fend,Fend,C,W)) :- safeState(F,F,C,W), safeState(Fend,Fend,C,W).
isSafeTransition(state(F,G,F,W),state(Fend,G,Fend,W)) :- safeState(F,G,F,W), safeState(Fend,G,Fend,W).
isSafeTransition(state(F,G,C,F),state(Fend,G,C,Fend)) :- safeState(F,G,C,F), safeState(Fend,G,C,Fend).
isSafeTransition(state(F,G,C,W),state(Fend,G,C,W))    :- safeState(F,G,C,W), safeState(Fend,G,C,W).

% Initial matching rule
trip(A,B,Path):- trip(A,B,Path, []).

% Finishing rule
trip(CurrentState, EndState,Path, _):-
    [CurrentState| [EndState|[]] ] = Path,
    isSafeTransition(CurrentState, EndState).

trip(CurrentState,EndState,Path, PreviousStates):-
    [CurrentState|[Next|Tail]] = Path,
    not(member(Next,PreviousStates)),
    isSafeTransition(CurrentState,Next),
    trip(Next,EndState, [Next|Tail], [CurrentState|PreviousStates]).

Answer 1

我自己发现了问题，我发布了解释以防对某人有帮助。

问题是没有任何规则限制职位的可能值。基本上我 忘记将可能的值限制为 n 或 s...

求解查询时，变量的潜在值是无穷大的。这就是为什么包含变量的状态存储在累加器中并匹配下一个状态。

为了解决这个问题，我添加了两个事实，它们定义了位置的有效值，并修改了规则控制状态是否有效以包含这些值。

在下面找到固定程序：

% Define the valid sides for any participant    
side(n).
side(s).

% Define what are the valid states for the Farmer, Goat, Cabbage and Wolf
unsafeState(F,G,C,W) :-
    (C=G, not(C=F));
    (G=W, not(G=F)).
validState(F,G,C,W) :-
    side(F),side(G),side(C),side(W),
    not(unsafeState(F,G,C,W)).

%Define what are the valid and safe transitions
isSafeTransition(state(F,F,C,W),state(Fend,Fend,C,W)) :- 
    validState(F,F,C,W), validState(Fend,Fend,C,W).
isSafeTransition(state(F,G,F,W),state(Fend,G,Fend,W)) :- 
    validState(F,G,F,W), validState(Fend,G,Fend,W).
isSafeTransition(state(F,G,C,F),state(Fend,G,C,Fend)) :- 
    validState(F,G,C,F), validState(Fend,G,C,Fend).
isSafeTransition(state(F,G,C,W),state(Fend,G,C,W))    :- 
    validState(F,G,C,W), validState(Fend,G,C,W).

% Initial matching rule
trip(A,B,Path):- trip(A,B,Path, []).

% Finishing rule
trip(CurrentState, EndState,Path, _):-
    [CurrentState| [EndState|[]] ] = Path,
    isSafeTransition(CurrentState, EndState).

trip(CurrentState,EndState,Path, PreviousStates):-
    [CurrentState|[Next|Tail]] = Path,
    not(member(CurrentState,PreviousStates)),
    isSafeTransition(CurrentState,Next),
    trip(Next,EndState, [Next|Tail], [CurrentState|PreviousStates]).

我在 Prolog 中仍然是个新手，所以如果有人可以提供任何更正，请做！

农夫的难题——递归规则和累加器打破了我的方法

The Farmer's puzzle - recursive rules and accumulators break my approach

prolog

river-crossing-puzzle