1

我有一些 int 变量的数组（可以超过 10 个）。我正在寻找一种有效的方法来限制这些数组的成对交集计数，即每个数组与任何其他数组的共同元素不能超过 x 个。

伪代码示例：[1,4,4] 和 [2,2,1] 将有一个共同元素 -> 数字 1。[4,4,4] 和 [9,4,4] 有元素 4通常，应忽略重复的 4。

在我当前的实现中，我遍历所有数组对，并为每个 par 检查每个元素是否也在另一个数组中。这当然非常慢，并且没有按照应有的方式消除重复项。

我的代码中有趣的部分如下所示：

constraint matches [0] = exists ( i in index_set(values1) ) ( values1[i]==values2[0] );
constraint matches [1] = exists ( i in index_set(values1) ) ( values1[i]==values2[1] );
constraint matches [2] = exists ( i in index_set(values1) ) ( values1[i]==values2[2] );
constraint matches [3] = exists ( i in index_set(values1) ) ( values1[i]==values2[3] );
constraint matches [4] = exists ( i in index_set(values1) ) ( values1[i]==values2[4] );

constraint sum(matches) <  x;

我曾考虑过使用 minizinc 集，因为它们支持一些集操作，但我无法让它们与变量一起使用。

有任何想法吗？

4

1 回答 1

1

也许像这样，array2set用于将数组转换为集合，然后card计算intersect每对之间的交叉点数。

int: rows = 4; % number of columns
int: cols = 5; % number of rows
array[1..rows,1..cols] of int: a = array2d(1..rows,1..cols, 
               [
               4,6,9,5,6,
               5,3,7,1,3,
               3,8,3,3,1,
               1,1,4,7,2,
               ]);
% convert the arrays to sets
array[1..rows] of set of int: s = [array2set([a[i,j] | j in 1..cols]) | i in 1..rows];

% decision variables
var int: z;

solve satisfy;
constraint
    z = sum(r1,r2 in 1..rows where r1 < r2) (
              card(s[r1] intersect s[r2])
        )
;
output 
[
  "z:\(z)\n"
] ++
[
  show(s[i]) ++ "\n"
  | i in 1..rows 
];

这个模型的输出是

z:7
{4,5,6,9}
{1,3,5,7}
{1,3,8}
{1,2,4,7}
于 2017-05-19T17:56:52.017 回答