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

Question

我是约束编程的新手，我正在尝试解决一个问题，我需要从一个由数字组成的二维数组中获取尽可能少的子数组 (2D)，并尽可能多地覆盖尽可能的原始二维数组，遵守以下规则：

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

例如以下矩阵：

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

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

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

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

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

谢谢！

Answer 1

在求解器内部，从基于 IntVar 的数组中获取值的方法是使用它的 MakeElement() function and in this case the 2d version。

这样您就可以从矩阵中获取特定值，但不能获取基于两个 IntVar 的范围（例如矩形的 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);

如果是二维数组（如问题中所示），那么您只需遍历两个维度。唯一的区别是 MakeElement() 的 2d 版本接受一个 IndexEvaluator2 项目（C# 中的 LongLongToLong）所以你必须自己制作继承 LongLongToLong 的 class并覆盖 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];
    }
}

这个 class 的唯一问题是它可以从数组中请求一个值，所以我们必须自己用 if (arg0 >= _rows || arg1 >= _cols) 来处理它。

P.S。我不知道这是否是完成它的最佳方法，但这是我能想到的最好方法，因为我在网上找不到类似的方法。

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

Get dynamic submatrix and apply constraints

constraint-programming

or-tools