algorithm - 有约束的座位算法

Question

我正在尝试制作一个程序，在 5 天内，每天都会制作一个新的座位安排。有一个必须遵守的约束：

• 人们以 4 人一组就座，并且在 5 天内不能与另一个人在同一组中超过一次。总共大约有30-35人。

我已经做了一些研究，似乎这是一个约束满足问题，但我想知道这种问题是否有更具体的名称，或者要使用的具体算法。

此外，是否可以确定在给定样本量下是否能够满足此约束条件？我是图论领域的新手，不知道在这种情况下哪些算法是可行的。

标签： algorithmmathgraphgraph-algorithm

Answer 1

下面的链接是社会 Golpher 问题的一个很好的起点。它包含更简单情况的解决方案（包括一些带有 4 表的情况），并提供了一些更高级论文的指针：http: //www.mathpuzzle.com/MAA/54-Golf%20Tournaments/mathgames_08_14_07.html