2

这是我对水壶问题的解决方案

:- use_module(library(clpfd)).

initial(state(8, 0, 0)).
final(state(4, 4, 0)).

constraint(A0, A1, B0, B1, C0, C1, V) :-
  A0 #< A1,
  ( B0 #> 0, T #= min(V - A0, B0), A1 #= A0 + T, B1 #= B0 - T, C1 #= C0
  ; C0 #> 0, T #= min(V - A0, C0), A1 #= A0 + T, C1 #= C0 - T, B1 #= B0
  ).

transition(state(A0, B0, C0), state(A1, B1, C1)) :-
  ( constraint(A0, A1, B0, B1, C0, C1, 8)
  ; constraint(B0, B1, A0, A1, C0, C1, 5)
  ; constraint(C0, C1, A0, A1, B0, B1, 3)
  ).

solve(A, A, _, [A]).
solve(A, B, P, [A|Q]) :-
  transition(A, A1),
  \+ member(A1, P),
  solve(A1, B, [A|P], Q).

path(P) :-
  initial(S0),
  final(S),
  solve(S0, S, [], P).

有没有办法在P不遍历所有选项的情况下找到最小长度？

4

1 回答 1

1

这是一个更多地利用 clpfd 功能的解决方案：首先陈述问题，然后尝试解决它（使用labeling/2或类似方法）。鉴于我们不知道（最短）路径的长度，这将产生越来越大的问题，直到找到解决方案。在我的代码中，我不会阻止两次访问相同的状态（但这可以以与@DavidTonhofer 编写的 MiniZinc 模型相同的方式添加，或者作为一些后处理）。但是，为了确保有限的搜索空间，如果路径的长度大于(5+1)*(3+1)，我添加了代码来停止问题生成，因为这是不同状态数量的上限（假设我们没有添加或除去 3 个水壶外的水）。

:- use_module(library(clpfd)).

initial(state(8, 0, 0)).
final(state(4, 4, 0)).


constraint(A0,A1,B0,B1,C0,C1,R,Max):-
  T#=min(Max-B0,A0),
  R in 0..1,
  R#==>T#>0,
  R#==>A1#=A0-T,
  R#==>B1#=B0+T,
  R#==>C1#=C0.
  

transition(state(A0, B0, C0), state(A1, B1, C1)) :-
  A0+B0+C0#=A1+B1+C1,
  A0 in 0..8,
  B0 in 0..5,
  C0 in 0..3,
  A1 in 0..8,
  B1 in 0..5,
  C1 in 0..3,
  constraint(A0,A1,B0,B1,C0,C1,RAB,5),
  constraint(B0,B1,A0,A1,C0,C1,RBA,8),
  constraint(A0,A1,C0,C1,B0,B1,RAC,3),
  constraint(C0,C1,A0,A1,B0,B1,RCA,8),
  constraint(C0,C1,B0,B1,A0,A1,RCB,5),
  constraint(B0,B1,C0,C1,A0,A1,RBC,3),
  RAB+RBA+RAC+RCA+RCB+RBC#=1.


solve(A, A, Xs, [A]):-
  labeling([],Xs).
solve(A, B, Xs, [A|Q]) :-
  length(Xs, L),
  L < 24*3,
  transition(A, A1),
  A=state(X1,X2,X3),
  solve(A1, B, [X1,X2,X3|Xs], Q).

path(P) :-
  initial(S0),
  final(S),
  solve(S0, S, [], P).

我试图使代码相对接近问题中的代码。主要区别在于所有序言级别的析取transition/2和constraint/7已被删除并被具体化所取代。特别是，如果采用该特定转换，我添加了等于的R参数。然后我声明其中一个转换必须发生。constraint/81transition/2

我必须补充一点，这个公式并不是特别有效，如果发现使用不同的 clpfd 公式或根本不使用 clpfd 可以更有效地解决问题，我不会感到惊讶。

于 2021-07-20T09:07:14.290 回答