algorithm - 优化问题——向量映射

Question

A 和 B 是 N 维向量集(N=10)，| B|>=|A|(|A|=10^2，|B|=10^5)。相似性度量 sim(a,b) 是点积(必需)。任务如下:对于A中的每个向量a，在B中找到向量b，使得相似度之和所有对的 ss 是最大的。

我的第一次尝试是贪心算法:

1. 找到相似度最高的对，并从 A,B 中移除该对
2. 重复(1)直到A为空

但是这种贪心算法在这种情况下不是最优的:

a_1=[1, 0]a_2=[.5, .4]b_1=[1, 1]b_2=[.9, 0]sim(a_1,b_1)=1sim(a_1,b_2)=.9sim(a_2,b_1)=.9sim(a_2, b_2)=.45

算法返回[a_1,b_1]和[a_2, b_2]，ss=1.45，但最优解产生ss =1.8.

是否有有效的算法来解决这个问题？谢谢

Answer 1

这本质上是一个 matching problem在加权bipartite graph .假设权重函数 f 是点积 (|ab|)。
我不认为你的权重函数的特殊结构会大大简化问题，所以你几乎要找到最大匹配。

你可以找到一些解决这个问题的基本算法in this wikipedia article .虽然乍一看它们似乎不适合您的数据(V = 10^5、E = 10^7)，但我仍然会研究它们:其中一些可能允许您利用您的“lame”顶点集，其中一个部分比另一个小几个数量级。

This article似乎也相关，尽管没有列出任何算法。

不完全是解决方案，但希望它有所帮助。