動的サブマトリクスを取得して制約を適用する

Question

私は、制約プログラミングの新機能であり、数値からなる2次元配列からできるだけ少ない量のサブ配列（2D）を取る必要がある問題を解決しようとしています。 、次の規則に従う、可能な限りオリジナルの2Dアレイのような多くの被覆：すべてのサブアレイは、各サブアレイ内の数字の合計が特定を超えてはならないオリジナル

の矩形部分でなければならない

• を数字
• すべてのサブアレイに2つ以上の数字が必要です

たとえば、次の行列のために：10の合計の最大値については

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

、解決策は次のようになります。

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

今、私はdiffn()の同等または-ツールを（使用していますMakeNonOverlappingBoxesConstraint()）を使用して、元の配列をカバーする四角形を作成します。

私の問題は、diffn（）によって作成された矩形を取得し、元の行列をそれぞれの位置とサイズに基づいて分割する方法です。Sum制約を適用できます。

diffn（）を使用せずに同じ制約を達成する別の方法がある場合は、試してみますが、他の方法では考えられません。

ありがとうございました！

Answer 1

ソルバー内のIntVarに基づいて配列から値を取得する方法は、MakeElement()関数を使用することです。この場合は2d versionです。

このようにして、行列から特定の値を得ることはできますが、2つのIntVars（たとえば、x - dxの長方形）に基づく範囲は得られません。範囲部分を達成するには、ループとConditionalExpression()を使用して、指定された値が範囲内にあるかどうかを調べることができます。 1D配列の例

は、 dataから要素を取得するために、そしてあなただけの反復（質問のように）2次元配列の場合に

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); 

を次のようにxx + dxには次のようになり位置します両方の次元を通して。唯一の違いはMakeElement()の2dバージョンがアイテム（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.これを達成するための最良の方法であるかどうかは分かりませんが、私が考えることのできる最高のものでした。