与clpfd的桥梁横穿难题

Question

我试图用clpfd解决'逃离Zurg'的问题.https://web.engr.oregonstate.edu/~erwig/papers/Zurg_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做这个？或者最好在链接中使用该方法？

仅供参考:我也找到了这个http://www.metalevel.at/zurg/zurg.html 哪个有DCG解决方案.在其中内置约束Time = <60,它没有找到最低时间.

Answer 1

这是一个CLP(FD)版本,基于您链接的代码.

主要区别在于,在此版本中,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回溯的组合,这种组合是完全合法的.在某些情况下,全局约束(如automaton/8CapelliC提到的)可以完整地表达问题,但是对于许多任务而言,将约束与正常回溯相结合也是一个好策略.

事实上,仅仅发布CLP(FD)约束通常是不够的:您通常还需要(labeling/2在CLP(FD)的情况下提供的)(回溯)搜索来获得具体的解决方案.因此,labeling/2如果您单独使用CLP(FD)约束成功地确定性地表达问题,则此迭代加深类似于否则将执行的搜索.

很好,我们还可以显示:

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

编辑:由于automaton/8CLP(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)"旗帜,或者与以下min/1选项混合labeling/2:

?- 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!