所以我正在编写一种算法，当给定一组来自不同地方的人时，它会根据一些参数将他们分成三组:
- 一组中没有两个人来自同一个地方
- 一组中没有两个人以前见过面
- 小组中的每个人都可以在同一天见面
- 18 岁以下的人不超过 1 人
我的数据结构中有一个变量用于上述所有必需的先决条件。我想知道是否有解决这个问题的好方法？目前我正在使用 Gale-Shapely 算法的变体(稳定婚姻问题的解决方案)。这个解决方案效果相对较好，但更常见的是，它需要我进入并对最终组进行一些小的调整。
有人有什么想法/建议吗？
在此先感谢您的帮助。
最佳答案
这是一个 graph partitioning问题，因此它几乎肯定是 NP-Hard(当你只有一个约束时，那么问题可以在多项式时间内解决 - 这类似于稳定婚姻问题 - 但是当你有多个约束时，那么复杂性向上射击)。解决这些问题的一个好方法是应用启发式算法(您正在使用 Gale-Shapely 算法)，然后解决与本地回溯搜索的任何冲突(听起来您目前正在手动执行) .我的建议是保持当前的启发式算法，如果它看起来对你很有效，并添加一个自动本地回溯算法来解决由启发式算法引起的任何冲突(例如，如果你有一个小组，其中有两个人未满 18 岁，然后将这些人中的一个与 18 岁以上且不违反其他三个约束的人交换；如果这不可能，则选择 18 岁以上且违反最少约束的人，然后交换为了满足现在违反的约束，从组中排除其他人；在 N 次失败的迭代之后，算法举手并要求人工干预)
关于algorithm - 具有需求的分组算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/26208963/