獲取動態子矩陣並應用約束條件

我對約束編程非常陌生，我試圖解決一個問題，從包含數字的二維數組中，我需要儘可能少地使用子數組（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

獲取動態子矩陣並應用約束條件

回答

相關問題