如何从 2 个列表中确定最佳组合

Question

我正在寻找一种方法来使团体中的人员达到最佳组合。让我概述一下情况。

假设我们有 A、B、C 和 D。此外，我们还有组 1、2、3、4 和 5。两者都是示例，可以更少或更多。每个人都给彼此打分。例如，A 对 B 的评分为 3，C 对 C 的评分为 2，依此类推。每个人还对每个组进行评分。 （假设评分为 0-5）。现在我需要某种算法来将这些人均匀地分布在各个组中，同时让他们尽可能快乐（例如：他们应该在一个高评价的组中，并且有高评价的人）。现在我知道人们不可能处于最佳组中（他们评分为 5 的组），但我需要他们处于整个组的最佳解决方案中。

我认为这是一个困难的问题，如果有人可以指导我了解有关此类问题的更多信息，或者帮助我找到我正在寻找的算法，我会很高兴。

谢谢！

编辑： 我看到了很多很好的答案，但这个问题对我来说太大了，无法正确解决。然而，到目前为止发布的答案为我进一步研究这个主题提供了一个很好的起点。非常感谢！

Answer 1

在确定这是 NP-Hard 问题后，我建议作为启发式解决方案：人工智能工具。

一种可能的方法是最陡爬坡 [SAHC]
首先，我们将定义我们的效用函数（设为u）。它可以是所有群体的总幸福感的总和。

接下来，我们定义我们的“世界”：S 是所有可能分区的组。

对于 S 的每个合法分区 s，我们定义：

next(s)={将一个人转移到不同组的所有可能性}

我们现在要做的就是随机重新启动运行 SAHC：

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.

它是 任何时间算法，这意味着当你给它更多的运行时间时，它会得到更好的结果，最终[在时间无穷大]它会找到最佳结果。

Answer 2

这个问题是 NP 难的：你可以从最大三角形填充（即在图中找到至少 k 个顶点不相交的三角形）减少到有 k 个大小为 3 的组的版本，没有人关心他是哪一组并喜欢每个人的 0 或 1。因此，即使是这种非常特殊的情况也很难。

为了解决这个问题，我会尝试使用 ILP：有二进制变量 g_ik 指示该人我在组 k 中，有限制以确保一个人仅在一个组中，并且组具有适当的大小。此外，二元变量 t_ijk 指示人 i 和 j 一起在组 k 中（由 t_ijk <= 0.5 g_ik + 0.5 g_jk 确保），二元变量 t_ij 指示 i 和 j 一起在任何组中（由 t_ij <= 0.5 g_ik + 0.5 g_jk 确保） ;= sum_k t_ijk)。然后，您可以在这些约束下最大化幸福函数。

这个 ILP 有很多变量，但现代求解器非常好，而且这种方法很容易实现。

Answer 3

这是优化问题的示例。这是一个非常好的
研究了解决问题的好方法。读
集体智慧编程更好地解释了这一点
比我。

基本上，任何类型的优化问题都分为三个部分。

1. 问题解决功能的输入。
2. 问题解决函数输出的解决方案。
3. 一个评分函数，用于评估解决方案的最佳程度
   得分。

现在问题可以描述为寻找产生的解决方案
最高分。为此，您首先需要制定一种格式
表示评分函数可以的可能解决方案
分数。假设6个人（0-5）和3组（0-2），这个python数据结构
会起作用并且是一个可能的解决方案：

output = [
    [0, 1],
    [2, 3],
    [4, 5]
    ]

人员 0 和 1 被放入组 0，人员 2 和 3 被放入组 1 等等
在。为了给这个解决方案评分，我们需要知道输入和规则
计算输出。输入可以由该数据表示
结构：

input = [
    [0, 4, 1, 3, 4, 1,  3, 1, 3],
    [5, 0, 1, 2, 1, 5,  5, 2, 4],
    [4, 1, 0, 1, 3, 2,  1, 1, 1],
    [2, 4, 1, 0, 5, 4,  2, 3, 4],
    [5, 5, 5, 5, 0, 5,  5, 5, 5],
    [1, 2, 1, 4, 3, 0,  4, 5, 1]
    ]

列表中的每个列表代表该人给出的评分。为了
例如，在第一行中，人员 0 给人员 0 评分为 0（您
无法评价自己）、4 给第 1 人、1 给第 2 人、3 给 3、4 给 4 以及
1 到 5 号。然后他或她对组 0-2 进行评分 3、1 和 3
分别。

上面是给定输入的有效解决方案的示例。怎么办
我们得分了吗？问题中没有具体说明，只是
需要“最佳”组合，因此我会任意决定
解决方案的分数是每个人幸福感的总和。每个
一个人的幸福感是通过添加他或她对某个事物的评价来确定的
组中每个人的平均评分，
排除人本身。

这是评分函数：

N_GROUPS = 3
N_PERSONS = 6
def score_solution(input, output):
    tot_score = 0
    for person, ratings in enumerate(input):
        # Check what group the person is a member of.
        for group, members in enumerate(output):
            if person in members:
                # Check what rating person gave the group.
                group_rating = ratings[N_PERSONS + group]

                # Check what rating the person gave the others.
                others = list(members)
                others.remove(person)
                if not others:
                    # protect against zero division
                    person_rating = 0
                else:
                    person_ratings = [ratings[o] for o in others]
                    person_rating = sum(person_ratings) / float(len(person_ratings))
                tot_score += group_rating + person_rating
    return tot_score

对于给定的解决方案，它应该返回 37.0 分。现在什么
我们要做的就是生成有效的输出，同时跟踪哪个输出
直到我们满意为止是最好的：

from random import choice
def gen_solution():
    groups = [[] for x in range(N_GROUPS)]
    for person in range(N_PERSONS):
        choice(groups).append(person)
    return groups

# Generate 10000 solutions
solutions = [gen_solution() for x in range(10000)]
# Score them
solutions = [(score_solution(input, sol), sol) for sol in solutions]
# Sort by score, take the best.
best_score, best_solution = sorted(solutions)[-1]
print 'The best solution is %s with score %.2f' % (best_solution, best_score)

在我的计算机上运行它会产生：

The best solution is [[0, 1], [3, 5], [2, 4]] with score 47.00

显然，您可能认为随机只是一个非常愚蠢的想法
生成解决方案来解决问题，确实如此。有很多
更复杂的方法来生成解决方案，例如模拟
退火或遗传优化。但它们都建立在相同的基础上
框架如上所述。