桥接拼图与clpfd

Question

我试图用clpfd解决“逃离祖格”的问题。JFP04.pdf玩具从左边开始，然后向右转。这就是我所拥有的：

:-use_module(library(clpfd)).

toy(buzz,5).
toy(woody,10).
toy(res,20).
toy(hamm,25).

%two toys cross, the time is the max of the two.
cross([A,B],Time):-
  toy(A,T1),
  toy(B,T2),
  dif(A,B),
  Time#=max(T1,T2).
%one toy crosses
cross(A,T):-
  toy(A,T).

%Two toys travel left to right
solve_L(Left,Right,[l_r(A,B,T)|Moves]):-
  select(A,Left,L1),
  select(B,L1,Left2),
  cross([A,B],T),
  solve_R(Left2,[A,B|Right],Moves).

%One toy has to return with the flash light
solve_R([],_,[]).
solve_R(Left,Right,[r_l(A,empty,T)|Moves]):-
  select(A,Right,Right1),
  cross(A,T),
  solve_L([A|Left],Right1,Moves).

solve(Moves,Time):-
   findall(Toy,toy(Toy,_),Toys),
   solve_L(Toys,_,Moves),
   all_times(Moves,Times),
   sum(Times,#=,Time).

all_times([],[]).
all_times(Moves,[Time|Times]):-
  Moves=[H|Tail],
  H=..[_,_,_,Time],
  all_times(Tail,Times).

在查询?-solve(M,T)或?-solve(Moves,T), labeling([min(T)],[T]).时，我得到了一个解决方案，但没有一个=< 60。(我也看不见.)我怎么用clpfd做这个？还是最好在链接中使用该方法？

FYI:我还找到了这个http://www.metalevel.at/zurg/zurg.html，它有一个DCG解决方案。在其中，约束Time=<60是内置的，它找不到最低的时间。

Answer 1

我认为用CLPFD建模这个谜题可以用自动机/8来完成。

escape_zurg(T,S) :-
    aggregate(min(T,S), (
     solve([5,10,20,25], [], S),
     sum_timing(S, T)), min(T,S)).

solve([A, B], _, [max(A, B)]).
solve(L0, R0, [max(A, B), C|T]) :-
    select(A, L0, L1),
    select(B, L1, L2),
    append([A, B], R0, R1),
    select(C, R1, R2),
    solve([C|L2], R2, T).

sum_timing(S, T) :-
    aggregate(sum(E), member(E, S), T).

产生这个解决方案

?- escape_zurg(T,S).
T = 60,
S = [max(5, 10), 5, max(20, 25), 10, max(10, 5)].

编辑

自动机/8是我力所能及的。让我们从更简单的开始:什么是简单的状态表示？在左边/右边我们有4个插槽，可以是空的:所以

escape_clpfd(T, Sf) :-
    L0 = [_,_,_,_],
    Zs = [0,0,0,0],
    L0 ins 5\/10\/20\/25,
    all_different(L0),
    ...

现在，由于问题如此简单，我们可以“硬编码”状态变化

...
lmove(L0/Zs, 2/2, L1/R1, T1), rmove(L1/R1, 1/3, L2/R2, T2),
lmove(L2/R2, 3/1, L3/R3, T3), rmove(L3/R3, 2/2, L4/R4, T4),
lmove(L4/R4, 4/0, Zs/ _, T5),
...

第一个lmove/4必须将2个元素从左移到右，在它完成之后，我们将在左边有2个零，在右边有2个零。时机(T1)将是max(A,B)，其中A，B现在是隐匿的。rmove/4类似，但T2中的“返回”是唯一的元素(匿名)，它将从右向左移动。我们正在对进化进行编码，在每一边断言0的数量(似乎不难概括)。

让我们完成：

...
T #= T1 + T2 + T3 + T4 + T5,
Sf = [T1,T2,T3,T4,T5].

现在，rmove/4更简单了，所以让我们对它进行编码：

rmove(L/R, Lz/Rz, Lu/Ru, M) :-
    move_one(R, L, Ru, Lu, M),
    count_0s(Ru, Rz),
    count_0s(Lu, Lz).

它延迟将实际工作移动到one/5，然后应用上面硬编码的数值约束：

count_0s(L, Z) :-
    maplist(is_0, L, TF),
    sum(TF, #=, Z).

is_0(V, C) :- V #= 0 #<==> C.

is_0/2重新表示空时隙条件，即使真值可数。值得一试：

?- count_0s([2,1,1],X).
X = 0.

?- count_0s([2,1,C],1).
C = 0.

?- count_0s([2,1,C],2).
false.

在CLP(FD)中编码move_one/5似乎很困难。在这里，Prolog不确定论似乎非常合适..。

move_one(L, R, [Z|Lt], [C|Rt], C) :-
    select(C, L, Lt), is_0(C, 0),
    select(Z, R, Rt), is_0(Z, 1).

选择/3它是一个纯谓词，当标记需要时Prolog会回溯.

没有最小化，但这很容易添加到我们得到的解决方案。到目前为止，这一切在我看来都是“合乎逻辑的”。但是当然..。

?- escape_clpfd(T, S).
false.

所以，这里有龙..。

?- spy(lmove),escape_clpfd(T, S).
% Spy point on escape_zurg:lmove/4
 * Call: (9) escape_zurg:lmove([_G12082{clpfd = ...}, _G12164{clpfd = ...}, _G12246{clpfd = ...}, _G12328{clpfd = ...}]/[0, 0, 0, 0], 2/2, _G12658/_G12659, _G12671) ?  creep
   Call: (10) escape_zurg:move_one([_G12082{clpfd = ...}, _G12164{clpfd = ...}, _G12246{clpfd = ...}, _G12328{clpfd = ...}], [0, 0, 0, 0], _G12673, _G12674, _G12661) ? sskip

..。等

抱歉，如果我有空余时间去调试的话，我会发个解决方案.

编辑有几个错误..。带着这种孤僻/4

lmove(L/R, Lz/Rz, Lu/Ru, max(A, B)) :-
    move_one(L, R, Lt, Rt, A),
    move_one(Lt, Rt, Lu, Ru, B),
    count_0s(Lu, Lz),
    count_0s(Ru, Rz).

至少我们开始获得解决方案(从外部向接口添加变量.)

escape_clpfd(T, Sf, L0) :- ...

?- escape_clpfd(T, S, Vs), label(Vs).
T = 85,
S = [max(5, 10), 10, max(10, 20), 20, max(20, 25)],
Vs = [5, 10, 20, 25] ;
T = 95,
S = [max(5, 10), 10, max(10, 25), 25, max(25, 20)],
Vs = [5, 10, 25, 20] ;
...

编辑

上面的代码工作正常，但速度慢得令人痛苦：

?- time((escape_clpfd(60, Sf, L0),label(L0))).
% 15,326,054 inferences, 5.466 CPU in 5.485 seconds (100% CPU, 2803917 Lips)
Sf = [max(5, 10), 10, max(20, 25), 5, max(5, 10)],
L0 = [5, 10, 20, 25] 

使用此更改移动_one/5：

move_one([L|Ls], [R|Rs], [R|Ls], [L|Rs], L) :-
    L #\= 0,
    R #= 0.
move_one([L|Ls], [R|Rs], [L|Lu], [R|Ru], E) :-
    move_one(Ls, Rs, Lu, Ru, E).

我的表现更好：

?- time((escape_clpfd(60, Sf, L0),label(L0))).
% 423,394 inferences, 0.156 CPU in 0.160 seconds (97% CPU, 2706901 Lips)
Sf = [max(5, 10), 5, max(20, 25), 10, max(5, 10)],
L0 = [5, 10, 20, 25] 

然后，添加到lmove/4

... A #< B, ...

我得到了

% 233,953 inferences, 0.089 CPU in 0.095 seconds (94% CPU, 2621347 Lips)
Sf = [max(5, 10), 5, max(20, 25), 10, max(5, 10)],

总的来说，它仍然比我的纯Prolog解决方案慢得多.

编辑

其他小改进：

?- time((escape_clpfd(60, Sf, L0),maplist(#=,L0,[5,10,20,25]))).
% 56,583 inferences, 0.020 CPU in 0.020 seconds (100% CPU, 2901571 Lips)
Sf = [max(5, 10), 5, max(20, 25), 10, max(5, 10)],

其中所有不同的/1已被替换为

...
chain(L0, #<),
...

另一个改进:计算两边的零是无用的:删除(任意的)一边在移动和移动我们得到。

% 35,513 inferences, 0.014 CPU in 0.014 seconds (100% CPU, 2629154 Lips)
Sf = [max(5, 10), 5, max(20, 25), 10, max(5, 10)],

编辑

为了好玩，这里有相同的纯Prolog解决方案(除了聚合)，它使用一个简单的确定性“提升”变量(提供'提升机')：

:- use_module(carlo(snippets/lifter)).

solve([A, B], _, [max(A, B)]).
solve(L0, R0, [max(A, B), C|T]) :-
    solve([C|select(B, select(A, L0, °), °)],
          select(C, append([A, B], R0, °), °),
          T).

顺便说一句，速度相当快：

?- time(escape_zurg(T,S)).
% 50,285 inferences, 0.065 CPU in 0.065 seconds (100% CPU, 769223 Lips)
T = 60,
S = [max(5, 10), 5, max(20, 25), 10, max(10, 5)].

(绝对时机不太好，因为我正在运行一个为调试而编译的SWI)

Answer 2

我认为@mat已经为我最初想做的事情找到了一个很好的答案，但我确实尝试了使用自动机/4，除了回溯搜索添加弧。这是我所能得到的。但是在调用ERROR: Arguments are not sufficiently instantiated时，我会得到错误的bridge/2。如果有人对这个方法有任何评论，或者知道为什么会出现这个错误，或者如果我使用automaton/4完全错误的话，那么就在这里发布吧！

fd_length(L, N) :-
  N #>= 0,
  fd_length(L, N, 0).

fd_length([], N, N0) :-
  N #= N0.
fd_length([_|L], N, N0) :-
  N1 is N0+1,
  N #>= N1,
fd_length(L, N, N1).

left_to_right_arc(L0,R0,Arc):-
  LenL#=<4,
  fd_length(L0,LenL),
  LenR #=4-LenL,
  fd_length(R0,LenR),
  L0 ins 5\/10\/20\/25,
  R0 ins 5\/10\/20\/25,
  append(L0,R0,All),
  all_different(All),
  Before =[L0,R0],
  select(A,L0,L1),
  select(B,L1,L2),
  append([A,B],R0,R1),
  After=[L2,R1],
  Cost #=max(A,B),
  Arc =arc(Before,Cost,After).

right_to_left_arc(L0,R0,Arc):-
  LenL#=<4,
  fd_length(L0,LenL),
  LenR #=4-LenL,
  fd_length(R0,LenR),
  L0 ins 5\/10\/20\/25,
  R0 ins 5\/10\/20\/25,
  append(L0,R0,All),
  all_different(All),
  Before=[L0,R0],
  select(A,R0,R1),
  append([A],L0,L1),
  After=[L1,R1],
  Cost#=A,
  Arc =arc(After,Cost,Before).

pair_of_arcs(Arcs):-
  left_to_right_arc(_,_,ArcLR),
  right_to_left_arc(_,_,ArcRL),
  Arcs =[ArcLR,ArcRL].

pairs_of_arcs(Pairs):-
  L#>=1,
  fd_length(Pairs,L),
  once(maplist(pair_of_arcs,Pairs)).

bridge(Vs,Arcs):-
  pairs_of_arcs(Arcs),
  flatten(Arcs,FArcs),
  automaton(Vs,[source([[5,10,20,25],[]]),sink([[],[5,10,20,25]])],
      FArcs).

Answer 3

这是，而不是，这是使用CLP(FD)的答案，而只是为了展示成本等于或低于60的解决方案(文本太大，不能放在注释中)。

这个谜题有几个变体。Logtalk在其searching/bridge.lgt示例中包括一个字符集和相应的跨过桥的时间。但是我们可以用补丁来解决这个问题的变化(使用当前的Logtalk git版本)：

?- set_logtalk_flag(complements, allow).
true.

?- {searching(loader)}.
...
% (0 warnings)
true.

?- create_category(patch, [complements(bridge)], [], [initial_state(start, ([5,10,20,25], left, [])), goal_state(end, ([], right, [5,10,20,25]))]).
true.

?- performance::init, bridge::initial_state(Initial), hill_climbing(60)::solve(bridge, Initial, Path, Cost), bridge::print_path(Path), performance::report.
5 10 20 25  lamp _|____________|_ 
20 25  _|____________|_ lamp 5 10 
5 20 25  lamp _|____________|_ 10 
5  _|____________|_ lamp 10 20 25 
5 10  lamp _|____________|_ 20 25 
 _|____________|_ lamp 5 10 20 25 
solution length: 6
state transitions (including previous solutions): 113
ratio solution length / state transitions: 0.05309734513274336
minimum branching degree: 1
average branching degree: 5.304347826086956
maximum branching degree: 10
time: 0.004001000000000032
Initial =  ([5, 10, 20, 25], left, []),
Path = [([5, 10, 20, 25], left, []),  ([20, 25], right, [5, 10]),  ([5, 20, 25], left, [10]),  ([5], right, [10, 20, 25]),  ([5, 10], left, [20, 25]),  ([], right, [5|...])],
Cost = 60 ;
5 10 20 25  lamp _|____________|_ 
20 25  _|____________|_ lamp 5 10 
10 20 25  lamp _|____________|_ 5 
10  _|____________|_ lamp 5 20 25 
5 10  lamp _|____________|_ 20 25 
 _|____________|_ lamp 5 10 20 25 
solution length: 6
state transitions (including previous solutions): 219
ratio solution length / state transitions: 0.0273972602739726
minimum branching degree: 1
average branching degree: 5.764705882352941
maximum branching degree: 10
time: 0.0038759999999999906
Initial =  ([5, 10, 20, 25], left, []),
Path = [([5, 10, 20, 25], left, []),  ([20, 25], right, [5, 10]),  ([10, 20, 25], left, [5]),  ([10], right, [5, 20, 25]),  ([5, 10], left, [20, 25]),  ([], right, [5|...])],
Cost = 60 ;
false.