algorithm - 拥有/想要列表匹配算法

Question

拥有/想要列表匹配算法

我正在一个高流量网站上实现一个元素交易系统。我有大量用户，每个用户都为许多特定项目维护一个 HAVE 列表和一个 WANT 列表。我正在寻找一种算法，使我能够根据您的 HAVE 和 WANT 与他们的匹配有效地推荐贸易伙伴。理想情况下，我想找到具有最高相互交易潜力的合作伙伴(即我有很多你想要的东西，你有很多我想要的东西)。我不需要找到全局最高潜力对(这听起来很难)，只需找到给定用户的最高潜力对(或者甚至只是一些高潜力对，而不是全局最大值)。

例子:

User 1 HAS A,C WANTS B,DUser 2 HAS D WANTS AUser 3 HAS A,B,D WANTS CUser 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.

复杂性的另一个来源是项目具有不同的值(value)，我想匹配可能的最高值(value)交易，而不是两个交易者之间的最大匹配数。因此，在上面的示例中，如果所有项目都值 1，但 A 和 D 都值 10，则用户 1 现在与用户 3 上方的用户 2 匹配。

执行此操作的一种简单方法是计算寻找合作伙伴的用户与数据库中所有其他用户之间的最大交易值(value)。我在考虑一些关于正确事情的查找表，我可能会做得更好。我试过谷歌搜索，因为这似乎是一个经典问题，但我不知道它的名字。

谁能推荐一个解决这个问题的好方法？我见过像 Magic Online Trading League 这样的网站似乎可以实时解决这个问题。

Answer 1

你可以在 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 名。