最低移动次数

Question

在本页面中，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.

是否有一种标准的方法可以在不指定上述程序中的移动次数的情况下找到最小移动解决方案？

Answer 1

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

?- length(X,_),solution([w,w,w,w],X).

Answer 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中，构造具有(*->)/2形式。
• SICStus Prolog提供了谓词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的查询都是通用的。