Минимальное количество ходов

Question

На этой странице 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. 

Есть стандартный способ найти минимальные шаги решение без указания количества ходов в вышеуказанной программе?

Answer 1

длина/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-Prolog, конструкция имеет вид (*->)/2.
• SICStus Prolog предлагает эту функцию с предикатом if/3. Дополнительная информация доступна here.

Пример запроса:

?- 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 универсально завершены.