0

几个小时前我开始学习 Prolog，我一直在尝试为 Farmer problem 实现求解器。我知道网上有很多例子，但出于学习的目的，我想了解为什么我的代码不起作用，方法是否有效，以及推理此类问题的正确方法是什么.

请参阅下面的代码。我所做的是：

  • 定义指示状态是否有效的规则（从农民的角度来看是安全的:)）
  • 定义指示转换是否有效和安全的规则
  • 定义代表有效行程的规则

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

  1. 如果我通过提供潜在的解决方案来测试行程规则，它的行为是正确的
  2. 如果我质疑行程规则，只有将问题缩短为三个步骤，它才会找到解决方案，例如trip( state(s,s,s,s), State(s,n,s,s), R)

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

所以，我的问题是：

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

在此先感谢您的帮助！

%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]).
4

1 回答 1

0

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

问题是没有任何规则限制 position 的可能值。基本上我忘记将可能的值限制为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 的新手，所以如果有人可以提供任何更正，请这样做！

于 2015-07-12T20:47:19.150 回答