2

AとBの2つのリストがあります。Aは最大1000要素、Bは最大100要素になります。ペアの絶対差の合計が最小になるように、Bのすべての要素をAの要素に一致させたいと思います。

つまり、|B|を選択したい Aとは異なるインデックスを作成し、それらをBのインデックスに割り当てて、次の合計が最小化されるようにします。sum（abs（A [j] --B [i]）for i in | B |、j = index_mapping（i））

私の最初のアプローチは次のとおりです。

  1. Bの各要素について、|B|を計算します。Aの最も近い要素。
  2. 貪欲な方法でペアを選択します（つまり、最初に最小エラー）

いくつかの簡単な例で遊んでみると、私のアプローチが最善ではないことは明らかです。私の目的には問題なく機能するはずですが、誰かがより良いアプローチを提案できるかどうか疑問に思っていました。

4

2 に答える 2

1

最終的に両方のリストを並べ替え、一致するようにそれらを繰り返し処理しました。これは私がやっていたことには十分うまくいきました。

于 2011-07-20T19:54:54.383 に答える
0

うーん...最初に頭に浮かぶのは、AとBを並べ替えることができれば、A[j]からB[i]への最初のマッピングを見つけたら、B [i+1]の場合はA[0]の代わりにA[j]を使用してテストを開始できます。

例えば：

A = [ 23, 34, 38, 52, 67, 68, 77, 80, 84, 95 ]
B = [ 31, 33, 64, 65, 99 ]

B [0] = 31から始めて、最も近い一致A[1]が見つかるまでAをステップスルーします。リストは順序付けられているので、 B[1]はA[1]よりも小さいものとは一致しないことがわかっているので、そこから比較を開始できます。結局のところ、A[1]は依然として最も近い一致です。B[2]では最も近い一致はA[4]であるため、B[3]はA[4]より低いものとは一致しないことがわかっているので、A[0]からA[3]を検索する必要はありません。

于 2011-06-02T04:52:34.770 に答える