Ago*_*ino 6 c++ mapping matrix minizinc gecode
我有一个问题,可以归结为找到一种将三角矩阵映射到跳过对角线的向量的方法。
基本上我需要使用 Gecode 库来翻译这个 C++ 代码
// implied constraints
for (int k=0, i=0; i<n-1; i++)
for (int j=i+1; j<n; j++, k++)
rel(*this, d[k], IRT_GQ, (j-i)*(j-i+1)/2);
Run Code Online (Sandbox Code Playgroud)
进入这个 MiniZinc(功能)代码
constraint
forall ( i in 1..m-1 , j in i+1..m )
( (differences[?]) >= (floor(int2float(( j-i )*( j-i+1 )) / int2float(2)) ));
Run Code Online (Sandbox Code Playgroud)
我需要找出differences[?]
.
MiniZinc 是一种函数/数学语言,没有合适的 for 循环。所以我必须映射那些接触上三角矩阵的所有单元格的索引 i 和 j,跳过其对角线,将这些单元格从 0 编号到任意值。
如果这是一个普通的三角矩阵(它不是),解决这样会做
index = x + (y+1)*y/2
Run Code Online (Sandbox Code Playgroud)
我正在处理的矩阵是一个n*n
方阵,索引从 0 到 n-1,但最好为n*m
矩阵提供更通用的解决方案。
这是完整的 Minizinc 代码
% modified version of the file found at https://github.com/MiniZinc/minizinc-benchmarks/blob/master/golomb/golomb.mzn
include "alldifferent.mzn";
int: m;
int: n = m*m;
array[1..m] of var 0..n: mark;
array[int] of var 0..n: differences = [mark[j] - mark[i] | i in 1..m, j in i+1..m];
constraint mark[1] = 0;
constraint forall ( i in 1..m-1 ) ( mark[i] < mark[i+1] );
% this version of the constraint works
constraint forall ( i in 1..m-1 , j in i+1..m )
( (mark[j] - mark[i]) >= (floor(int2float(( j-i )*( j-i+1 )) / int2float(2))) );
%this version does not
%constraint forall ( i in 1..m-1, j in i+1..m )
% ( (differences[(i-1) + ((j-2)*(j-1)) div 2]) >= (floor(int2float(( j-i )*( j-i+1 )) / int2float(2))) );
constraint alldifferent(differences);
constraint differences[1] < differences[(m*(m-1)) div 2];
solve :: int_search(mark, input_order, indomain, complete) minimize mark[m];
output ["golomb ", show(mark), "\n"];
Run Code Online (Sandbox Code Playgroud)
谢谢。
当心。您从链接中发现的公式,index = x + (y+1)*y/2
,包括对角元素,是一个下三角矩阵,这是我收集的不是你想要的。您正在寻找的确切公式实际上是index = x + ((y-1)y)/2
(参见:https : //math.stackexchange.com/questions/646117/how-to-find-a-function-mapping-matrix-indices)。
再次注意,我给你的这个公式假设你的指数:x,y, are zero-based。您的 MiniZinc 代码使用的索引 i,j从 1 (1 <= i <= m), 1 <= j <= m)) 开始。对于从 1 开始的索引,公式为T(i,j) = i + ((j-2)(j-1))/2
。所以你的代码应该是这样的:
constraint
forall ( i in 1..m-1 , j in i+1..m )
((distances[(i + ((j-2)*(j-1)) div 2]) >= ...
Run Code Online (Sandbox Code Playgroud)
请注意,它(j-2)(j-1)
始终是 2 的倍数,因此我们可以使用除数为 2 的整数除法(无需担心与浮点数之间的转换)。
以上假设您使用的是m*m
方阵。
要推广到M*N
矩形矩阵,一个公式可以是:
其中 0 <= i < M, 0<= j < N [如果您再次需要索引从 1 开始,请将 i 替换为 i-1,将 j 替换为上述公式中的 j-1]。这涉及上三角矩阵的所有单元格以及当 N > M 时出现的正方形“边上的额外块”。也就是说,它涉及所有单元格 (i,j),使得 i < j 为 0 <= i < M, 0 <= j < N。
完整代码:
% original: https://github.com/MiniZinc/minizinc-benchmarks/blob/master/golomb/golomb.mzn
include "alldifferent.mzn";
int: m;
int: n = m*m;
array[1..m] of var 0..n: mark;
array[1..(m*(m-1)) div 2] of var 0..n: differences;
constraint mark[1] = 0;
constraint forall ( i in 1..m-1 ) ( mark[i] < mark[i+1] );
constraint alldifferent(differences);
constraint forall (i,j in 1..m where j > i)
(differences[i + ((j-1)*(j-2)) div 2] = mark[j] - mark[i]);
constraint forall (i,j in 1..m where j > i)
(differences[i + ((j-1)*(j-2)) div 2] >= (floor(int2float(( j-i )*( j-i+1 )) / int2float(2))));
constraint differences[1] < differences[(m*(m-1)) div 2];
solve :: int_search(mark, input_order, indomain, complete)
minimize mark[m];
output ["golomb ", show(mark), "\n"];
Run Code Online (Sandbox Code Playgroud)
下三角版本(采用以前的代码并在必要时交换 i 和 j):
% original: https://github.com/MiniZinc/minizinc-benchmarks/blob/master/golomb/golomb.mzn
include "alldifferent.mzn";
int: m;
int: n = m*m;
array[1..m] of var 0..n: mark;
array[1..(m*(m-1)) div 2] of var 0..n: differences;
constraint mark[1] = 0;
constraint forall ( i in 1..m-1 ) ( mark[i] < mark[i+1] );
constraint alldifferent(differences);
constraint forall (i,j in 1..m where i > j)
(differences[j + ((i-1)*(i-2)) div 2] = mark[i] - mark[j]);
constraint forall (i,j in 1..m where i > j)
(differences[j + ((i-1)*(i-2)) div 2] >= (floor(int2float(( i-j )*( i-j+1 )) / int2float(2))));
constraint differences[1] < differences[(m*(m-1)) div 2];
solve :: int_search(mark, input_order, indomain, complete)
minimize mark[m];
output ["golomb ", show(mark), "\n"];
Run Code Online (Sandbox Code Playgroud)