问特定分组算法

EN

下面是帮助你入门的3个想法。

1. 贪婪算法。将列表中的第一个学生与列表中的第一个兼容的导师配对。将列表中的第二个学生与列表中的第一个兼容的导师配对。等等。
2. 找到最“流行”的可用小时，并首先匹配到那个小时。然后是下一个最受欢迎的小时，依此类推。
3. 找到最不“受欢迎”的可用小时，并首先匹配到那个小时。然后是最不受欢迎的，等等，

免责声明:我假设你正在做一些关于学习/爱好/管理便利的事情，换句话说，你的项目没有多少钱处于危险之中。如果我的假设是错的，我会建议你学习更多关于算法的知识，或者聘请有专业知识的人。

您可以将此问题视为一个图问题:通过一组不相交的子图覆盖二部图，同时尊重两个分区(学生，组)并最大化一个分区(学生)的覆盖。

我在想这个启发式的方法：

• 从一个空的solution
• 开始，同时有未分配的学生和开放的(少于六个成员)组：
  • 按可用插槽的顺序对未分配的学生进行排序
  • 从列表顶部选择六名学生(从顶部开始阅读列表，直到找到六名学生可以参加的组)并将他们作为一个组使用。

  H19如果您无法选择六名学生，请尽可能多地挑选。H210H111如果找不到组成一个组的三名学生，但是你有两个：

  • 为这个组找到第三个学生，这个学生当前被分配到一个你可以选择的组中(超过三个人)，然后用他来填充这个组。首选可以从未分配的set
  • 中重新填充的组如果找不到第三个人，请从不同的3人组中选择一个。在那个组中反复寻找他的继任者(或者放弃)。您可以尝试从parallel.

中的不同三人组中移除

​

- If you only have one student, see if you can fill any of his groups by two other people from other groups. If needed, replace them recursively or give up.
- If you have a student whose all candidate groups are already full, look for a person in any of these group that can't be moved to a non-full group. If all replacement groups are already full, recurse.
- If you can't find a way to shift people around to satisfy any unassigned student, finish

​

请注意，这可以归结为：

快速找到一个能让大多数人满意的解决方案(你可以就此打住)。然后，尝试通过找到一系列配对来插入学生：

在

• 中，学生在使用和未使用的班级之间交替结束于

班级

请注意，这与在二部图中寻找交替路径同构，并且可以进行优化。

请注意，这可能仍然无法找到最佳解决方案，因为它永远不会替换单个组中的一个以上的人来满足一个人。

上面的伪代码指示在每个步骤中对学生列表进行排序。相反，您可以跟踪对此列表的更改，并在进行更新时更新排序顺序。

更新:我没有注意到你也想分配老师。

在这种情况下，当您将学生分配到某个组时，需要将教师分配给该组。这将阻止创建某些组，但如果没有空闲教师，如果您可以将不同的教师分配到不同的组中，则可以从不同的组中接收教师。再说一次，它只是在寻找一个交替的图，这一次是在教师组子图中-把学生拖来拖去以释放教师似乎是不可行的。

您想要覆盖的整个图现在有三个分区:学生、教师、组。老师和学生不互动，所以有两个层次:学生-小组，小组-教师。这两个层是独立的，除非它们必须覆盖相同的组集合。