3

在此页面http://cseweb.ucsd.edu/classes/fa09/cse130/misc/prolog/goat_etc.html 中演示了如何解决流行的狼、山羊和卷心菜难题。

change(e,w).
change(w,e).

move([X,   X,Goat,Cabbage],   wolf,[Y,   Y,Goat,Cabbage]) :- change(X,Y).
move([X,Wolf,   X,Cabbage],   goat,[Y,Wolf,   Y,Cabbage]) :- change(X,Y).
move([X,Wolf,Goat,      X],cabbage,[Y,Wolf,Goat,      Y]) :- change(X,Y).
move([X,Wolf,Goat,Cabbage],nothing,[Y,Wolf,Goat,Cabbage]) :- change(X,Y).

oneEq(X,X,_).
oneEq(X,_,X).

safe([Man,Wolf,Goat,Cabbage]) :-
    oneEq(Man,Goat,   Wolf),
    oneEq(Man,Goat,Cabbage).

solution([e,e,e,e],[]).
solution(Config,[FirstMove|OtherMoves]) :-     
    move(Config,FirstMove,NextConfig),     
    safe(NextConfig),                     
    solution(NextConfig,OtherMoves).

但是为了使用这个程序找到一个实际的解决方案，有必要指定所需的确切移动次数，如下所示：

?- length(X,7), solution([w,w,w,w],X).
X = [goat, nothing, wolf, goat, cabbage, nothing, goat] ;
X = [goat, nothing, wolf, goat, cabbage, nothing, goat] ;
X = [goat, nothing, wolf, goat, cabbage, nothing, goat] ;
X = [goat, nothing, wolf, goat, cabbage, nothing, goat] ;
X = [goat, nothing, wolf, goat, cabbage, nothing, goat] ;
X = [goat, nothing, wolf, goat, cabbage, nothing, goat] ;
X = [goat, nothing, wolf, goat, cabbage, nothing, goat] ;
X = [goat, nothing, wolf, goat, cabbage, nothing, goat] ;
X = [goat, nothing, wolf, goat, cabbage, nothing, goat] ;
X = [goat, nothing, wolf, goat, cabbage, nothing, goat] ;
X = [goat, nothing, wolf, goat, cabbage, nothing, goat] ;
X = [goat, nothing, wolf, goat, cabbage, nothing, goat] ;
X = [goat, nothing, wolf, goat, cabbage, nothing, goat] ;
X = [goat, nothing, wolf, goat, cabbage, nothing, goat] ;
X = [goat, nothing, wolf, goat, cabbage, nothing, goat] ;
X = [goat, nothing, wolf, goat, cabbage, nothing, goat] ;
X = [goat, nothing, cabbage, goat, wolf, nothing, goat] ;
X = [goat, nothing, cabbage, goat, wolf, nothing, goat] ;
X = [goat, nothing, cabbage, goat, wolf, nothing, goat] ;
X = [goat, nothing, cabbage, goat, wolf, nothing, goat] ;
X = [goat, nothing, cabbage, goat, wolf, nothing, goat] ;
X = [goat, nothing, cabbage, goat, wolf, nothing, goat] ;
X = [goat, nothing, cabbage, goat, wolf, nothing, goat] ;
X = [goat, nothing, cabbage, goat, wolf, nothing, goat] ;
X = [goat, nothing, cabbage, goat, wolf, nothing, goat] ;
X = [goat, nothing, cabbage, goat, wolf, nothing, goat] ;
X = [goat, nothing, cabbage, goat, wolf, nothing, goat] ;
X = [goat, nothing, cabbage, goat, wolf, nothing, goat] ;
X = [goat, nothing, cabbage, goat, wolf, nothing, goat] ;
X = [goat, nothing, cabbage, goat, wolf, nothing, goat] ;
X = [goat, nothing, cabbage, goat, wolf, nothing, goat] ;
X = [goat, nothing, cabbage, goat, wolf, nothing, goat] ;
false.

是否有一种标准方法可以找到最小移动解决方案而无需在上述程序中指定移动次数？

4

2 回答 2

2

length/2 具有生成能力，那么只需避免指定值：

?- length(X,_),solution([w,w,w,w],X).
于 2015-07-02T04:52:32.643 回答
2

正如我们所知，具有相同最小步数的解决方案数量有限，我们将密切关注实现通用终止。

minlen_solution(Xs,S) :-
   (   setof(t,solution([w,w,w,w],Xs),_)   % eliminate redundant answers
   *-> Xs = S
   ;   minlen_solution([_|Xs],S)           % no solution? try bigger length
   ).

minlen_solution/2使用(*->)/2，称为“软切割”，承诺最小解决方案长度。

关于便携性的说明：

  • 在 SWI-Prolog 中，该结构的形式为(*->)/2.
  • SICStus Prolog 通过 predicate 提供此功能if/3。更多信息可在此处获得。

示例查询：

?- minlen_solution([],Xs).
  Xs = [goat,nothing,cabbage,goat,   wolf,nothing,goat]
; Xs = [goat,nothing,   wolf,goat,cabbage,nothing,goat].

如果我们想找到所有长度大于或等于 8 的解，我们 可以这样进行：

?- length(Xs,8), solution([w,w,w,w],Xs).   % try length = 8
false.                                     % no solutions!

?- length(Xs,9), solution([w,w,w,w],Xs).   % try length = 9
...

但是，我们仍然必须承诺最小长度。

minlen_solutions/2我们可以直接指定解决方案列表长度的下限，如下所示：

?- length(Xs,8),minlen_solution(Xs,S).
  S = [goat,   goat,   goat,nothing,cabbage,   goat,   wolf,nothing,goat]
; S = [goat,   goat,   goat,nothing,   wolf,   goat,cabbage,nothing,goat] 
; S = [goat,nothing,cabbage,cabbage,cabbage,   goat,   wolf,nothing,goat]
; S = [goat,nothing,cabbage,cabbage,   wolf,   goat,cabbage,nothing,goat]
; S = [goat,nothing,cabbage,   goat,   goat,   goat,   wolf,nothing,goat]
; S = [goat,nothing,cabbage,   goat,   wolf,cabbage,cabbage,nothing,goat]
; S = [goat,nothing,cabbage,   goat,   wolf,nothing,   goat,   goat,goat]
; S = [goat,nothing,cabbage,   goat,   wolf,nothing,nothing,nothing,goat]
; S = [goat,nothing,cabbage,   goat,   wolf,   wolf,   wolf,nothing,goat]
; S = [goat,nothing,nothing,nothing,cabbage,   goat,   wolf,nothing,goat]
; S = [goat,nothing,nothing,nothing,   wolf,   goat,cabbage,nothing,goat]
; S = [goat,nothing,   wolf,   goat,cabbage,cabbage,cabbage,nothing,goat]
; S = [goat,nothing,   wolf,   goat,cabbage,nothing,   goat,   goat,goat]
; S = [goat,nothing,   wolf,   goat,cabbage,nothing,nothing,nothing,goat]
; S = [goat,nothing,   wolf,   goat,cabbage,   wolf,   wolf,nothing,goat]
; S = [goat,nothing,   wolf,   goat,   goat,   goat,cabbage,nothing,goat]
; S = [goat,nothing,   wolf,   wolf,cabbage,   goat,   wolf,nothing,goat]
; S = [goat,nothing,   wolf,   wolf,   wolf,   goat,cabbage,nothing,goat].

为了便于阅读，上面只显示了答案替换S。

请注意，所有使用minlen_solution/2通用终止的查询。

于 2015-07-02T10:07:06.710 回答