ruby - 填充项目矩阵的算法，项目对

Question

大家好，我有一种快速约会类型的应用程序(不用于约会，只是一个类似的概念)，可以比较用户并在基于回合的事件中匹配他们。

目前我正在存储每个用户与用户的比较(使用余弦相似度)，然后找到两个用户都可用的回合。我当前的设置适用于较小的规模，但我似乎在较大的数据集中缺少一些匹配项。

For example with a setup like so (assuming 6 users, 3 from each group)

Round (User1, User2)
----------------------------
1  (x1,y1)  (x2,y2)  (x3,y3)
2  (x1,y2)  (x2,y3)  (x3,y1)
3  (x1,y3)  (x2,y1)  (x3,y2)

我的方法现在很有效，可以确保每个用户都遇到合适的用户而不会重叠，这样用户就被排除在外，只是没有更大的数据集。

My current algorithm

我像这样存储 x 中每个用户与 y 中每个用户的比较

Round, user1, user2, similarity

为了构建事件时间表，我简单地按相似性对比较进行排序，然后迭代结果，为两个用户找到一个开放回合，如下所示:

event.user_maps.all(:order => 'similarity desc').each do |map|
  (1..event.rounds).each do |round|
    if user_free_in_round?(map.user1) and user_free_in_round?(map.user2)
      #creates the pairing and breaks from the loop
    end
  end
end

这不是精确的代码，而是构建时间表的通用算法。有谁知道一种更好的方法来填充项目配对矩阵，在这种矩阵中，任何一项都不能出现在同一个插槽中的多个位置？

编辑

澄清一下，我遇到的问题是，在较大的集合中，我将最高相似度匹配放在首位的算法有时会导致冲突。我的意思是，用户以这样一种方式配对，即他们没有其他用户可以见面。

像这样:

Round (User1, User2)
----------------------------
1  (x1,y1)  (x2,y2)  (x3,y3)
2  (x1,y3)  (x2,nil)  (x3,y1)
3  (x1,y2)  (x2,y1)  (x3,y2)

我希望能够防止这种情况发生，同时保留在调度中给予更高优先级的更高相似用户的需求。

在真实场景中，匹配的数量远远多于可用的回合，x 用户与 y 用户的数量不均匀，在我的测试用例中，我不会让每一轮都充满，而我只会让大约 90% 左右的人被填充，而像上面这样的碰撞导致了问题。

Answer 1

我认为即使在编辑之后这个问题仍然需要澄清，但我可能会遗漏一些东西。

据我所知，您想要的是每一轮新回合都应该以最佳匹配开始(定义为所有匹配对的余弦相似度之和)。任何一对 (x_i,y_j) 在一轮中匹配后，就没有资格进入下一轮。

您可以通过构建一个二部图来做到这一点，其中您的 X 是一侧的节点，Y 是另一侧的节点，边权重是余弦相似度。然后您会在此图中找到最大加权匹配。对于下一轮，您消除了上一轮已经使用的边并再次运行匹配算法。有关如何在二分图中编码最大权重匹配的详细信息，请参阅 here .

顺便说一句，这个解决方案不是最优的，因为我们以贪婪的方式从一轮到下一轮进行。我有一种感觉，获得最佳解决方案将是 NP 困难，但我没有证据，所以不能确定。