为最有共同爱好的人安排座位的算法

Question

我的数据是关于人和爱好的，具有多对多关系。每个人至少有一项爱好。

我需要找到一种方法让所有的人都坐在 N 个座位的 table 旁，这样每张 table 上的人之间的共同爱好最多。不需要每张 table 周围的所有人之间至少有一个共同的爱好。此外，表格不一定必须完全填满。

任何想法将不胜感激。

Answer 1

首先，这是一个 NP 难问题 - 例如，任何可以解决您的问题的算法都可以解决 Longest Path加权图的问题如下:

• 每个图的顶点都是一个人
• 图的任何边都可以通过创建新爱好来编码，仅由边的两个顶点/人共享

(对于 NP 完全问题可能有更简单的归约，但我想这就可以了)。

Skiena 会建议 Simulated Annealing ，从任何安排开始，随机选择。诀窍是逐渐降低您接受恶化变化的可能性(因此，一开始您允许它有一定的自由度来避免局部最优，但它会逐渐“冷却”并在某些区域稳定下来并进行小的改进)。您也可以多次运行它并保留最佳解决方案。

您或许可以本着同样的精神手工编写一些不那么复杂的代码。我猜你的问题实例会很小，所以如果你尝试许多它们(并尝试随机优化它们)，你一定会找到好的解决方案。

当然，如果您的问题非常小，您可以枚举所有排列并找到最佳排列。 (如果您有 n 个人，请确保固定某人的位置并且只为 n - 1 个人生成排列)。