我有一个问题可以归结为寻找一种将三角矩阵映射到跳过对角线的向量的方法。在跳过对角线的向量上映射上三角矩阵
基本上我需要使用Gecode库
// 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);
向该MiniZinc(功能性)代码
constraint
forall (i in 1..m-1 , j in i+1..m)
((differences[?]) >= (floor(int2float((j-i)*(j-i+1))/int2float(2))));
把这种C代码和我需要在differences[?]
弄清楚的索引。
MiniZinc是一种功能/数学语言,没有适当的循环。 因此,我必须映射那些触及所有且仅接触上三角矩阵的单元格的索引i和j,跳过其对角线,将k指向从0到任意值的单元格。
如果这是一个普通的三角矩阵(它不是),解决like this会做
index = x + (y+1)*y/2
我处理的矩阵是一个正方形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"];
感谢。
我对这个答案仍然很感兴趣。我将再次使用这个非常公式来进行另一个项目。你可以看看代码吗?谢谢。 – Agostino 2015-01-12 21:29:33
对不起,长时间回复。看看我的编辑。关键点:用T(i,j)= i +(j-1)*(j-2))/ 2来映射{(i,j)|。 1 <= i j(下三角形),但是我的代码使用元组j> i(上三角形)。无论哪种方式将工作,但你问上部三角问题,所以我给了代码。如果你想要下三角的代码,随时问。 –
2015-01-13 21:53:00
删除列表理解。 var 0..n:differences = [mark [j] - mark [i] |的array [int]而不是var [int] i in 1..m,j in i + 1..m];''你只需要var 0..n的差阵[1 ..(m *(m-1))div 2]'。 – 2015-01-13 23:59:49