CLPFD和递推公式

Question

给定一个field，找到从(0, 0)到(3, 3)的“最便宜”路径。只有向上和向右移动是允许的。

field([
   [1, 1, 1, 1],
   [3, 3, 4, 3],
   [3, 3, 1, 3],
   [3, 3, 1, 1] 
]).

nth([A|_], 0, A).
nth([_|T], I, A) :- I #> 0, J #= I - 1, nth(T, J, A).

at(I, J, E) :- field(M), nth(M, I, R), nth(R, J, E).

下面是我的递归解决方案：

:- use_module(library(clpfd)).

price(0, 0, P) :- at(0, 0, P).
price(I, 0, P) :-
  I #=< 3,
  I #> 0,
  I0 #= I - 1,
  price(I0, 0, P0),
  at(I, 0, P1),
  P #= P0 + P1.
price(0, J, P) :-
  J #=< 3,
  J #> 0,
  J0 #= J - 1,
  price(0, J0, P0),
  at(0, J, P1),
  P #= P0 + P1.
price(I, J, P) :-
  I #=< 3,
  J #=< 3,
  I #> 0,
  J #> 0,
  I0 #= I - 1,
  J0 #= J - 1,
  price(I0, J, P0),
  price(I, J0, P1),
  at(I, J, P2),
  P #= min(P0, P1) + P2.

我可以在不同的方向运行：

?- price(3, 3, P).
?- price(I, J, P), I #= 3, J #= 3.
?- price(I, J, P), P #> 10.

1. 能记住中间的步骤吗?严格来说是必要的吗？
2. 只有在I和J被禁足时，才有办法使用记忆吗？
3. CLPFD如何处理谓词price有4条规则的事实？库是否将不同的规则合并成一个大的if？
4. 用price内部的if_编写一个规则更好吗？

Answer 1

Ad 3，当前clpfd/clpz的实现都是一个与实际编译过程(“准备执行”)连接很少的库。因此，您希望没有这样的谓词级优化。这些子句保留下来，并被一个接一个地试用--由于头上的0，可能会有一点点索引。如果您想获得高效的代码，则需要直接组合公共案例。例如，您可能首先在单个规则I in 1..3, J in 1..3中考虑，然后避免所有其他比较。这意味着您需要一些中介辅助谓词。

还请注意I #=< 3, I #> 0和I in 1..3之间的细微差别。前者成功地用于I = 1+0，而后者则产生类型错误。对于0+0 OTOH，您的程序失败了。您可能需要至少一致的行为，因此您也可以在需要通用表达式的地方使用(#)/1。

广告4，if_/3，或者更确切地说，reif可能感兴趣，因为只有0的特例。另外，请注意，通常情况下，您可以使用更复杂的具体化条件，如if_/3第8页中的这里，而不是嵌套treememberd_t/3。

广告1和2在某些系统中对此有一些支持，但它仍然是非常尖端的。特别是，如果您想将它与约束一起使用。

关于您的代码的最后一个评论。你所做的就是一个接一个地获得一个现有的算法，然后你直接对它进行重新编码。考虑最后一个子句，您可以独立地探索两条路径，然后加入它们的结果。您只能这样做，因为您对实际问题了解很多，特别是这两条路径都有一个解决方案。唯一实际发生的不确定情况是坐标的实例化。

Answer 2

正如我在另一个答案中所示，您的递归解决方案的行为是指数级的。对付这种情况的通常方法是增加回忆录。但回忆录递归的结果是直接实现的，通过翻转时间箭头，使用一种动态规划方法，只需立即从给定的字段创建出最优价格的字段；然后可以使用nth或其内建的等价物自由查询该领域的价格。

在下面的文章中，我假设field是一个完整的NxN列表结构。这些列表的元素可能被实例化，也可能不被实例化。

% field(Field), prices(Field,Prices).
prices([],[]).
prices([R1|Rs],[Q1|Qs]):-
   a(R1,0,Q1),  
   bs(Rs,Q1,Qs). 

a([],_,[]).
a([A|AT],P0,[P|PT]):- P #= P0+A, a(AT,P,PT).

bs([],_,[]).
bs([R|Rs],[P0|Q0],[Q|Qs]):- b(R,P0,[P0|Q0],Q), bs(Rs,Q,Qs).

b([],_,[],[]).
b([A|AT],P01,[P0|PT0],[P|PT]):- P #= min(P0,P01)+A, b(AT,P,PT0,PT).

测试：

69 ?- time(( field(_F),maplist(writeln,_F),writeln('----'),
             prices(_F,_X),maplist(writeln,_X) )).
[1,1,1,1,1,1]
[3,3,4,3,2,5]
[3,3,1,3,1,3]
[3,3,1,1,4,3]
[3,3,1,1,4,2]
[3,3,7,1,4,1]
----
[1,  2, 3, 4, 5, 6]
[4,  5, 7, 7, 7,11]
[7,  8, 8,10, 8,11]   % (hand formatted)
[10,11, 9,10,12,14]
[13,14,10,11,15,16]
[16,17,17,12,16,17]
% 289 inferences, 0.000 CPU in 0.027 seconds (0% CPU, Infinite Lips)
true.

这实际上没有回答您的四个问题中的任何一个，但它展示了如何使用动态编程方法编写回忆录递归。

Answer 3

对于问题1的后半部分，当然，在这里回忆录是值得的，您的代码时钟为指数而不是二次型(我认为这可以去掉2 )：

30 ?- time( (I=5, J=5, price(I, J, P)) ).
% 19,120 inferences, 0.000 CPU in 0.007 seconds (0% CPU, Infinite Lips)
I = J, J = 5,
P = 17 ;
% 10,163 inferences, 0.000 CPU in 0.002 seconds (0% CPU, Infinite Lips)
false.

31 ?- time( (I=4, J=4, price(I, J, P)) ).
% 5,120 inferences, 0.000 CPU in 0.003 seconds (0% CPU, Infinite Lips)
I = J, J = 4,
P = 15 ;
% 2,771 inferences, 0.000 CPU in 0.001 seconds (0% CPU, Infinite Lips)
false.

32 ?- time( (I=3, J=3, price(I, J, P)) ).
% 1,366 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
I = J, J = 3,
P = 10 ;
% 769 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
false.

33 ?- _X = [ 19.12/5.12, 5.12/1.37 ], maplist(is,A,_X).
A = [3.734375, 3.7372262773722627].

34 ?- _X = [ 29.3/7.9, 7.9/2.15 ], maplist(is,A,_X).
A = [3.7088607594936707, 3.674418604651163].

我使用您的代码运行了上面的代码，并对其进行了修改，以扩大字段，如下所示：

field([
   [1, 1, 1, 1, 1, 1],
   [3, 3, 4, 3, 2, 5],
   [3, 3, 1, 3, 1, 3],
   [3, 3, 1, 1, 4, 3],
   [3, 3, 1, 1, 4, 2],
   [3, 3, 7, 1, 4, 1]
]).

price(0, 0, P) :- at(0, 0, P).
price(I, 0, P) :-
  I #=< 5,
  .... .
price(0, J, P) :-
  J #=< 5,
  .... .
price(I, J, P) :-
  I #=< 5,
  J #=< 5,
  .... .