获取动态子矩阵并应用约束条件

我对约束编程非常陌生，我试图解决一个问题，从包含数字的二维数组中，我需要尽可能少地使用子数组（2D）覆盖尽可能多的原始2D阵列成为可能，服从以下规则的：获取动态子矩阵并应用约束条件

每个子阵列必须是原始
号的每个子阵列必须不超过一个特定的所述的总和的矩形部分号码
每个子阵列必须至少有两个数字

例如，对于下面的矩阵：

对于10的最大总和，一个解决办法是：

3 -not picked 
{ 5 1 4 } 
{ 5 1 } 
{ 2 8 } 
{ 0 8 } 
{ 1 3 
    2 1 } 
8 -not picked

现在我使用diffn()等效的或工具（ MakeNonOverlappingBoxesConstraint()）来创建要覆盖原始数组的矩形。

我的问题是如何获取由diffn（）创建的矩形并根据每个矩阵的位置和大小拆分原始矩阵，因此我可以应用Sum约束。

如果没有使用diffn（）来实现相同的约束的另一种方法，那么我会试试看，但我想不出任何其他方式。

谢谢！

来源

2017-01-09 MitsakosGR

从求解器内部基于IntVar的数组中获取值的方法是使用MakeElement()函数，在此例中为2d version。

通过这种方式，您可以从矩阵中获取特定值，但不是基于两个IntVars（例如矩形的x-dx）的范围。要完成范围部分，您可以使用循环和ConditionalExpression()来确定指定值是否在范围内。

例如，在一维数组中，为了从data得到的元素，位置x到x + dx将如下

int[] data = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; 
IntVar x = solver.MakeIntVar(0, data.Length - 1); 
IntVar dx = solver.MakeIntVar(1, data.Length); 

solver.Add(x + dx <= data.Length); 

IntVarVector range = new IntVarVector(); 
for (int i = 0; i < dx.Max(); i++) 
{ 
    range.Add(solver.MakeConditionalExpression((x + i < x + dx).Var() , solver.MakeElement(data, (x + i).Var()), 0).Var()); 
} 

solver.Add(range.ToArray().Sum() <= 10);

在2D阵列的情况下（如在问题），那么你只是迭代通过两个维度。唯一不同的是，MakeElement()的二维版本接受IndexEvaluator2项（C＃中的LongLongToLong），因此您必须创建自己的类继承LongLongToLong并覆盖Run()函数。

class DataValues: LongLongToLong 
{ 
    private int[,] _data; 
    private int _rows; 
    private int _cols; 

    public DataValues(int[,] data, int rows, int cols) 
    { 
     _rows = rows; 
     _cols = cols; 
     _data = data; 
    } 

    public override long Run(long arg0, long arg1) 
    { 
     if (arg0 >= _rows || arg1 >= _cols) 
      return 0; 

     return _data[arg0, arg1]; 
    } 
}

这一类唯一的问题是，它可以要求关闭阵列的值，所以我们必须if (arg0 >= _rows || arg1 >= _cols)处理它自己。

P.S.我不知道这是否是实现它的最好方法，但这是我能想到的最好的方法，因为我在网上找不到任何类似的东西。

来源

2017-02-02 09:27:14 MitsakosGR

获取动态子矩阵并应用约束条件

回答

相关问题