MiniZinc：压缩列表中的非零元素对

Question

我有这样一种情况，我正在为一个数组 S 建模，其中包含一组来自预定义域 1..t 的值（一个时间表），加上 0，这是一个"not there/not used".

的特殊值

我现在想要 post 对成本函数求和的约束，表示为列表 C 的二维数组 C，包含 S' 的每个非零元素=10=] 同样的顺序，像这样：

constraint x = sum([C[S'[d], S'[d + 1]] | d in 1..max - 1])

然而，这并不容易做到。我尝试过的事情：

利用roots的函数形式得到数据为非零的S的索引集合。该解决方案的问题是：
- 结果是一个集合，因此不能成对压缩或轻易转换为列表，即使我从提供的实例数据中知道它们的编号。
- roots 似乎要求所有值都参与数组，而我只想拥有除 0 之外的完整域。
使用列表理解（例如 [S[i] | i in 1..max where S[i] != 0]）仅 select 值非零的元素：这也不起作用，因为 where 子句列表理解导致列表的类型为 opt，并且元素数量错误（我假设其中一些将是 <>），从本质上将过滤零的问题减少到相同的问题再次使用 <>:s.
将成本函数视为 DFA 并将 0 值视为自循环：这不允许（以我可以识别的任何方式）进行计数；只验证转换，我不关心。

我在这里真正想要的是 filter 或 zip，它们都可以轻松解决我的问题，但我认为我缺少某种标准解决方案。否则，我将不得不重新设计模型。

Answer 1

可以通过使用递归函数来解决您的问题，该函数通过遍历数组的索引来计算成本 S。我在下面的一个小例子中说明了函数 calculate_cost()：

int: t = 10; int: N = 5;

% cost array
array[1..t,1..t] of int: C = array2d(1..t,1..t,[ i | i in 1..t, j in 1..t]);

% variables
array[1..N] of var 0..t: S;
var 0..1000: x;

% constraints
constraint S[1] = 4; % setting some arbitrary values
constraint S[2] = 7;
constraint S[3] = 0;
constraint S[4] = 6;

constraint x =  calculate_cost(1,2);

function var int: calculate_cost(int: index1, int:index2) =
  if index1 > N then 0 
  elseif index2 > N then 0
  else 
    let {
       var bool: value_at_index1_is_zero = S[index1] == 0;
       var bool: value_at_index2_is_zero = S[index2] == 0;
    }
    in 
      if value_at_index1_is_zero 
         then calculate_cost(index1+1, index1+2)
      elseif value_at_index2_is_zero 
         then calculate_cost(index1, index2 + 1) 
      else 
        C[S[index1],S[index2]] + calculate_cost(index2, index2+1)   
      endif
  endif;

solve satisfy;

此示例有 S = [4, 7, 0, 6, 0] 并计算成本 x = C[4,7] + C[7,6] = 4 + 7 = 11。

在函数 calculate_cost() 中，我通过跳过 S 中具有零值的索引递归计算总和。在前几行中，我检查索引是否超出范围，在这种情况下 return 0（递归的基本情况）。然后我创建两个局部变量 true 如果 S[index] 的值对于 index 为零。然后，如果其中一种情况为真，我将忽略这些索引，并再次递归调用该函数，并且 increase/adapt 递归调用中的相应索引。

这可行，但可能不是解决此问题的好方法，因为它在 FlatZinc 模型中引入了很多辅助变量，因此重新表述问题可能仍然更好。

MiniZinc：压缩列表中的非零元素对

MiniZinc: zipping pairs of non-zero elements in a list

arrays

minizinc