有/想要列表匹配算法
我正在一个高流量的网站上实施一个项目交易系统.我有大量用户,每个用户都维护一个特定项目的HAVE列表和WANT列表.我正在寻找一种算法,这将允许我根据您的HAVE和WANT匹配他们有效地建议贸易伙伴.理想情况下,我希望找到具有最高互相交易潜力的合作伙伴(即我有很多你想要的东西,你有很多我想要的东西).我不需要找到全局最高潜力对(听起来很难),只需找到给定用户的最高潜在对(或者甚至只是一些高潜力对,而不是全局最大对).
例:
User 1 HAS A,C WANTS B,D User 2 HAS D WANTS A User 3 HAS A,B,D WANTS C User 1 goes to the site and clicks a button that says "Find Trading Partners" and the top-ranked result is User 3, followed by User 2.
复杂性的另一个来源是项目具有不同的值,并且我希望匹配最高价值的交易,而不是两个交易者之间的最多匹配.因此,在上面的示例中,如果所有项目都值1,但A和D都值10,则用户1现在与用户3上方的用户2匹配.
一种天真的方法是计算寻找合作伙伴的用户与数据库中所有其他用户之间的最大交易价值.我正在考虑一些关于正确事情的查找表,我可能会做得更好.我试过谷歌搜索,因为这似乎是一个经典问题,但我不知道它的名称.
任何人都可以推荐一个解决这个问题的好方法吗？我已经看到像Magic Online Trading League这样的网站似乎可以实时解决它.
您可以通过保留拥有并想要给定物品的所有人员的散列表（或者在数据库中，索引）来做到这一点O(n*k^2) （n 是人数，k 是他们拥有/想要的物品的平均数量） ，然后为所有拥有当前用户想要的物品以及想要当前用户拥有的物品的人评分。显示前 10 名或前 20 名分数。
[编辑] 如何在 SQL 中实现这一点的示例：
-- Get score for @userid wants
SELECT UserHas.UserID, SUM(Items.Weight) AS Score
FROM UserWants
INNER JOIN UserHas ON UserWants.ItemID = UserHas.ItemID
INNER JOIN Items ON Items.ItemID = UserWants.ItemID
WHERE UserWants.UserID = @userid
GROUP BY UserWants.UserID, UserHas.UserID
这会根据当前用户想要的物品，为您提供其他用户及其分数的列表。对当前用户拥有其他人想要的项目执行相同的操作，然后以某种方式将它们组合起来（添加分数或您想要的任何内容）并获取前 10 个。