3

1 から始まる数直線上の位置に収まる 1 から N までの番号付き要素のリストがあります。これらの要素には次の制約もあります。

  • 要素 1 は位置 1 にあり、要素 N は位置 >= 要素 N-1 の位置にある必要があります。(つまり、要素 2 は位置 1、要素 3 は位置 7、要素 4 は位置 8 (ただし、位置 5 ではない) にある可能性があります)。
  • 一部の要素は、線上で互いに一定の距離内にある必要があります。
  • 一部の要素は、ライン上で他の要素から一定以上離れている必要があります。

私の目的は、要素 1 と要素 N の間の最大スパンを表す整数を返すことです。整列が不可能な場合は -1 を返し、要素が任意の距離離れている場合は -2 を返します。

私は与えられます：

  • 要素数
  • withinArray[][] ここで、 withinArray[x][y] = 距離要素 x と y がライン上にある必要があります。ゼロ値は、制約がないことを表します。
  • atLeastArray[][] ここで、atLeastArray[x][y] = 距離要素 x と y は線上で離れている必要があります。ゼロ値は、制約がないことを表します。

入力例は次のようになります: 4 つの要素、withinArray[1][3] = 10、withinArray[2][4] = 20、および atLeastArray[2][3] = 3 (他のすべての配列値はゼロ)。

この入力の戻り値は 27 になります (要素 1 は位置 1、要素 2 は位置 8、要素 3 は位置 11、要素 4 は位置 28)。

これまでのところ、私はこれを思いつきました：

for (int i = 1; i < n; i++) {
    for (int j = 1; j < atLeastArray.length; j++) 
        if (j == i)
            positions[i] = positions[j] - atLeastArray[i][j];
    for (int j = 1l j < withinArray.length; j++) 
        if (j == i) 
            positions[j] = positions[i] + withinArray[i][j];
}
return positions[n] - positions[1];

これにより、私が示した例に対する正しい答えが得られますが、すべての場合に機能するという確信はありません。また、不可能な場合や要素が離れている可能性がある場合のケースを定義する方法もわかりません。

4

1 に答える 1

0

これを線形計画法で考えてみましょう。変数 x_1、...、x_n と、x_i <= x_(i+1)、x_i - x_j <= w_{ij}、および x_i - x_j >= a_(ij) という形式の一連の制約があります。

変数に対してフーリエ・モツキン消去法を実行するとどうなるか注目してください --- つまり、変数が現れるすべての方程式でそれを分離し、2 つの不等式のセットを形成します。たとえば、さまざまな k に対して x_i <= foo_k 、さまざまな k に対して x_i >= bar_l とします。 l、次に x_i を含むすべての制約を削除し、それらを各 k および l の制約 bar_l <= foo_k に置き換えます。

以前と同じ形式の拘束がさらに増えます! x_i - x_j <= a および x_i - x_j <= b がわかっている場合、x_i - x_j <= min(a,b) と結論付けて、前の 2 つの制約を忘れることができることに注意してください。したがって、n^2 以上の制約は必要ありません。

したがって、x_1 と x_n 以外のすべての変数を削除するだけです。最後に、x_n - x_1 >= a と x_n - x_1 <= b という 2 つの制約があります。a <= b であること、および b が無限大ではないことを確認してください。

ええと、誰かがこのことについて数学を書く方法を教えてくれたら、私は感謝します:)

于 2012-12-05T03:06:05.340 に答える