最少移动次数
Minimum number of moves
在此页中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.
是否有一种标准方法可以找到最小步数解决方案,而无需在上述程序中指定步数?
length/2有生成能力,那么就避免指定值:
?- length(X,_),solution([w,w,w,w],X).
众所周知,具有相同最小步数的解决方案数量有限,我们将密切关注实现通用终止。
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
,称为 "soft cut",以实现最小解长度。
关于便携性的说明:
示例查询:
?- 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
的查询均已终止。
在此页中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.
是否有一种标准方法可以找到最小步数解决方案,而无需在上述程序中指定步数?
length/2有生成能力,那么就避免指定值:
?- length(X,_),solution([w,w,w,w],X).
众所周知,具有相同最小步数的解决方案数量有限,我们将密切关注实现通用终止。
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
,称为 "soft cut",以实现最小解长度。
关于便携性的说明:
示例查询:
?- 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
的查询均已终止。