根据偏好的相似性匹配两个元素（人物）

Question

我正处于网站的计划阶段，它会定期将两个用户相互匹配。

池中的每个人将有多个在匹配过程中使用的偏好，例如，他们喜欢什么类型的音乐，以及他们每周有哪些日子。为了这个项目的目的，如果偏好是特定的，我想分配更高的权重/匹配优先权;即两个只喜欢“科幻小说”的人比仅仅将两个检查“上述所有”的人放在一起更好。我在想，一个标准的贪婪匹配算法可能会起作用，但是那里有更有效的算法吗？

Answer 1

事情并非如此简单，您需要创建一个实用程序功能，让您知道哪个更符合要求。例如，哪个更好：
（1）一对配对非常好，另一个配对非常差。
（2）两对，平均匹配。

我建议使用一些经过验证的artificial intelligence工具来解决这个问题。
第一，一些定义：

• P={all persons}
• S={all possibilities to match all people}
• 让u:PxP->R是一对打分函数：u(p1,p2)=their score as a match [取决于你的课程资料]
• 让U:S->R是一个打分函数整个匹配：U(aMatch) = Sigma(u(p1,p2)) for each paired couple。
• 让next:S->2^S是：现在next(S)={all possible matchings which are different from S by swapping two people only}

，上述定义可以使用steepest ascent hill climbing或genethic algorithm，这被证明是人工智能工具，得到一个好的结果。

最陡峭的上升山登山 [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：，该算法anytime，这意味着它会取得更好的成绩，你给它更多的时间。如果你的时间 - >无穷大，算法将最终找到最佳解决方案。
注2：效用函数U只是一个建议，你也可以使用max{u(p1,p2) | for each pair in the match}，或者你认为合适的其他效用函数。

编辑：
即使是简单的问题，那就是：两个人可以简单地“匹配”或“不匹配” [u(p1,p2)=0或u(p1,p2)=1]实际上是maximal matching problem，这是NP-Hard，因此没有已知的多项式解决这个问题的方法，并且可能会使用上面提出的启发式解决方案。
请注意，如果您的图形是bipartite [即你不能与男性/女性匹配男性]，这个问题可以在多项式时间内解决。更多信息：matching in bipartite graphs