与clpfd桥交叉难题

问题描述：

我试图通过clpfd解决'从Zurg'问题'逃脱。 https://web.engr.oregonstate.edu/~erwig/papers/Zurg_JFP04.pdf 玩具从左侧开始向右侧移动。这是我有：与clpfd桥交叉难题

:-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？或者最好是在链接中使用该方法？

仅供参考：我也发现这http://www.metalevel.at/zurg/zurg.html 其中有一个DCG解决方案。其中约束时间= < 60内置，它没有找到最低时间。

答

这里是一个CLP（FD）版本的基础上，code you linked to。

主要区别在于，在此版本中，Limit是一个参数，而不是硬编码值。此外，它还使用CLP（FD）约束条件的灵活性来说明，与低级算术相比，使用约束条件时可以更自由地重新排序目标，并且可以更加明确地声明代码：

:- use_module(library(clpfd)). 

toy_time(buzz, 5). 
toy_time(woody, 10). 
toy_time(rex, 20). 
toy_time(hamm, 25). 

moves(Ms, Limit) :- 
    phrase(moves(state(0,[buzz,woody,rex,hamm],[]), Limit), Ms). 

moves(state(T0,Ls0,Rs0), Limit) --> 
    [left_to_right(Toy1,Toy2)], 
    { T1 #= T0 + max(Time1,Time2), T1 #=< Limit, 
     select(Toy1, Ls0, Ls1), select(Toy2, Ls1, Ls2), 
     Toy1 @< Toy2, 
     toy_time(Toy1, Time1), toy_time(Toy2, Time2) }, 
    moves_(state(T1,Ls2,[Toy1,Toy2|Rs0]), Limit). 

moves_(state(_,[],_), _)   --> []. 
moves_(state(T0,Ls0,Rs0), Limit) --> 
    [right_to_left(Toy)], 
    { T1 #= T0 + Time, T1 #=< Limit, 
     select(Toy, Rs0, Rs1), 
     toy_time(Toy, Time) }, 
    moves(state(T1,[Toy|Ls0],Rs1), Limit).

使用例如，使用迭代加深先找到最快的解决方案：

 
?- length(_, Limit), moves(Ms, Limit). 
Limit = 60, 
Ms = [left_to_right(buzz, woody), right_to_left(buzz), left_to_right(hamm, rex), right_to_left(woody), left_to_right(buzz, woody)] ; 
Limit = 60, 
Ms = [left_to_right(buzz, woody), right_to_left(woody), left_to_right(hamm, rex), right_to_left(buzz), left_to_right(buzz, woody)] ; 
Limit = 61, 
Ms = [left_to_right(buzz, woody), right_to_left(buzz), left_to_right(hamm, rex), right_to_left(woody), left_to_right(buzz, woody)] ; 
etc.

注意，此版本使用的CLP（FD）约束的组合（修剪和算术）和内置Prolog的回溯，而这种一个组合是完全合法的。在某些情况下，全局约束（如CapelliC提到的automaton/8）可以完整地表达问题，但将约束与正常回溯相结合对于许多任务来说也是一个很好的策略。实际上，只是发布CLP（FD）约束通常是不够的：无论如何，您通常还需要一个（回溯）搜索，在CLP（FD）的情况下由labeling/2提供，以获得具体解决方案。因此，如果您成功地仅用CLP（FD）约束来确定性地表达问题，则此迭代加深类似于labeling/2将执行的搜索。

得很漂亮，我们还可以显示：

 
?- Limit #< 60, moves(Ms, Limit). 
false.

编辑：由于对automaton/8的渴求似乎是CLP（FD）的约束有兴趣的用户，这是很好的中几乎难以抑制的，我也为您制定了一个解决方案，为您提供强大的全球约束。如果你觉得这个很有趣，请提供@ CapelliC的回答，因为他最初的想法是使用automaton/8。这个想法是让一个或两个玩具的每个可能的（和明智的）运动对应一个独特的整数，并且这些运动引起自动机的不同状态之间的转换。请注意，闪光灯的一面在状态中也起着重要作用。另外，我们为每个弧配备一个算术表达式以跟踪迄今为止所花费的时间。请尝试?- arc(_, As).以查看此自动机的弧线。

:- use_module(library(clpfd)). 

toy_time(b, 5). 
toy_time(w, 10). 
toy_time(r, 20). 
toy_time(h, 25). 

toys(Toys) :- setof(Toy, T^toy_time(Toy, T), Toys). 

arc0(arc0(S0,M,S)) :- 
    state(S0), 
    state0_movement_state(S0, M, S). 

arcs(V, Arcs) :- 
    findall(Arc0, arc0(Arc0), Arcs0), 
    movements(Ms), 
    maplist(arc0_arc(V, Ms), Arcs0, Arcs). 

arc0_arc(C, Ms, arc0(S0,M,S), arc(S0, MI, S, [C+T])) :- 
    movement_time(M, T), 
    nth0(MI, Ms, M). 

movement_time(left_to_right(Toy), Time) :- toy_time(Toy, Time). 
movement_time(left_to_right(T1,T2), Time) :- 
    Time #= max(Time1,Time2), 
    toy_time(T1, Time1), 
    toy_time(T2, Time2). 
movement_time(right_to_left(Toy), Time) :- toy_time(Toy, Time). 


state0_movement_state(lrf(Ls0,Rs0,left), left_to_right(T), lrf(Ls,Rs,right)) :- 
    select(T, Ls0, Ls), 
    sort([T|Rs0], Rs). 
state0_movement_state(lrf(Ls0,Rs0,left), left_to_right(T1,T2), S) :- 
    state0_movement_state(lrf(Ls0,Rs0,left), left_to_right(T1), lrf(Ls1,Rs1,_)), 
    state0_movement_state(lrf(Ls1,Rs1,left), left_to_right(T2), S), 
    T1 @< T2. 
state0_movement_state(lrf(Ls0,Rs0,right), right_to_left(T), lrf(Ls,Rs,left)) :- 
    select(T, Rs0, Rs), 
    sort([T|Ls0], Ls). 

movements(Moves) :- 
    toys(Toys), 
    findall(Move, movement(Toys, Move), Moves). 

movement(Toys, Move) :- 
    member(T, Toys), 
    ( Move = left_to_right(T) 
    ; Move = right_to_left(T) 
    ). 
movement(Toys0, left_to_right(T1, T2)) :- 
    select(T1, Toys0, Toys1), 
    member(T2, Toys1), 
    T1 @< T2. 

state(lrf(Lefts,Rights,Flash)) :- 
    toys(Toys), 
    phrase(lefts(Toys), Lefts), 
    foldl(select, Lefts, Toys, Rights), 
    (Flash = left ; Flash = right). 

lefts([]) --> []. 
lefts([T|Ts]) --> ([T] | []), lefts(Ts).

而现在，终于，我们终于可以用automaton/8我们这么深的解决方案的愿望，我们真正认为值得持有“CLP（FD）”的旗帜，orgiastically与混合的labeling/2min/1选项：

?- time((arcs(C, Arcs), 
     length(Vs, _), 
     automaton(Vs, _, Vs, [source(lrf([b,h,r,w],[],left)), 
           sink(lrf([],[b,h,r,w],right))], 
        Arcs, [C], [0], [Time]), 
     labeling([min(Time)], Vs))).

产生：

 
857,542 inferences, 0.097 CPU in 0.097 seconds(100% CPU, 8848097 Lips) 
Arcs = [...], 
Time = 60, 
Vs = [10, 1, 11, 7, 10] ; 
etc.

我将这些解决方案转换为易读的状态转换（〜3行代码）。

对于额外的满意度，这比原来的版本与普通的Prolog，为此我们不得不更快：

 
?- time((length(_, Limit), moves(Ms, Limit))). 
1,666,522 inferences, 0.170 CPU in 0.170 seconds (100% CPU, 9812728 Lips)

这个故事的寓意是：如果你直截了当的Prolog的解决方案需要超过十分之一秒来产生解决方案，您最好学习如何使用最复杂和最强大的全局约束之一，以将运行时间缩短几毫秒！ :-)

尽管如此，更严重的一点是，这个例子表明约束传播可以很快得到回报，即使对于比较小的搜索空间也是如此。使用CLP（FD）解决更复杂的搜索问题时，您可以期待更大的相对收益。

注意虽然第二个版本虽然在某种意义上在全局上传播约束，但缺少一个与传播和修剪有关的重要特性：以前，我们能够直接使用该程序来显示没有解决方案的时间少于60分钟，使用直接自然的查询（?- Limit #< 60, moves(Ms, Limit).，失败）。这从第二方案开始只隐含着，因为我们知道，其他条款，更长的清单最多可以增加所花的时间。不幸的是，length/2的孤立电话没有得到备忘录。

另一方面，第二个版本能够证明至少同样令人印象深刻的东西，它比第一个版本更高效，更直接地实现：即使没有构建单个显式解决方案，我们可以使用第二版本来显示，任何溶液（如果有的话）需要至少 5交叉：

?- time((arcs(C, Arcs), 
     length(Vs, L), 
     automaton(Vs, _, Vs, [source(lrf([b,h,r,w],[],left)), 
           sink(lrf([],[b,h,r,w],right))], 
     Arcs, [C], [0], [Time]))).

得到：

 
331,495 inferences, 0.040 CPU in 0.040 seconds (100% CPU, 8195513 Lips) 
..., 
L = 5 
... .

这只能通过约束传播来工作，并且不涉及任何labeling/2！

感谢这个答案做我希望和回答的问题。然而，我很想看看它是如何使用自动机来完成的......所以我现在不会接受... – user27815

我也期待着一些使用automaton/8的实验。有一点很清楚：任何这样的解决方案都必须使用迭代加深（或不同的完整搜索策略）来找到最短或最快的解决方案。这是因为任何对'automaton/8'的调用都需要签名，即被描述的列表被充分实例化。因此，至少该列表的长度必须是已知的，并且对于解决方案的实际搜索将非常类似于我的回答，因此也可能以“长度（列表，_）”开始，并将迭代深化与约束组合。 – mat

谢谢你的回答，因为它和CapelliC的回答帮助我了解了clpfd。 – user27815

答

我认为用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)],

这很好，但我想了解更多的clpfd库。感谢您使用自动机/ 8的提示，这将是非常高兴看到这种思路更多.. – user27815

是的，我试图弄清楚我愚蠢的答案:) – CapelliC

感谢您在这方面的工作 - 它帮助我理解了使用clpfd所需的思想。 – user27815

答

这是而不是使用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.

答

我认为@mat已经为我最初尝试做的事提出了一个很好的答案，但我确实尝试了并使用自动机/ 4以及回溯搜索来添加弧。这是我得到的。但拨打bridge/2时出现错误ERROR: Arguments are not sufficiently instantiated。如果有人对此方法有任何评论，或者知道为什么会出现此错误，或者我正在使用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).

用一个有限自动机的状态转换对它进行建模绝对是一个有趣的想法，所以+1！要找到问题，请尝试使用'？ - gtrace，your_goal.'并在SWI-Prolog的图形跟踪器中浏览您的程序。顺便说一下，在一些条款的末尾，实际上并不需要统一。只要将这些条款直接写在自然的地方。例如：'left_to_right_arc（L0，R0，arc（Before，Cost，After））： - ...'，即可以将这些条款直接移到子句头中，因为在其他地方不需要它们。 – mat

与clpfd桥交叉难题

相关推荐