优化问题 - 矢量映射

A和B是一组N维向量（N=10）|B|>=|A|（|A|=10^2，|B|=10^5）。相似性度量sim（a，b）是点积（必需）。任务如下：对于A中的每个向量a在B中找到向量b，使得所有对的相似之和ss是最大的。优化问题 - 矢量映射

我第一次尝试是贪心算法：

找到对相似度最高，并删除从A那一双，B
重复（1），直到为空

但这种贪婪算法在这种情况下不是最理想的：

 
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。

有没有高效的算法来解决这个问题？谢谢

来源

2011-01-23 user574959

如果合适，请标记为家庭作业。 – 2011-01-23 15:54:25

直觉告诉我，您找不到比* O（| A || B |）*最差情况更快的算法。 – 2011-01-23 16:01:51

@Oli Charlesworth你可能误解了这个问题。 *正确*`O（| A || B |）`算法在这里非常受欢迎:) – 2011-01-23 16:27:28

这实质上是一个matching problem加权bipartite graph。假设权重函数f是点积（|ab|）。
我不认为你的权重函数的特殊结构将会简化很多问题，所以你很难找到最大匹配。

你可以找到这个问题的一些基本算法in this wikipedia article。虽然乍一看他们似乎不适合您的数据（V = 10^5,E = 10^7），但我仍会研究它们：其中一些可能会让您利用您的'跛脚'一组垂直度，一部分数量级更小比其他。

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

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

来源

2011-01-23 16:10:25

我第二次在这里Nikita，这是一个任务（或匹配）的问题。我不确定这对您的问题在计算上是否可行，但是您可以使用匈牙利算法，也称为Munkres' assignment algorithm，其中分配(i,j)的成本是ai和bj的点积的负值。除非您碰巧知道A和B的元素是如何形成的，否则我认为这是针对您的问题的最有效的已知算法。

来源

2011-01-23 16:27:58 carnieri

优化问题 - 矢量映射

回答

相关问题