将x人分成n个不同大小的房间的算法

Question

对于一个项目，我必须设计一种算法，让一群人根据他们的喜好进入酒店房间。我在 Python 中创建了一个字典，其中有一个人作为键，作为一个值，列出了他们希望与之共处的所有人。

有不同类型的房间，可容纳 2-10 人。有多少房间是什么类型的由程序的用户指定。

我尝试通过尝试所有房间组合然后根据居民的偏好给每个房间打分并寻找最高分来暴力解决这个问题。这适用于小团体规模，但有 200 人的团体会给 200 人！我可怜的电脑在我有生之年无法计算出的组合。

我想知道是否有我无法找到的算法来解决我的问题。

提前致谢！泰斯

Answer 1

您可以将字典想象成图表。然后你可以创建一个邻接矩阵。

例如，假设您有一组 4 人，A、B、C 和 D。

A：想和B、C在一起
B：想和A在一起
C：想和D在一起
D：想和A、C在一起

你的矩阵看起来像这样：

//    A  B  C  D
// A  0  1  1  0
// B  1  0  0  0
// C  0  0  0  1
// D  1  0  1  0

我们称此矩阵为 M。然后您可以计算转置（我们称其为 MT）并将 M 添加到 MT。你会得到这样的东西。

//    A  B  C  D
// A  0  2  1  1
// B  2  0  0  0
// C  1  0  0  2
// D  1  0  2  0

然后根据其值的总和对行（或列，因为它是对称的，所以无关紧要）进行排序。

//    A  B  C  D
// A  0  2  1  1
// C  1  0  0  2
// D  1  0  2  0
// B  2  0  0  0

对列执行相同的操作

//    A  C  D  B
// A  0  1  1  2
// C  1  0  2  0
// D  1  2  0  0
// B  2  0  0  0

根据第一行中的最大值开始填充您的房间，并通过移除分配房间的人来减少矩阵。您应该先选择最大的房间。

例如，如果我们有一个可以容纳 2 人的房间，您可以将 B 和 A 分配给它，因为第一行中的最大值是 2，它对应于 B。

减少的矩阵将是：

//    C  D
// C  0  2
// D  2  0

循环直到全部完成。

Answer 2

您已经描述了一个贪婪的解决方案。因此，我建议使用模拟退火解决方案。

为此，您首先将每个人随机分配到房间。现在您开始考虑随机交换人员。您总是接受可以提高分数的交换，但也有可能接受不好的交换。如果交换真的很糟糕，接受不良交换的机会就会下降，而且会随着时间的推移而下降。在你尝试足够多之后，无论你有什么可能都很好。

之所以称为“模拟退火”，是因为它模拟了缓慢冷却的物质形成well-organized crystal结构的过程。因此，您通常使用的参数称为 T 温度。标准函数是：

def maybe_swap(assignment, x, y, T):
    score_now = score(assignment)
    swapped = swap(assignment, x, y)
    score_swapped = score(swapped)
    if random.random() < math.exp( (score_swapped - score_now) / T ):
        return swapped
    else:
        return assignment

然后你只需要考虑要做多少工作。像这样：

for count_down in range(400, -1, -1):
    for i in range(n^2):
        x = floor(random.random(n))
        y = floor(random.random(n))
        if x != y:
            assignment = maybe_swap(assignment, x, y, count_down / 100.0)

（你应该尝试一下参数。）

将x人分成n个不同大小的房间的算法

algorithm for dividing x amount of people into n rooms of different sizes

algorithm

language-agnostic