填充项目矩阵的算法,项对

)在基于轮的事件中对用户进行比较和匹配。

目前,我正在存储每个用户对用户的比较(使用余弦相似性),然后找到两个用户都可用的轮。我当前的设置在较小的规模下运行良好,但在较大的数据集中我似乎缺少一些匹配。

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

这不是精确的代码,而是构建时间表的通用算法。有没有人知道一个更好的方法来填充一个项目对矩阵,其中没有一个项目可以在同一个插槽的多个位置?

EDIT

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

是这样的:

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%左右的匹配,而上面的冲突会导致问题。