arrays - MiniZinc:压缩列表中的非零元素对

Question

我遇到了一种情况，我正在对数组进行建模 S包含来自预定义域 1..t 的一组值(计划) ，加上0 ，这是“不存在/未使用”的特殊值。

我现在想发布一个约束来对成本函数求和，表示为二维数组 C ，列表 S' ，保存 S 的每个非零元素以相同的顺序，如下所示:

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] )仅选择值非零的元素:这也不起作用，因为 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 中具有零值的索引来递归计算总和。 。在前几行中，我检查索引是否越界，并在这种情况下返回 0(递归的基本情况)。然后我创建两个局部变量 true如果值为 S[index] index 为零。然后，如果其中一种情况为真，我将忽略这些索引，并再次递归调用该函数，并在递归调用中增加/调整相应的索引。

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