16

サイズNの整数の配列が与えられた場合、互いに最も近い要素を持つサイズKのサブセットを効率的に見つけるにはどうすればよいでしょうか?

サブセット (x1、x2、x3、..xk) の近さを次のように定義します。

ここに画像の説明を入力 

2 <= N <= 10^5

2 <= K <= N

制約:配列には重複が含まれている可能性があり、並べ替えが保証されていません。

私のブルートフォースソリューションは、大きな N に対して非常に遅く、複数のソリューションがあるかどうかをチェックしません:

N = input()
K = input()
assert 2 <= N <= 10**5
assert 2 <= K <= N
a = []
for i in xrange(0, N):
    a.append(input())
a.sort()

minimum = sys.maxint
startindex = 0

for i in xrange(0,N-K+1):
    last = i + K
    tmp = 0
    for j in xrange(i, last):
        for l in xrange(j+1, last):
            tmp += abs(a[j]-a[l])
            if(tmp > minimum):
                break

    if(tmp < minimum):
        minimum = tmp
        startindex = i #end index = startindex + K?

例:

N = 7
K = 3
array = [10,100,300,200,1000,20,30]
result = [10,20,30]

N = 10
K = 4
array = [1,2,3,4,10,20,30,40,100,200]
result = [1,2,3,4]
4

7 に答える 7

6

あなたの現在の解決策はO(NK^2)（と仮定してK > log N）です。いくつかの分析により、これを に減らすことができると思いますO(NK)。

サイズ K の最も近いセットは、並べ替えられたリストで隣接する要素で構成されます。基本的には、最初に配列を並べ替える必要があるため、その後の分析では、K数値の各シーケンスが並べ替えられていると想定されます。これにより、二重合計を単純化できます。

x[j] >= x[i]配列が次のように並べ替えられていると仮定すると、j > i近さのメトリックを書き直して絶対値を排除できます。

ここに画像の説明を入力

次に、記法を単純な境界を持つ二重和に書き直します。

ここに画像の説明を入力

x[i]との間の内部距離をx[j]3 番目の合計として書き直すことができることに注意してください。

ここに画像の説明を入力

ここでd[l]、今後の表記を簡略化するために使用しました。

ここに画像の説明を入力

d[l]は、リスト内の隣接する各要素間の距離です。fixed の内側の 2 つの合計の構造を見てくださいi。

j=i+1         d[i]
j=i+2         d[i] + d[i+1]
j=i+3         d[i] + d[i+1] + d[i+2]
...
j=K=i+(K-i)   d[i] + d[i+1] + d[i+2] + ... + d[K-1]

内側の 2 つの和の三角形構造に注目してください。これにより、隣接する項の距離に関して、内側の 2 つの合計を 1 つの合計として書き直すことができます。

total: (K-i)*d[i] + (K-i-1)*d[i+1] + ... + 2*d[K-2] + 1*d[K-1]

これにより、合計は次のようになります。

ここに画像の説明を入力

これで、この二重和の構造を見ることができます。

i=1     (K-1)*d[1] + (K-2)*d[2] + (K-3)*d[3] + ... + 2*d[K-2] + d[K-1]
i=2                  (K-2)*d[2] + (K-3)*d[3] + ... + 2*d[K-2] + d[K-1]
i=3                               (K-3)*d[3] + ... + 2*d[K-2] + d[K-1]
...
i=K-2                                                2*d[K-2] + d[K-1]
i=K-1                                                           d[K-1]

ここでも、三角形のパターンに注目してください。合計は次のようになります。

1*(K-1)*d[1] + 2*(K-2)*d[2] + 3*(K-3)*d[3] + ... + (K-2)*2*d[K-2] 
  + (K-1)*1*d[K-1]

または、単一の合計として次のように記述します。

ここに画像の説明を入力

隣接する差のこのコンパクトな単一の合計は、より効率的なアルゴリズムの基礎です。

  1. 配列のソート、順序付けO(N log N)
  2. 隣接する各要素の差を計算します。O(N)
  3. 差分の各シーケンスを反復しN-K、上記の合計、順序を計算しますO(NK)

2 番目と 3 番目のステップを組み合わせることができることに注意してください。ただし、Python の場合は距離が異なる場合があります。

コード：

def closeness(diff,K):
  acc = 0.0
  for (i,v) in enumerate(diff):
    acc += (i+1)*(K-(i+1))*v
  return acc

def closest(a,K):
  a.sort()
  N = len(a)
  diff = [ a[i+1] - a[i] for i in xrange(N-1) ]

  min_ind = 0
  min_val = closeness(diff[0:K-1],K)

  for ind in xrange(1,N-K+1):
    cl = closeness(diff[ind:ind+K-1],K)
    if cl < min_val:
      min_ind = ind
      min_val = cl

  return a[min_ind:min_ind+K]
于 2013-10-21T05:54:44.980 に答える
2

O(N*K)この手順はifAが sortedで実行できます。がソートされていない場合A、時間はソート手順によって制限されます。

これは、次の 2 つの事実に基づいています (Aが注文された場合にのみ関連します)。

  • 最も近いサブセットは常に後続します
  • K後続の要素の近さを計算する場合、距離の合計は、次の 2 つの要素の時間の合計として計算できます。(K-i)*iここで、iは1,...,K-1です。
  • 並べ替えられた配列を反復処理する場合、全体の合計を再計算するのは冗長です。代わりにK、前の 2 つの最小要素間の距離の倍数を削除Kし、2 つの新しい最大要素の距離の倍数を追加できます。この事実は、前のサブセットの近さを使用してサブセットの近さを計算するために使用されてO(1)います。

ここに疑似コードがあります

List<pair> FindClosestSubsets(int[] A, int K)
{
    List<pair> minList = new List<pair>;
    int minVal = infinity;
    int tempSum;
    int N = A.length;

    for (int i = K - 1; i < N; i++)
    {
        tempSum = 0;

        for (int j = i - K + 1; j <= i; j++)
              tempSum += (K-i)*i * (A[i] - A[i-1]);

        if (tempSum < minVal)
        {
              minVal = tempSum;
              minList.clear();
              minList.add(new pair(i-K, i);
        }

        else if (tempSum == minVal)
              minList.add(new pair(i-K, i);
    }

    return minList;
}

この関数は、最適なソリューション (各ソリューションの開始インデックスと終了インデックス) を表すインデックスのペアのリストを返します。これは、最小値のすべてのソリューションを返したいという質問に暗示されています。

于 2013-10-21T06:23:24.320 に答える
1

ソート後、x1、x2、... xk が解である場合、x1、x2、... xk は連続した要素であると確信できますよね?

そう、

  1. 数字の間の間隔を取る
  2. これらの間隔を合計して、k 個の数値間の間隔を取得します
  3. それらの中で最も小さいものを選択してください
于 2013-10-20T22:36:42.793 に答える
1

以下を試してください：

N = input()
K = input()
assert 2 <= N <= 10**5
assert 2 <= K <= N
a = some_unsorted_list
a.sort()

cur_diff = sum([abs(a[i] - a[i + 1]) for i in range(K - 1)])
min_diff = cur_diff
min_last_idx = K - 1
for last_idx in range(K,N):
    cur_diff = cur_diff - \
               abs(a[last_idx - K - 1] - a[last_idx - K] + \
               abs(a[last_idx] - a[last_idx - 1])
    if min_diff > cur_diff:
        min_diff = cur_diff
        min_last_idx = last_idx

min_last_idx から、min_first_idx を計算できます。idx の順序を維持するために range を使用します。これが python 2.7 の場合、直線的に多くの RAM が必要になります。これは、使用するアルゴリズムと同じですが、すべてを合計するよりも少ないため、わずかに効率的です (複雑さの定数が小さくなります)。

于 2013-10-20T20:35:41.470 に答える
0

私の最初の解決策は、すべての K 要素ウィンドウを調べて、各要素を m で乗算し、その範囲の合計を取得することでした。ここで、m は -(K-1) で初期化され、各ステップで 2 ずつインクリメントされ、から最小合計を取得します。リスト全体。したがって、サイズ 3 のウィンドウの場合、m は -2 で、範囲の値は -2 0 2 になります。これは、K ウィンドウの各要素が合計に特定の重みを加えるという特性を観察したためです。たとえば、要素が [10 20 30] の場合、合計は (30-10) + (30-20) + (20-10) になります。したがって、式を分解すると、2*30 + 0*20 + (-2)*10 になります。これは O(n) 時間で達成でき、操作全体は O(NK) 時間になります。ただし、このソリューションは最適ではないことが判明しており、このアルゴリズムが失敗する特定のエッジ ケースがあります。私はまだそれらのケースを把握していませんが、

for(i = 0 ;i <= n - k;++i)
{
    diff = 0;
    l = -(k-1);
    for(j = i;j < i + k;++j)
    {
        diff += a[j]*l;
        if(min < diff)
            break;
        l += 2;
    }
    if(j == i + k && diff > 0)
    min = diff;
}
于 2013-10-22T04:26:33.410 に答える