我认为用CLPFD建模这个难题可以用自动机/ 8来完成。 在Prolog我会写
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现在为incognite。 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).
它推迟到move_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这是一个纯粹的断言和前导会原路返回时，标签将需要......
没有最小化，但是，很容易后，我们得到的解决方案增加了。到目前为止，所有对我来说似乎都是“合乎逻辑的”。但是，当然...
?- 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
...等等等等
对不起，将发布一个解决方案，如果我会得到一些业余时间调试......
编辑有一些错误......这个lmove/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]
with this change to move_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)],
其中all_different/1已换成
...
chain(L0, #<),
...
另一个改进：用于零计数两侧是无用：去除（arbitrarly）一个我们得到了
% 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)],
感谢这个答案做我希望和回答的问题。然而，我很想看看它是如何使用自动机来完成的......所以我现在不会接受... – user27815
我也期待着一些使用automaton/8的实验。有一点很清楚：任何这样的解决方案都必须使用迭代加深（或不同的完整搜索策略）来找到最短或最快的解决方案。这是因为任何对'automaton/8'的调用都需要签名，即被描述的列表被充分实例化。因此，至少该列表的长度必须是已知的，并且对于解决方案的实际搜索将非常类似于我的回答，因此也可能以“长度（列表，_）”开始，并将迭代深化与约束组合。 – mat
谢谢你的回答，因为它和CapelliC的回答帮助我了解了clpfd。 – user27815