最適化問題 - ベクトル・マッピング

Question

AとBN次元ベクトル（N=10）、|B|>=|A|（|A|=10^2、|B|=10^5）のセットです。類似度sim（a、b）はドットプロダクト（必須）です。タスクは次のとおりです。各ベクトルに対してAのaを検索すると、Bにベクトルbがあり、すべてのペアの類似度の合計が最大になるように検索されます。

私の最初の試みは、貪欲アルゴリズムた：B

1. が最も類似度の高いペアを見つけるとAからのペアを削除
2. リピート（1）Aが空になるまで

しかしこのような貪欲アルゴリズムは、この場合最適ではない。

 
a_1=[1, 0] 
a_2=[.5, .4] 

b_1=[1, 1] 
b_2=[.9, 0] 

sim(a_1,b_1)=1 
sim(a_1,b_2)=.9 
sim(a_2,b_1)=.9 
sim(a_2, b_2)=.45 

アルゴリズムの戻り値[a_1,b_1]および[a_2, b_2],ss=1.45であるが、最適な溶液収率はss=1.8である。

この問題を解決するには効率的なアルゴリズムがありますか？ありがとう

Answer 1

これは、基本的には、のmatching problemです。重み関数fは内積（|ab|）であると仮定してください。
体重機能の特別な構造が問題を単純化するとは思わないので、最大限のマッチングを見つけることにかなり慣れています。

この問題の基本アルゴリズムはin this wikipedia articleです。一見すると、彼らはあなたのデータ（V = 10^5、E = 10^7）のために実行可能なようには見えませんが、私はまだそれらを研究するでしょう：それらのいくつかは、あなたの「色あい」の頂点セットを利用できますもう一方よりも。

も関連するようですが、アルゴリズムは記載されていません。

解決策ではありませんが、役立つことを願っています。

Answer 2

ここでは二番目のニキータは、割り当て（またはマッチング）問題です。私はこれがあなたの問題に対して計算上実行可能であるかどうかはわかりませんが、Munkres' assignment algorithmとも呼ばれるハンガリーのアルゴリズムを使うことができます。割り当てのコスト(i,j)は内積の負数でaiとbjです。 AとBの要素がどのように形成されているのか分からない限り、これはあなたの問題の最も効率的な既知のアルゴリズムだと思います。