根据偏好的相似性将两个元素（人）匹配在一起

Question

我正在规划一个网站，该网站将定期将两个用户匹配在一起。

池中的每个人都会有几个在匹配过程中使用的偏好，例如他们喜欢什么类型的音乐以及一周中的哪几天可以听。出于本项目的目的，如果偏好特定，我想分配更高的权重/匹配优先级；也就是说，两个只喜欢“科幻小说”的人比简单地将两个勾选“以上所有”的人放在一起更好。我认为标准的贪婪匹配算法可能会起作用，但是有没有更有效的算法？

Answer 1

事情没那么简单，您需要创建一个实用函数，让您知道哪个更匹配。例如，哪个会更好：

(1) 一对非常匹配，另一对则非常差。

(2) 两对，平均匹配。

我建议使用一些经过充分验证的人工智能工具来解决这个问题。

首先，一些定义：

• P={所有人}
• S={匹配所有人的所有可能性}
• 让u:PxP->R< /code> 是一对的评分函数：u(p1,p2)=their
匹配得分 [当然取决于您的数据]
• 让 U:S->R 为整个匹配的评分函数：U(aMatch)
= Sigma(u(p1,p2)) 对于每对配对。
• 设 next:S->2^S 为： next(S)={所有可能的匹配
与 S 不同，仅交换两个人}

现在，根据上述定义，您可以使用 最陡爬山或遗传算法，它们是经过验证的人工智能工具，用于获取一个好的结果。

最速爬坡[SAHC]很简单，从随机匹配开始，做一些小的改变，直到达到无法进行局部改进的程度。该点是局部最大值，并且是最佳解决方案的候选点。使用不同的初始状态重新启动该进程。

伪代码：

1. best<- -INFINITY
2. while there is more time
3. choose a random matching
4. NEXT <- next(s)
5. if max{ U(v) | for each v in NEXT} < U(s): //s is a local maximum
   5.1. if u(s) > best: best <- u(s) //if s is better then the previous result - store it.
   5.2. go to 2. //restart the hill climbing from a different random point.
6. else:
   6.1. s <- max { NEXT }
   6.2. goto 4.
7. return best //when out of time, return the best solution found so far.

注1：该算法是任何时间，这意味着你给它更多的时间，它会得到更好的结果。如果你的时间->无穷大，算法最终会找到最优解。

注2：效用函数U只是一个建议，您也可以使用max{u(p1,p2) |对于匹配中的每一对}，或您认为合适的任何其他实用函数。

编辑：

即使是更简单的问题，即：两个人可以简单地“匹配”或“不匹配”[u(p1,p2)=0 或 u(p1,p2)= 1]实际上是最大匹配问题，是NP-Hard，因此这个问题没有已知的多项式解决方案，并且有一个启发式的解决方案可能应该使用上面建议的解决方案。

请注意，如果您的图表是二分 [即您无法将男性与男性/女性与女]，这个问题可以在多项式时间内解决。详细信息：二分图中的匹配