计算最高的2边平均值匹配

Question

“问题的第一部分致力于更好地解释概念，因此我们知道，我们正在计算的内容。如果您觉得不必要，请随意跳到下面的部分，”

---

1.问题的基本概述：

您好，我有一个excel应用程序，类似于约会网站。您可以打开各种用户配置文件，甚至可以根据业余爱好，城市和其他标准浏览数据并找到潜在的匹配项。

它的计算方式与问题无关，但“查找匹配”计算的结果看起来像这样，是一个有序的用户列表，具体取决于它们的拟合程度（最后一栏）

与该问题有关的主要是：

• 第一列（ID） - 用户的ID
• 最后一栏（Zhoda） - 其他用户的Match%，与当前选择的一个

2.我需要做什么 - 它目前是如何完成的

我需要在所有用户中找到平均最高匹配。如果我以算法编写这个：

1. Loop through all users
2. For each user in our database calculate the potential matches
3. Store the score of selected user ID, against all the found user IDs
4. Once it's all calculated, pit all users against each other _
   and find the highest match on average

显然这听起来很复杂/模糊，所以这是一个简化的例子。假设我已经完成了第一个3步骤并获得了以下结果：

在这里，期望的结果将是：

User1 <- 46% -> User2

因为他们的平均综合百分比最高：

• User1 vs User2：30%
• User2 vs User1：62% User1 <- (30+62)/2 -> User2

没有其他可能的用户组合具有更高的match%平均值

---

3.问题背后的目的：

现在很明显你可能会问，如果我得到它后面的计算，那么为什么首先要问这个问题呢？嗯，原因是一切与一切的结合是非常低效的。

在我的数据库中，只要有100个用户而不是3个用户。我将不得不单独对100*100进行match%计算，更不用说之后检查每个用户的average Match%与另一个用户。

是否有一种更好的方式来接近，我也可以

• 最小化我必须计算的数据
• 一些排序算法，我可以跳过某些计算，以便更快
• 计算最高average match%的整体更好的方法

所以概括一下：

• 我有一个用户数据库。
• 每个用户对每个其他用户都有一定数量的Match%
• 我需要找到两个用户，一个对另一个用户（双方）在所有可能的组合中具有最高的Match%平均值。

---

如果您需要任何其他信息，请告诉我们。 我会尝试尽可能地更新问题。

Answer 1

正如你提出的问题 - 不，你无法显着提高速度。由于您已将match%作为任意函数呈现，仅受隐含范围约束，因此您无法利用数学属性来减少最坏情况搜索方案。

在给定的情况下，您可以做的最好是利用范围。首先，不要打扰“平均”：因为这些是严格的二元匹配，除以2只是浪费时间;保持总数。

从选择一对开始;做双向比赛。一旦您发现总共超过100，存储该值并使用它来修剪任何不合标准的搜索。例如，如果你最好的匹配到目前为止总共120，那么如果你找到一对match(A, B) < 20，你不打扰计算match(B, A)。

在两者之间，您可以维护第一个匹配的排序列表（O（n log n））;不要做第二场比赛，除非你有理由相信这一场比赛可能会超过你的最佳比赛。

优化的其余部分包括收集有关匹配的统计信息，以便您可以平衡何时首先执行双向匹配。例如，您可以推迟第二场比赛的第一场比赛，该比赛低于已经推迟的第70场比赛。这是希望找到一个更好的匹配，完全消除这一个。

---

如果您收集有关match函数分布的统计信息，那么您可以更好地调整此来回过程。

如果您可以推导出有关match函数的数学属性，那么可能有一些方法可以利用这些属性来提高效率。但是，由于它已经缺乏正式的拓扑“距离”度量标准d（见下文），我对此并不抱太大希望。

基本指标属性：

• d（A，B）存在所有对（A，B）
• d（A，B）= d（B，A）
• d（A，A）= 0 //不适用于二分图
• d服从三角不等式 - 它不直接适用，但对二分图有一些间接影响。