minizinc - minizinc：在数组中查找元素

Question

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

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)];

score 1 · Accepted Answer

（它总是有助于具有尽可能多的信息的完整模型，例如“m”和“n”的值以及其他已知/固定值。此外，提及错误消息通常会有所帮助。）

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

我猜“结果”真的应该是一个单一的决策变量，而不是你定义的数组。然后你可以写

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]

请注意，两种解决方案都具有相同的最佳目标值（“z”），均为 250。

但是，对要求有另一种解释（来自您的评论）：

对于 a 中的每个元素，从 b 中选择一个对应的值 - 该值必须与 a 中的每个元素的值最接近。

其中“结果”中的每个值仅对应于具有相同索引 (“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]

然后选择“结果”（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：在数组中查找元素

1 回答 1

Related

Reference