时间戳

首页 > 解决方案 > 有没有办法在 MiniZinc 中交换二维数组（矩阵）的列，并跟踪它？

arrays - 有没有办法在 MiniZinc 中交换二维数组（矩阵）的列，并跟踪它？

问题描述

我目前正在研究 MiniZinc。

我得到了以下二维数组（矩阵）：

0  1  0  0  0  0 
0  1  1  1  0  1 
0  0  0  0  1  1

假设它有一些顺序。左边的第一列是第一列，右边的下一列是第二列，依此类推，例如：

1  2  3  4  5  6
----------------
0  1  0  0  0  0 
0  1  1  1  0  1 
0  0  0  0  1  1

我需要一种方法（比如约束或其他东西）来帮助我减少一行中的第一个 1 和同一行的最后一个 1 之间的距离。例如，一个理想的矩阵是：

1  2  3  4  6  5
----------------
0  1  0  0  0  0 
0  1  1  1  1  0 
0  0  0  0  1  1

如您所见，这是通过将第 5 列和第 6 列交换在一起。但我不知道如何做到这一点，并跟踪顺序，知道第一个矩阵有 [1 2 3 4 5 6] 而第二个是 [1 2 3 4 6 5]

我真的不知道如何在二维变量数组中对这种交换列进行建模。

谢谢您的帮助！

标签： arrayssortingswapconstraint-programmingminizinc

解决方案

这是一个简单的方法：假设您的原始数据矩阵是data。您可以使用数组（例如x）来跟踪列的新顺序。要使用您使用的新订单data[row,x[col]]，例如

 [data[row,x[col]] | row in 1..num_rows, col in 1..num_cols]

这是一个小例子。请注意，您必须添加约束x以使其更有趣。

include "globals.mzn"; 
int: num_rows;
int: num_cols;
array[1..num_rows, 1..num_cols] of int: data;

% decision variables
array[1..num_cols] of var 1..num_cols: x; 

solve satisfy;

constraint
  all_different(x)
  % /\ more constraints on x  ....
;

output [
    "data:\n",
    show2d(data) ++ "\n" ++ 
    "x: \(x)\n",
    "new_data:\n",
    show2d(array2d(1..num_rows, 1..num_cols, [data[i,x[j]] | i in          1..num_rows,j in 1..num_cols])) ++ "\n"
];

% data
num_rows = 3;
num_cols = 6;
data = array2d(1..num_rows,1..num_cols,
  [
  0,1,0,0,0,0,
  0,1,1,1,0,1,
  0,0,0,0,1,1
  ]);

解决方案之一是：

 data:
 [| 0, 1, 0, 0, 0, 0 |
    0, 1, 1, 1, 0, 1 |
    0, 0, 0, 0, 1, 1 |]

 x: [3, 1, 4, 5, 2, 6]
 new_data:
 [| 0, 0, 0, 0, 1, 0 |
    1, 0, 1, 0, 1, 1 |
    0, 0, 0, 1, 0, 1 |]

推荐阅读