匹配两个要素（人员）一起的基础上preferences相似 [英] Matching two elements (people) together based on similarity of preferences

问题描述

我在一个网站上，将匹配两个用户的计划阶段一起定期。

I'm in the planning stages of a website that will match two users together periodically.

在池中的每个人都会有几个preferences那些在匹配过程中使用，例如什么样的音乐风格，他们喜欢和他们所提供的星期几。对于这个项目的目的，我想赋予更高的权重/匹配优先，如果preferences具体;即两个人谁只喜欢'科幻'是不是简单地放在一起的两个人谁勾掉以上所有的更好的匹配。我在想，一个标准的贪婪匹配算法可能会工作，但没有任何算法，在那里，更有效？

Each person in the pool will have several preferences that are used in the matching process, e.g. what genres of music they like and which days of the week they are available. For the purposes of this project, I'd like to assign higher weight/match priority if the preferences are specific; i.e. two people who ONLY like 'science fiction' are a better match than simply putting together two people who checked off 'all of the above'. I'm thinking that a standard greedy matching algorithm would probably work, but is there any algorithm out there that is more efficient?

推荐答案

这不是那么简单，你需要创建一个实用的功能，可以让你知道哪个是更好的匹配。例如，这将是更好的：
（1）一对具有优良的匹配，另一个是非常差的。
（2）的两个双，平均匹配

It is not that simple, you need to create a utility function that lets you know which is better matching. For example, which will be better:
(1) one pair with excellent match, the other is terribly poor.
(2) two pairs, with an average match.

我建议使用一些很好的证明人工智能工具针对此问题。
第一，定义如下：

I suggest using some well proven artificial intelligence tools for this problem.
first, some definitions:

• P = {所有人}
• S = {所有的可能性，以匹配所有的人}
• 让 U：PxP-＆GT; R 是一个计分函数的对： U（P1，P2）=他们 得分为匹配 [取决于你的课程内容]
• 让 U：S-＆GT; R 是一个打分函数整个匹配： U（aMatch） =西格玛（U（P1，P2）），每个配对的情侣。
• 让下一：S-→2，2S 是：下一个（S）= {所有可能的匹配这是 通过交换两个人不同仅S}

• P={all persons}
• S={all possibilities to match all people}
• let u:PxP->R be a scoring function for a pair: u(p1,p2)=their score as a match [depends on your data of course]
• let U:S->R be a scoring function for the whole matching: U(aMatch) = Sigma(u(p1,p2)) for each paired couple.
• let next:S->2^S be: next(S)={all possible matchings which are different from S by swapping two people only}

现在，上述定义可以使用最陡的上升爬坡或< A HREF =htt​​p://en.wikipedia.org/wiki/Genetic_algorithm相对=nofollow> genethic算法，这被证明是人工智能工具，得到一个好的结果。

Now, with the above definition you can use steepest ascent hill climbing or a genethic algorithm, which are proven Artificial Intelligence tools for getting a good result.

最速上升爬山 [SAHC]很简单，首先随机匹配，并进行了小改动，直到你达到一个地步，你不能让一个局部改进。这点是局部最大值，和一个候选是最好的解决办法。重新启动具有不同的初始状态的过程。
伪code：

Steepest Ascent Hill Climbing [SAHC] is simple, start with as random matching, and make a small change, until you reach a point where you cannot make a local improvement. This point is a local maximum, and a candidate to be the best solution. restart the process with a different initial state.
pseudo code:

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 只是一个建议，你也可以使用最大值{U（P1， P2）|每对在比赛中} ，或任何其他的效用函数你找到适合。

Note1: that this algorithm is anytime, which means it will get better results as you give it more time. and if your time->infinity, the algorithm will eventually find the optimal solution.
Note2: the utility function U is just a suggestion, you could also use max{u(p1,p2) | for each pair in the match}, or any other utility function you find fits.

编辑：
即使是简单的问题，那就是：两个人可以简单地匹配或不匹配[ U（P1，P2）= 0 或 U（P1，P2）= 1 ]实际上是的最大匹配问题，这是 NP难，因而存在没有已知的对这一问题的多项式溶液和启发式溶液，如上面建议或许应该使用。
需要注意的是，如果你的图是二部 [即你所不能比拟的男性与男性/女性与女性]，这个问题是solveable在多项式时间。更多信息：<一href="http://en.wikipedia.org/wiki/Matching_%28graph_theory%29#Maximum_matchings_in_bipartite_graphs"相对=nofollow>在二分图匹配

Even the simpler problem, which is: two people can simply "match" or "not match" [u(p1,p2)=0 or u(p1,p2)=1] is actually the maximal matching problem, which is NP-Hard, thus there is no known polynomial solution for this problem, and a heuristical solution, such as suggested above should probably be used.
Note that if your graph is bipartite [i.e. you cannot match male with male/female with female], this problem is solveable in polynomial time. More info: matching in bipartite graphs

这篇关于匹配两个要素（人员）一起的基础上preferences相似的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！