带约束的Minizinc搜索2d数组
带约束的Minizinc搜索2d数组
提问于 2016-01-30 20:15:26
如何从2d数组的每一行中选择最小的数目，同时确保最多可以选择同一列两次(在以下情况下，对于第1行，选择第5列；对于第2行，第5列被选中，而对于第3行，则不能再选择第5列，因此选择第2列作为最小值)：(此外，在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|]回答 1
Stack Overflow用户
回答已采纳
发布于 2016-01-30 21:55:19
下面是一种将所选列的值与每一行的“实际”最小值之间的差值之和最小化的方法。
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有两个最优解，即解比“实”最优值大1(如果没有max 2列约束的话)。
z: 1
x: [5, 5, 2] values:[13, 7, 7]
----------
z: 1
x: [1, 5, 5] values:[14, 7, 6]第一个解决方案意味着我们从第5列中为第2行选择值(即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"，但我今晚有点懒。:-)
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/35106613
复制相关文章
相似问题
腾讯云开发者
