将x个人的数量分成n个不同大小的房间的算法
对于一个项目，我必须设计一个算法，将适合一组人进入酒店房间，根据他们的喜好。我用Python创建了一本字典，字典中有一个人作为密钥，并作为一个值列出了所有他们想要与之在一起的人的列表。
有不同类型的房间，可以容纳2-10人。程序的用户指定了多少个类型的房间。
我试图通过尝试所有的房间组合来强行解决这个问题，然后根据居民的喜好给每个房间一个分数，并寻找最大的分数。这是很好的工作小组的小规模，但有一组200将给予200！我可怜的计算机在我的有生之年无法计算的组合。
我想知道是否有一种算法是我无法找到的解决我的问题。
提前感谢！蒂杰斯
回答 2
Stack Overflow用户
发布于 2020-09-23 18:24:39
你能做的就是把你的字典想象成一个图表。然后你可以创建一个邻接矩阵。
例如，假设你有一组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开始填充您的房间，从第一行开始，基于该行中的最大值，并通过删除分配给房间的人员来减少矩阵。你应该先选择最大的房间。
例如，如果我们有一个可以有两个人的房间，你会给它分配人B和A，因为第一行的最大值是2，它对应于人B。
然后，缩减的矩阵如下：
// C D
// C 0 2
// D 2 0你一直循环直到一切都完成。
Stack Overflow用户
发布于 2020-09-23 21:47:25
你已经有了一个贪婪的解决方案。因此，我将建议一个模拟退火方案。
为此，你首先把每个人都随机分配到房间。现在你开始考虑随意交换人了。你总是接受能提高你分数的掉期，但是有机会接受一个坏的交换。如果掉期真的很糟糕的话，接受坏掉期的机会就会减少，而且也会随着时间的推移而下降。在你做了足够的实验之后，你所拥有的一切可能都是非常好的。
它被称为“模拟退火”，因为它是对缓慢冷却的物质形成组织良好的晶体结构的过程的模拟。所以你通常使用的参数叫做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)(您应该使用参数。)
https://stackoverflow.com/questions/64032465
复制相似问题
腾讯云开发者
