在水壶问题中寻找最短路径

Question

这是我解决水壶问题的方法

:- 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？

Answer 1

这是一个更多地利用 clpfd 功能的解决方案：首先陈述问题，然后尝试解决它（使用 labeling/2 或类似的方法）。鉴于我们不知道（最短）路径的长度，这将产生越来越大的问题，直到找到解决方案。在我的代码中，我不会阻止两次访问相同的状态（但这可以通过与@DavidTonhofer 编写的 MiniZinc 模型相同的方式添加，或者作为一些 post-processing）。但是，为了确保有限搜索 space，我添加了代码以在路径长度超过 (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/8，如果进行了特定转换，它等于 1。然后我在 transition/2 中声明必须发生其中一个转换。

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

在水壶问题中寻找最短路径

Finding shortest path in water jugs problem

prolog

clpfd

water-jug-problem