minizinc - MiniZinc : Y/N? 中关系的预计算传递闭包

Question

我正在尝试解决 MiniZinc 中的一个练习，其中部分排序关系由二维数组给出:

enum NODE = { A, B, C, D, E };

int : SOURCE = 1;
int : TARGET = 2;

array[int,1..2] of NODE: edge =
   [| A, B        % edge 1, source & edge 1, target
    | A, E        % edge 2, source & edge 2, target
    | B, C        % edge 3, source & edge 3, target
    | B, D |];    % edge 4, source & edge 4, target
  
set of int: EDGES = index_set_1of2(edge);  

output ["EDGES is \(EDGES)\n"];

predicate ancestor_descendant(NODE: a, NODE: d) =
   exists(edge_num in EDGES)(edge[edge_num,SOURCE]=a /\ edge[edge_num,TARGET]=d)
   \/
   exists(edge_num in EDGES)(
      exists(m in NODE)(
         edge[edge_num,SOURCE]=a 
         /\
         edge[edge_num,TARGET]=m
         /\
         ancestor_descendant(m,d)));
   
constraint assert(fix(ancestor_descendant(A,B)),"Failed a->b");
constraint assert(fix(ancestor_descendant(A,E)),"Failed a->e");
constraint assert(fix(ancestor_descendant(B,C)),"Failed b->c");
constraint assert(fix(ancestor_descendant(B,D)),"Failed b->d");
constraint assert(fix(ancestor_descendant(A,C)),"Failed a->c"); % transitive
constraint assert(fix(ancestor_descendant(A,D)),"Failed a->d"); % transitive
constraint assert(not(fix(ancestor_descendant(E,D))),"Failed a->d"); 
constraint assert(not(fix(ancestor_descendant(A,A))),"Failed a->a"); 

上面只是实现了下面的树和一个询问是否节点的谓词 a是节点 d 的祖先.

但是，我觉得回答谓词 ancestor_descendant/2大型 edge 可能会变得昂贵数组，如果在优化期间经常调用谓词，这可能是一个障碍。
我应该期望 MiniZinc 自己内存/缓存(不可变的)谓词结果吗？我应该自己这样做吗？虽然我不知道如何避免设置 (card(NODE)^2)*2 大小的 true 数组和 false (不像在 Prolog 中我只会将谓词的肯定答案保留在数据库中)。

Answer 1

MiniZinc 确实为模型中的任何决策变量表达式实现了记忆化，形式为 Common Sub-expression Elimintation (CSE) .这应该确保任何两个节点的调用结果和存在的结果将只存在一次。
一般来说，已经发现通过内存的 CSE 对于参数表达式是不值得的，因为它在内存中的成本很高，而且在 MiniZinc 中参数表达式通常很快。因此，如果您在展平阶段遇到问题，那么我建议您事先明确计算后代。