MiniZinc:在列表中压缩非零元素对

Question

我有一种情况,我正在建模一个数组S,其中包含来自预定义域的一组值(一个计划)1..t,加上0,这是"不存在/不使用"的特殊值.

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

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

但是,这不容易做到.我尝试过的事情:

• 使用函数形式roots获取S其数据非零的索引集.该解决方案的问题是:
  • 结果是一个集合,因此不能压缩成对或容易地转换为列表,即使我从提供的实例数据中知道它们的数量.
  • root似乎要求所有值都参与数组,而我希望只有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]0则为index.然后,如果这些情况之一是真的,我忽略那些索引,并递归地再次调用该函数,并在递归调用中增加/调整相应的索引.

这可行,但可能不是解决此问题的一种非常好的方法,因为它在FlatZinc模型中引入了许多辅助变量,因此重新表述问题可能仍然更好.