2

我对约束编程真的很陌生，我正在尝试解决一个问题，即从由数字组成的二维数组中，我需要尽可能少的子数组（2D），覆盖尽可能多的原始二维数组尽可能遵守以下规则：

  • 每个子数组必须是原始数组的一个矩形部分
  • 每个子数组中的数字之和不得超过特定数字
  • 每个子数组中必须至少有 2 个数字

例如对于以下矩阵：

3 5 1 4
5 1 2 8
0 8 1 3
8 3 2 1

对于 10 的最大总和，解决方案将是：

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

现在我正在使用diffn()等效于 or-tools ( MakeNonOverlappingBoxesConstraint() ) 来创建将覆盖原始数组的矩形。

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

如果有另一种方法可以在不使用 diffn() 的情况下实现相同的约束，那么我会尝试一下，但我想不出任何其他方式。

谢谢！

4

1 回答 1

1

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

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

例如，在一维数组中，为了从 中获取元素data，位置xtox + 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项目（LongLongToLong在 C# 中），因此您必须创建自己的类来继承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)。

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

于 2017-02-02T09:27:14.143 回答