おそらく異なるサイズの2つのセット間の距離の測定

Question

2組の整数AとBがありますが、必ずしも同じサイズである必要はありません。私の必要に応じて、私は2つの要素aとb（整数）の間の距離をちょうどabs(a-b)にします。次のように私は2つのセットの間の距離を規定してい

：

1. セットが同じサイズである場合、すべての対の距離の総和を最小化する[B]（A及びBからBから）、可能なすべての「ペアパーティション」（最小限の可能なパーティションがある）にわたって最小化されます。
2. セットが同じサイズでない場合、サイズがm、サイズがnのB（mは<）とし、サイズがmのBのすべてのサブセットに（1）からの距離を最小にします。

私の質問は、上記の定義に従って、以下のアルゴリズム（直感的な推測）が正しい答えを与えるかどうかです。

• はD(i,j) = abs(A(i)-B(j))
• 、Dの最小の要素を見つけ、それを蓄積し、行とその要素の列を削除して、サイズm X nのマトリックスDを構築します。次の最小エントリを累積し、すべての行と列が削除されるまで蓄積し続けます。

例えば、A={0,1,4}とB={3,4}場合、D（左上とに要素を有する）である：

3 4

03 4

12 3

41 0

は距離が1と4と3とのペアリング4から、0 + 2 = 2です。

Answer 1

この問題は、スキーとスキーヤーの問題とも呼ばれ、長さと高さが異なるn個のスキーヤーとm個のスキーヤーがいることに注意してください。目標は、スキーヤーをスキーヤーに合わせて、高さとスキーの長さの差の合計が最小になるようにすることです。

問題を解決するには、O（n^3）時間が必要な最小体重バイパータイトマッチングを使用できます。

O（n）余分なメモリでO（n^2）時間を達成するには、以下の単純な動的プログラミングアルゴリズムを使用します。

ポイントがすでにpaperに記載されているアルゴリズムを使用してソートされている場合は、問題を線形時間で解決することができます。

はO（n^2）の動的プログラミングアルゴリズム：上記アウターforループの各反復i後

if (size(B) > size(A)) 
    swap(A, B); 
sort(A); 
sort(B); 
opt = array(size(B)); 
nopt = array(size(B)); 
for (i = 0; i < size(B); i++) 
    opt[i] = abs(A[0] - B[i]); 
for (i = 1; i < size(A); i++) { 
    fill(nopt, infinity); 
    for (j = 1; j < size(B); j++) { 
    nopt[j] = min(nopt[j - 1], opt[j - 1] + abs(A[i] - B[j])); 
    swap(opt, nopt); 
} 
return opt[size(B) - 1]; 

、opt[j]要素{B[0],..., B[j]}を用い{A[0],..., A[i]}に一致する最適解を含んでいます。

このアルゴリズムの正確さは、a1がb1と一致し、a2がb2と一致し、a1が< a2の場合、b1 < = b2であるという事実に依存しています。

Answer 2

ありませんそれは、例えば、最良の答えではありません。 A：{3,7}とB：あなたが選択されます{0,4}：{（3,4）、（0,7 ）}で、距離は8ですが、{（3,0）、（4,7）}を選択してください。この場合、距離は6です。

Answer 3

あなたの答えは、最小値に近似していますが、必ずしも最適値ではありません。あなたは一般的にはるかに簡単で良い結果をもたらす「貪欲な」アプローチに従っていますが、最良の答えを保証するものではありません。

Answer 4

最適化を得るには、Dの割り当て問題を解決します。

割り当て問題では、2つのグラフで完全な一致が検出され、合計エッジの重みが最小になり、問題に完全に対応します。それはPにもあります。

EDIT OPの問題が割り当てにどのようにマッピングされるかを説明します。

説明を簡単にするために、特殊な要素e_kを使用して、小さい方のセットを拡張してください。

Aを作業者の集合、Bをタスクの集合（内容は単なるラベル）とします。

コストは、AとBの要素間の距離（つまり、エントリはD）とします。 e_kと何かの間の距離は0です。

次に、コストが最小限になるように、AとBの完全な一致（つまり、すべての作業者がタスクに一致している）を探します。このはの割り当て問題です。