優化問題 - 矢量映射

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

優化問題 - 矢量映射

回答

相關問題