用几个标准将一个班级分成组的可能性

Question

我必须将一个50人的班级分成10个不同的讨论小组，每个小组5人。理论上，有1.35363x10^37种可能的方法，如果已经确定组将由5个组成，则这只是{50!}/{(5!^10)*10!)}的结果。

但是，每个小组都将由一名主持人领导。这大大减少了可能的组合数量，因为每个辅导员在5个可能的领域中有一个专业领域，应该尽可能地与学生所写的主题相匹配。如果有3名辅导员具有能力A，3人具有能力B，2人具有能力C，1人具有能力D，1人具有能力E，15名学生被分配到A，15名学生被分配到B，10名学生被分配到C，5名学生被分配到D，5名学生被分配到E，则可能的组合数量降至252 505。

但学生和辅导者都一直在倡导使用更多的标准，而不仅仅是专注于专业领域。例如，想要加入一群互相认识的学生，或者与一位对特定研究方法有特殊知识的促进者在一起。

我试图说明我的直觉推理，它告诉我，如果目标是一个完全有效的解决方案，每个新的标准都会增加任务的复杂性/不可能性。但我不能让我的大脑以令人满意的方式分析表达这一点。

我的推理是否正确，即添加标准将减少遵循包含-排除原则可以丢弃的可能性的数量，从而使任务更加复杂，添加可能的组合？我还认为，如果标准不兼容(例如，如果相互认识的学生正在撰写关于不同主题的文章，并且没有足够的有能力的主持人)，某些限制将变得不可行。

Answer 1

您需要区分计算复杂性和人类复杂性。添加约束几乎会自动增加问题的人类复杂性，因为这意味着有更多的东西需要你考虑。但是--计算复杂度增加并不是真的。至少有时它会减少。

例如，假设您有一个包含200个项目的集合，您希望确定其中是否存在满足某些约束的子集。根据约束，可能没有可行的方法来做到这一点。毕竟，2^200对于暴力破解来说太大了。现在添加子集需要恰好有3个元素的约束。现在，突然之间可以使用暴力(只需遍历所有1,313,400个3元素子集，直到找到解决方案或确定不存在任何解决方案)。这足以表明，添加约束总是会使问题本质上更加困难，这并不是真的。在离散情况下，一个新的约束可以以一种可以利用的方式减少搜索空间的大小。在连续情况下，它可以减少自由度，从而降低问题的维数。这并不是说它总是让它变得更容易。可能作为经验法则，额外的约束往往会使问题变得更加困难。

你的实际问题没有清楚地表达出来，无法给出具体的建议。一种可能性(以及处理某种无关约束激增的一种方法)是将约束分为需要满足的硬约束和仅需要但不是严格需要的软约束。将其转化为优化问题:在满足硬约束的条件下，找到使满足的软约束数量最大化的解。也许你可以把它描述成一个integer programming问题，希望能找到一个确切的解决方案。或者，如果很容易生成满足硬约束的解决方案，并且很容易改变一个这样的解决方案来获得另一个解决方案(例如，交换不同组中的两个学生)，那么evolutionary algorithm将是一个合理的启发式方法。