如何从2列出了确定最佳组合 [英] How to determine best combinations from 2 lists

问题描述

我在寻找一种方法，使人们在群体中最好的组合。让我把有关情况。

I'm looking for a way to make the best possible combination of people in groups. Let me sketch the situation.

假设我们有人员A，B，C和D。此外，我们有组1，2，3，4和5两者都是示例，并且可以是更少或更多。每个人给出的评级，以彼此的人。因此，例如差饷B A 3，C 2，依此类推。每个人也给每一个组。 （说的评级是0-5）。现在，我需要一些排序算法，同时保持他们高兴，因为可以均匀地分布，这些人在群体（如：他们应该是在一个highrated组，highrated人）。现在我知道这是不可能的，为人民群众是最好的组（他们评为5的），但我需要他们是在为整个集团的最佳解决方案。

Say we have persons A, B, C and D. Furthermore we have groups 1, 2, 3, 4 and 5. Both are examples and can be less or more. Each person gives a rating to each other person. So for example A rates B a 3, C a 2, and so on. Each person also rates each group. (Say ratings are 0-5). Now I need some sort of algorithm to distribute these people evenly over the groups while keeping them as happy as possible (as in: They should be in a highrated group, with highrated people). Now I know it's not possible for the people to be in the best group (the one they rated a 5) but I need them to be in the best possible solution for the entire group.

我认为这是一个很难回答的问题，我会很高兴，如果有人可以直接我这个类型的问题，一些更多的信息，或帮助我，我要找的算法中。

I think this is a difficult question, and I would be happy if someone could direct me to some more information about this types of problems, or help me with the algo I'm looking for.

谢谢！

编辑： 我看到很多伟大的答案，但这个问题太大了，我太正确地解决。然而，迄今为止公布的答案给了我一个很好的起点，也是进一步考虑这个问题。非常感谢了！的

推荐答案

建立此之后 NP-硬问题，我建议作为一种启发式的解决方案：人工智能工具

after establishing this is NP-Hard problem, I would suggest as a heuristical solution: Artificial Intelligence tools.

一个可行的方法是最陡的上升爬坡 [SAHC] 首先，我们将定义我们的效用函数（让它成为 U ）。它可以是总幸福在所有组的总和。
接下来，我们定义的世界： S是该组的所有可能的分区的。
对于s的每个合法的划分S，我们定义：
下一个（S）= {动一个人到不同的组中的所有可能性}

A possible approach is steepest ascent hill climbing [SAHC] first, we will define our utility function (let it be u). It can be the sum of total happiness in all groups.
next,we define our 'world': S is the group of all possible partitions.
for each legal partition s of S, we define:
next(s)={all possibilities moving one person to a different group}

现在我们所运行做SAHC随机重新启动：

all we have to do now is run SAHC with random restarts:

1. best<- -INFINITY 
2. while there is more time
3. choose a random partition as starting point, denote it as s.
4. NEXT <- next(s)
5. if max{ U(NEXT) } < u(s): //s is the top of the hill
   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.

有随时算法的，这意味着你给它更多的时间它会得到一个更好的结果运行，并最终[时间为∞，它会找到最佳的结果。

It is anytime algorithm, meaning it will get a better result as you give it more time to run, and eventually [at time infinity] it will find the optimal result.

这篇关于如何从2列出了确定最佳组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！