随机匹配用户
Randomly matching users
我正在尝试考虑一种算法，该算法根据用户定义的某些属性（位置、兴趣等）随机配对用户。许多应用程序和游戏都实现了类似的算法，例如，Tinder（流行的约会移动应用程序）根据用户的位置、性别和年龄随机匹配用户。不过，对于 Tinder，两个用户 "pairing" 之间的关系并不重要。然而，我正在尝试将用户配对以进行某种即时通信和交互。
问题是我不知道从哪里开始。如果轮子已经完成了很多次，或者至少使用另一个实现作为参考，我不想重新发明轮子。不过，我的 Google 搜索并不充分，很可能是因为不知道要搜索什么，例如特定的算法名称。
如何实现加权随机用户匹配算法？最佳匹配算法会更好。我不希望您提供一个代码的所有代码（除非它真的很容易），psuedo-code/theory 或 link 到一个定义良好的库或实现就可以了。
目前我在想什么：
Storing/Connecting
- 将用户分为两个 table：主动和被动。 Active User 通过 Passive table 执行随机 search/pair 算法。向匹配的被动用户发送匹配请求。被动用户接受第一个收到的匹配请求拒绝所有其他。用户匹配进行通信，可以从 table 中删除。如果被动用户在一段时间后不是 "picked"，则可能需要超时，以便它可以成为主动用户。
正在搜索
- 活跃用户根据活跃用户位置的设置范围之类的东西随机选择一定数量的被动用户。考虑到被动用户从他们的位置设置的范围？
加权算法
- 每个用户定义的属性都分配有特定的重要性权重。计算匹配属性的数量（相似或范围内的？）以及它们组合在一起的权重。根据匹配值对用户进行排序。为匹配度最高的被动用户执行 storing/connecting 阶段。如果该用户接受匹配请求，则他们将连接，如果不尝试下一个最高匹配的被动用户。如果没有建立连接，则重新开始整个算法。
如果你想要随机分配，解决方案很简单。如果你想要别的东西，你需要首先说明你有什么标准来决定如何对比赛进行排名；您已经开始了这个过程，但是在您能够清楚地说明 什么 您正在寻找之前，决定 如何 完成它将会浪费很多时间努力。
更具体地说，这里有一个算法：使用任何标准为每个用户分配一个数字分数；按该分数对列表进行排序；匹配每个连续的对。如果这没有产生令人满意的匹配集，请解释它违反了哪些标准（因为我在你的问题描述中找不到任何标准）。
如果相反，您可以为每个可能的配对计算分数，则可以改为这样做：计算所有此类配对分数。重复：取得分最高的那对并将这两个从池中移除。这将问题简化为一个集合操作问题。
这是我目前的情况。
How would I implement a weighted random User matching algorithm?
实现这种算法有多个部分。您需要一种方法来确定用户之间的相似性以及对这种相似性进行评级的方法。此外，您需要一种执行算法的方法，例如：是将所有用户都放入一个池中，然后服务器进行匹配，还是将用户分开，一个执行操作，而另一个等待匹配（如中所述）问题）。
至于确定用户之间的相似度，请查看Collaborative Filtering. This StackExchange问答处理类似的问题。协同过滤通常用于推荐系统（电子商务网站推荐您可能感兴趣的产品），但算法的基础可以应用于匹配用户之间的相似性。
相似度评分取决于您选择使用的特定算法，但加权值是一种方法。在这种情况下，用户包含的每个属性都被分配了一个加权值，表示该值对算法的重要性。权重值越高越重要。您选择的您认为更重要的加权值。该值本身没有意义，但相对于算法很有用。类似地，分配给用户的总计算相似值（应用权重的整个算法的结果值）本身没有意义，但与具有计算值的其他用户相比时很有用。
获得这些值后，您可以简单地对用户进行排序（最高值最相似），然后连接。 但是您如何准确地确定用户之间的相似性？一种方法是查看属性并查看它们是否相等。
例如，假设所有用户都分配了一个布尔值 "likesMusic" 属性。要比较用户 1 和用户 2 之间的此属性，看看它们是否相等：
if(User1.getLikesMusic() == User2.getLikesMusic()){
return 1;
else{
return 0;
}
值0可以在算法中用于不匹配，1可以用于精确匹配。然后可以将 returned 值乘以属性分配的权重值，并添加到所有其他属性计算中。这适用于匹配或不匹配的值，但对于可能匹配的值呢？例如，考虑一个属性 "favFoods"，它是一组用户最喜欢的食物。用户可以分享一些、全部或不分享最喜欢的食物。
return (User1.getFavFoods().intersection(User2.getFavFoods()) / User1.getFavFoods().size());
上面的伪代码通过获取集合之间的相交值的数量除以User1的设置长度来比较User2最喜欢的食物与User1的相似程度。 注意： 必须切换值才能了解用户 1 最喜欢的食物与用户 2 的相似程度。这种方法的好处是它使我们保持在 0 和 1 之间的 return 范围内。这样我们可以保持我们的初始值 1 是完全匹配，0 是不匹配，并且两者之间的所有内容都会有点匹配。
这适用于集合和列表，但是可以在一个范围内的值呢？这就是事情变得有点复杂的地方。例如，考虑每个用户都有一个年龄属性。年龄越接近越好。我们可以取两个用户年龄之间的差异，然后差异越大匹配值越小。但是当差异值变大时匹配值变小的速率是多少？这个值，下降率，必须根据适合您的特定应用程序的任何内容来选择。例如，假设每两年有差异，我们就会将相似度降低 10%。由于 1 将是完全匹配，因此以这种下降率，我们有：
return 1 - ((abs(User1.getAge() - User2.getAge()) / 2) * 0.1);
注意：您必须注意确保从 1 中减去的值不超过 1，因为我们不需要负数。
以上方程式应该涵盖了您会遇到的大多数情况。现在，如果我们知道用户属性的所有 "types"（exact、set 或 range），我们可以使用正确的公式得到值 V，乘以它的权重 W，得到总匹配两个用户之间的值，M:
M = (V1 * W1) + (V2 * W2) + , ... , + (Vn * Wn)
此算法足以进行单向匹配（如果您允许设置属性具有不同的长度，那么 User1 可能与 User2 匹配得很好，但 User2 可能与 User1 匹配得不太好，令人惊讶）。因此，对于双向匹配，您需要调整算法。例如，也许您可以执行从 User1 到 User2 和从 User2 到 User1 的匹配算法，并对这些值进行平均以获得用户之间的总双向匹配值。
至于如何执行算法（将用户分为主动和被动两个表，让主动用户对被动用户执行算法并发送连接请求，将用户添加到池中并让服务器对每个组合执行算法用户，或其他方式），我还没有找到太多关于哪种方法是最佳方法的信息。所以我想这取决于偏好、环境和效率。
我正在尝试考虑一种算法，该算法根据用户定义的某些属性（位置、兴趣等）随机配对用户。许多应用程序和游戏都实现了类似的算法，例如，Tinder（流行的约会移动应用程序）根据用户的位置、性别和年龄随机匹配用户。不过，对于 Tinder，两个用户 "pairing" 之间的关系并不重要。然而，我正在尝试将用户配对以进行某种即时通信和交互。
问题是我不知道从哪里开始。如果轮子已经完成了很多次，或者至少使用另一个实现作为参考，我不想重新发明轮子。不过，我的 Google 搜索并不充分，很可能是因为不知道要搜索什么，例如特定的算法名称。
如何实现加权随机用户匹配算法？最佳匹配算法会更好。我不希望您提供一个代码的所有代码（除非它真的很容易），psuedo-code/theory 或 link 到一个定义良好的库或实现就可以了。
目前我在想什么：
Storing/Connecting
- 将用户分为两个 table：主动和被动。 Active User 通过 Passive table 执行随机 search/pair 算法。向匹配的被动用户发送匹配请求。被动用户接受第一个收到的匹配请求拒绝所有其他。用户匹配进行通信，可以从 table 中删除。如果被动用户在一段时间后不是 "picked"，则可能需要超时，以便它可以成为主动用户。
正在搜索
- 活跃用户根据活跃用户位置的设置范围之类的东西随机选择一定数量的被动用户。考虑到被动用户从他们的位置设置的范围？
加权算法
- 每个用户定义的属性都分配有特定的重要性权重。计算匹配属性的数量（相似或范围内的？）以及它们组合在一起的权重。根据匹配值对用户进行排序。为匹配度最高的被动用户执行 storing/connecting 阶段。如果该用户接受匹配请求，则他们将连接，如果不尝试下一个最高匹配的被动用户。如果没有建立连接，则重新开始整个算法。
如果你想要随机分配，解决方案很简单。如果你想要别的东西，你需要首先说明你有什么标准来决定如何对比赛进行排名；您已经开始了这个过程，但是在您能够清楚地说明 什么 您正在寻找之前，决定 如何 完成它将会浪费很多时间努力。
更具体地说，这里有一个算法：使用任何标准为每个用户分配一个数字分数；按该分数对列表进行排序；匹配每个连续的对。如果这没有产生令人满意的匹配集，请解释它违反了哪些标准（因为我在你的问题描述中找不到任何标准）。
如果相反，您可以为每个可能的配对计算分数，则可以改为这样做：计算所有此类配对分数。重复：取得分最高的那对并将这两个从池中移除。这将问题简化为一个集合操作问题。
这是我目前的情况。
How would I implement a weighted random User matching algorithm?
实现这种算法有多个部分。您需要一种方法来确定用户之间的相似性以及对这种相似性进行评级的方法。此外，您需要一种执行算法的方法，例如：是将所有用户都放入一个池中，然后服务器进行匹配，还是将用户分开，一个执行操作，而另一个等待匹配（如中所述）问题）。
至于确定用户之间的相似度，请查看Collaborative Filtering. This StackExchange问答处理类似的问题。协同过滤通常用于推荐系统（电子商务网站推荐您可能感兴趣的产品），但算法的基础可以应用于匹配用户之间的相似性。
相似度评分取决于您选择使用的特定算法，但加权值是一种方法。在这种情况下，用户包含的每个属性都被分配了一个加权值，表示该值对算法的重要性。权重值越高越重要。您选择的您认为更重要的加权值。该值本身没有意义，但相对于算法很有用。类似地，分配给用户的总计算相似值（应用权重的整个算法的结果值）本身没有意义，但与具有计算值的其他用户相比时很有用。
获得这些值后，您可以简单地对用户进行排序（最高值最相似），然后连接。 但是您如何准确地确定用户之间的相似性？一种方法是查看属性并查看它们是否相等。
例如，假设所有用户都分配了一个布尔值 "likesMusic" 属性。要比较用户 1 和用户 2 之间的此属性，看看它们是否相等：
if(User1.getLikesMusic() == User2.getLikesMusic()){
return 1;
else{
return 0;
}
值0可以在算法中用于不匹配，1可以用于精确匹配。然后可以将 returned 值乘以属性分配的权重值，并添加到所有其他属性计算中。这适用于匹配或不匹配的值，但对于可能匹配的值呢？例如，考虑一个属性 "favFoods"，它是一组用户最喜欢的食物。用户可以分享一些、全部或不分享最喜欢的食物。
return (User1.getFavFoods().intersection(User2.getFavFoods()) / User1.getFavFoods().size());
上面的伪代码通过获取集合之间的相交值的数量除以User1的设置长度来比较User2最喜欢的食物与User1的相似程度。 注意： 必须切换值才能了解用户 1 最喜欢的食物与用户 2 的相似程度。这种方法的好处是它使我们保持在 0 和 1 之间的 return 范围内。这样我们可以保持我们的初始值 1 是完全匹配，0 是不匹配，并且两者之间的所有内容都会有点匹配。
这适用于集合和列表，但是可以在一个范围内的值呢？这就是事情变得有点复杂的地方。例如，考虑每个用户都有一个年龄属性。年龄越接近越好。我们可以取两个用户年龄之间的差异，然后差异越大匹配值越小。但是当差异值变大时匹配值变小的速率是多少？这个值，下降率，必须根据适合您的特定应用程序的任何内容来选择。例如，假设每两年有差异，我们就会将相似度降低 10%。由于 1 将是完全匹配，因此以这种下降率，我们有：
return 1 - ((abs(User1.getAge() - User2.getAge()) / 2) * 0.1);
注意：您必须注意确保从 1 中减去的值不超过 1，因为我们不需要负数。
以上方程式应该涵盖了您会遇到的大多数情况。现在，如果我们知道用户属性的所有 "types"（exact、set 或 range），我们可以使用正确的公式得到值 V，乘以它的权重 W，得到总匹配两个用户之间的值，M:
M = (V1 * W1) + (V2 * W2) + , ... , + (Vn * Wn)
此算法足以进行单向匹配（如果您允许设置属性具有不同的长度，那么 User1 可能与 User2 匹配得很好，但 User2 可能与 User1 匹配得不太好，令人惊讶）。因此，对于双向匹配，您需要调整算法。例如，也许您可以执行从 User1 到 User2 和从 User2 到 User1 的匹配算法，并对这些值进行平均以获得用户之间的总双向匹配值。
至于如何执行算法（将用户分为主动和被动两个表，让主动用户对被动用户执行算法并发送连接请求，将用户添加到池中并让服务器对每个组合执行算法用户，或其他方式），我还没有找到太多关于哪种方法是最佳方法的信息。所以我想这取决于偏好、环境和效率。