minizinc：在数组中查找元素

Question

我有两个不同长度的数组（类型：int）。我如何为数组 a 中的每个数字找到数组 b 中最接近的数字（以下不起作用，但可能是因为语法错误）：

int: m;
int: n;
array [1..m] of int: a;
array [1..n] of int: b;
array[1..m] of int: results;
results = [abs(a[i] - b[j])| i in 1..m, j in 1..n];
solve minimize results;
output ["Solution: ", show(results)];

Answer 1

（它总是有助于获得尽可能多的信息的完整模型，例如 "m" 和 "n" 的值以及其他 known/fixed 值。另外，提到错误消息通常有帮助。）

你的模型中有一些未知的东西，所以我不得不猜测一下。

我想 "results" 确实应该是单个决策变量，而不是您定义的数组。然后你可以写

var int: results = sum([abs(a[i] - b[j])| i in 1..m, j in 1..n]);

或

var int: results;
...
constraint results = sum([abs(a[i] - b[j])| i in 1..m, j in 1..n]);

此外，就目前而言，该模型并不是特别有趣，因为它只定义了两个常量数组 "a" 和 "b"（必须用常量值填充）。我假设其中至少有一个是决策变量。决策变量数组必须用 "var int" 声明（或更好：类似 "var 1..size" 的东西，其中 1..size 是数组中可能值的域）。

这是一个工作模型的示例，它可能与您所想的一样，也可能不一样：

int: m = 10;
int: n = 10;
array [1..m] of int: a = [1,2,3,4,5,6,7,8,9,10];
array [1..n] of var 1..10: b;
var int: results = sum([abs(a[i] - b[j])| i in 1..m, j in 1..n]);

solve minimize results;
output [
  "Solution: ", show(results),"\n",
  "a: ", show(a), "\n",
  "b: ", show(b), "\n",
  ];

2015-11-19更新：

我不确定我是否完全理解这些要求，但这里有一个变体。请注意，求和循环根本不使用 "b" 数组，仅使用 "a" 和 "results"。为确保 "results" 中的值是从 "b" 中选择的，"results" 的域只是 "b".

中的值的集合

int: m = 10;
int: n = 10;
array [1..m] of int: a = [1,2,3,4,5,6,7,8,9,10];
array [1..n] of int: b = [5,6,13,14,15,16,17,18,19,20];

% decision variables

% values only from b
array[1..m] of var {b[i] | i in 1..n}: results;
var int: z; % to minimize

constraint
   z >= 0 /\
   z = sum(i in 1..m) (
     sum(j in 1..m) (abs(a[i]-results[j])) 
     % (abs(a[i]-results[i])) % alternative interpretation (see below)
   )
;

solve minimize z;

output [
  "z: ", show(z), "\n",
  "results: ", show(results),"\n",
  "a: ", show(a), "\n",
  "b: ", show(b), "\n",
];

Gecode 有这样的最优解：

 z: 250
 results: [5, 5, 5, 5, 5, 5, 5, 5, 5, 5]
 a: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
 b: [5, 6, 13, 14, 15, 16, 17, 18, 19, 20]

另一个求解器 (Opturion CPX) 的解与您的变体更相似：

 z: 250
 results: [6, 6, 5, 5, 5, 6, 6, 6, 5, 5]
 a: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
 b: [5, 6, 13, 14, 15, 16, 17, 18, 19, 20]

请注意，两种解决方案都具有相同的最佳 objective 值 ("z") 250。

然而，对要求的另一种解释（来自您的评论）：

for each element in a, select a corresponding value from b - this value has to be the closest in value to each element in a.

其中 "results" 中的每个值仅对应于具有相同索引 ("i") 的 "a" 中的值，即

 % ...
 constraint
   z >= 0 /\
   z = sum(i in 1..m) (
      (abs(a[i]-results[i])) 
   )

 ;

那么解决方案是（Gecode）：

z: 19
results: [5, 5, 5, 5, 5, 6, 6, 6, 6, 13]
a: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
b: [5, 6, 13, 14, 15, 16, 17, 18, 19, 20]

然后选择 "results" (13) 中的最后一个值，因为它更接近 10（"a" 中的最后一个元素）。

更新 2 (2015-11-20)

关于第二条评论，关于2D（不是你写的3D版本），这是一个模型。它基于上述模型的第二种解释。将其扩展到更大的维度只是改变维度和添加循环变量的问题。

请注意，这假设 - 可能与您原来的问题相反 - "a" 和 "results" 的维度相同。如果不是，则第二种解释就不是您想要的。另外，我更改了 "a" 和 "b" 中的值以使其更有趣。 :-)

int: m = 3;
int: n = 3;
array [1..m,1..n] of int: a = [|1,2,3|4,5,6|7,8,9|];
array [1..m,1..n] of int: b = [|5,6,13|14,15,16,|7,18,19|];

% decision variables

% values only from b
array[1..m,1..n] of var {b[i,j] | i in 1..m, j in 1..n}: results;
var int: z;

constraint
   z >= 0 /\
   z = sum(i in 1..m, j in 1..n) (
     (abs(a[i,j]-results[i,j]))
  )
;

solve minimize z;

output [  "z: ", show(z), "\n" ]
++["results:"]++
[
  if j = 1 then "\n" else " " endif ++
    show_int(2,results[i,j])
  | i in 1..m, j in 1..n
]
++["\na:"]++
[
   if j = 1 then "\n" else " " endif ++
      show_int(2,a[i,j])
   | i in 1..m, j in 1..n
]
++["\nb:"]++
[
   if j = 1 then "\n" else " " endif ++
     show_int(2,b[i,j])
    | i in 1..m, j in 1..n
];

一个最优解是这样的：

minizinc：在数组中查找元素

minizinc: find element in arrray

minizinc