Minizinc 搜索带约束的二维数组
Minizinc search 2d array with constraints
我怎么能 select 二维数组每一行的最小数字,同时确保同一列最多可以被 select 编辑两次
(在以下情况下,对于第 1 行,选择第 5 列;对于第 2 行,选择第 5 列,而对于第 3 行,第 5 列不能再 selected,因此第 2 列是 select编辑为最小值):
(此外,在java中,经常使用ArrayList来添加和删除元素,但是在Minizinc中如何使用约束来做到这一点)?
int: m = 3;
int: n = 5;
array[1..m,1..n] of int: diffs = [|14,18,24,30,13
|10,12,18,24,7
| 8,7,12,18,6|]
下面是一种方法,它可以最小化所选列的值与每行的 "real" 最小值之间的差值之和。
include "globals.mzn";
int: m = 3;
int: n = 5;
array[1..m,1..n] of int: diffs = [|14,18,24,30,13
|10,12,18,24,7
| 8,7,12,18,6|];
% decision variables
array[1..m] of var 1..n: x; % which row to select
var int: z; % difference between the selected and smallest values
solve minimize z;
% solve satisfy;
% constraint 1: at_most 2 of the same column can be selected
constraint
% at most two rows can have the same column
forall(j in 1..n) (
at_most(2,x,j)
)
;
% constraint 2: calculate the least difference
constraint
% get smallest difference to the smallest value
z = sum(i in 1..m) (
% value of selected column - the smallest value of the row
diffs[i,x[i]]-min([diffs[i,j] | j in 1..n])
)
% /\ % for solve satisfy
% z = 1
;
output [
"z: \(z)\n",
"x: \(x) values:\([diffs[i,x[i]] | i in 1..m])\n"
];
对于这个问题实例,有两个 z=1 的最优解,即该解比 "real" 最优值大 1(如果没有最大 2 列约束)。
z: 1
x: [5, 5, 2] values:[13, 7, 7]
----------
z: 1
x: [1, 5, 5] values:[14, 7, 6]
第一个解决方案意味着我们从第 5 列的前两行中选取值(即 13 和 7 的值),对于第三行,我们从第 2 列中选取值(即 7)。这恰好是示例中提到的解决方案。
还有一种替代方法,其中约束 2 替换为以下约束,即直接对所选值求和(而不是与每行最小值的差):
% constraint 2: calculate the least difference
constraint
z = sum([diffs[i,x[i]] | i in 1..m])
% /\ % for solve satisfy
% z = 27
;
当然,它具有相同的列解决方案。区别仅在于 "z":
的值
z: 27
x: [5, 5, 2] values:[13, 7, 7]
---------
z: 27
x: [1, 5, 5] values:[14, 7, 6]
可以说后面的变体更简洁,但如果 "diffs" 矩阵中的值很大,那么可能应该使用第一个变体,因为求解器更愿意使用较小的值。 (对于具有大值的矩阵,建议使用 "z" 的限制域而不是 "var int",但我今晚有点懒。:-)
我怎么能 select 二维数组每一行的最小数字,同时确保同一列最多可以被 select 编辑两次 (在以下情况下,对于第 1 行,选择第 5 列;对于第 2 行,选择第 5 列,而对于第 3 行,第 5 列不能再 selected,因此第 2 列是 select编辑为最小值): (此外,在java中,经常使用ArrayList来添加和删除元素,但是在Minizinc中如何使用约束来做到这一点)?
int: m = 3;
int: n = 5;
array[1..m,1..n] of int: diffs = [|14,18,24,30,13
|10,12,18,24,7
| 8,7,12,18,6|]
下面是一种方法,它可以最小化所选列的值与每行的 "real" 最小值之间的差值之和。
include "globals.mzn";
int: m = 3;
int: n = 5;
array[1..m,1..n] of int: diffs = [|14,18,24,30,13
|10,12,18,24,7
| 8,7,12,18,6|];
% decision variables
array[1..m] of var 1..n: x; % which row to select
var int: z; % difference between the selected and smallest values
solve minimize z;
% solve satisfy;
% constraint 1: at_most 2 of the same column can be selected
constraint
% at most two rows can have the same column
forall(j in 1..n) (
at_most(2,x,j)
)
;
% constraint 2: calculate the least difference
constraint
% get smallest difference to the smallest value
z = sum(i in 1..m) (
% value of selected column - the smallest value of the row
diffs[i,x[i]]-min([diffs[i,j] | j in 1..n])
)
% /\ % for solve satisfy
% z = 1
;
output [
"z: \(z)\n",
"x: \(x) values:\([diffs[i,x[i]] | i in 1..m])\n"
];
对于这个问题实例,有两个 z=1 的最优解,即该解比 "real" 最优值大 1(如果没有最大 2 列约束)。
z: 1
x: [5, 5, 2] values:[13, 7, 7]
----------
z: 1
x: [1, 5, 5] values:[14, 7, 6]
第一个解决方案意味着我们从第 5 列的前两行中选取值(即 13 和 7 的值),对于第三行,我们从第 2 列中选取值(即 7)。这恰好是示例中提到的解决方案。
还有一种替代方法,其中约束 2 替换为以下约束,即直接对所选值求和(而不是与每行最小值的差):
% constraint 2: calculate the least difference
constraint
z = sum([diffs[i,x[i]] | i in 1..m])
% /\ % for solve satisfy
% z = 27
;
当然,它具有相同的列解决方案。区别仅在于 "z":
的值z: 27
x: [5, 5, 2] values:[13, 7, 7]
---------
z: 27
x: [1, 5, 5] values:[14, 7, 6]
可以说后面的变体更简洁,但如果 "diffs" 矩阵中的值很大,那么可能应该使用第一个变体,因为求解器更愿意使用较小的值。 (对于具有大值的矩阵,建议使用 "z" 的限制域而不是 "var int",但我今晚有点懒。:-)