特定分组算法

Question

我正在编写一个程序，根据学生和导师的可用性来组成辅导小组。可用性在由字母表示的阻塞时间列表中给出。例如，如果一个学生将他的可用性表示为[A，C，D]，则他在一天的第一、三和四个小时内可用。如何编写一个函数，它接受学生列表和导师列表，并给出最大化放置在小组中的学生列表？我使用Java编程，但我更关心算法而不是代码本身。一些细节如下：

小组必须包含3-6名学生和1名导师。

学生只能在一个小组中。

必须最大化满意（放置在小组中）的学生数量。 例如，假设我们有1-6名学生和两名导师，两名导师都在A和B时段可用。学生们在1：A，2：A，3：A，4：AB，5：AB，6：B可用。该算法应返回两个小组：[1, 2, 3, 导师1]和[4, 5, 6, 导师2]。这样可以将每个学生分配到某个小组，而不是将1-5放在一个小组中并让6离开，这是更好的选择。

- John Claxton

---

我想要一个功能...好的，但是没有免费的帮助：你尝试过什么？现有的代码是什么？等等。 - fge

我真的不知道从哪里开始，因为没有任何有趣的现有代码，因为我没有算法可以基于它。 - John Claxton

令人惊讶的是（或许也不是...），这个页面右侧大部分相关问题都涉及到了这个确切的问题。或许可以在那里查找一下。 - Matt Dodge

我的唯一担忧是填充一个组的最大请求数，任何一个组的大小都必须在3-6之间。一种启发式方法可能会很好用。请求数不会很多（最多约100个），因此即使是NP解决方案也可能适用。 - John Claxton

@JohnClaxton 所以你需要最大化的只是拥有小组的学生人数 - 每个小组的大小是一个硬性限制吗？ - John Dvorak

Answer 1

以下是三个帮助您入门的想法。

1. 贪心算法。将列表中的第一个学生与列表中的第一个兼容导师匹配。将列表中的第二个学生与列表中的第一个兼容导师匹配，以此类推。

2. 找到最受欢迎的可用时间，并首先匹配该时间。然后是下一个最受欢迎的时间，以此类推。

3. 找到最不受欢迎的可用时间，并首先匹配该时间。然后是下一个最不受欢迎的时间，以此类推。

免责声明：我假设您正在处理类似于学习/爱好/行政便利等方面的项目，换句话说，您的项目没有太多的经济利益。如果我的假设是错误的，我建议您需要更多地研究算法，或者雇用一些有专业知识的人。

- Aaron Kurtzhals

---

这很容易导致大量未填充的组。 - John Dvorak

谢谢你的想法！这个项目没有任何资金投入，只是我在考虑我的工作（我是一名导师）的一个副业项目。 - John Claxton

Answer 2

您可以将此问题视为图形问题：通过一组不相交的子图覆盖二分图，同时尊重两个分区（学生、小组），并最大化一个分区（学生）的覆盖。

我正在考虑以下启发式方法：

• 从一个空的解决方案开始
• 当有未分配的学生和开放（少于六名成员）的小组时：
  • 按照空闲时间段的顺序对未分配的学生进行排序
  • 从列表的前面选择六名学生（从上往下读列表，直到找到可以参加六人小组的组），并将他们用作小组。
  • 如果无法选择六名学生，则选择尽可能多的人数。
  • 如果无法找到三个可以组成小组的学生，但你有两个：
    • 为该小组找到一个第三个学生，该学生目前已被分配到一个你可以从中取走的小组（超过三人），并使用他来填充该小组。优先考虑可以从未分配集合中重新填充的小组
    • 如果找不到第三个人，请从不同的三人小组中选一个。在该组中递归搜索其替代品（或放弃）。您可以同时尝试从不同的三人小组中删除。
  • 如果只有一个学生，请查看是否可以通过其他小组的两个人来填补他的小组。如有必要，递归替换它们或放弃。
  • 如果您有一个所有候选小组都已满的学生，请查找任何一个无法移动到非满小组的人。如果所有替换小组都已满，请递归。
  • 如果找不到任何方法来调整人员以满足任何未分配的学生，请完成

请注意，这归结为以下内容：

快速找到满足大多数人的解决方案（您可以在此停止）。然后尝试通过找到一系列配对来插入学生，其中：

- 在使用和未使用的配对之间交替 - 从学生开始 - 结束于班级

请注意，这等同于在二分图中查找交替路径，并且可以进行优化。

请注意，这仍可能无法找到最佳解决方案，因为它从不更换单个组中的超过一个人以满足一个人。

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

---

更新：我没有注意到您也想分配老师。

在这种情况下，当您为组分配学生时，需要将老师分配给该组。这将防止创建某些组，但如果没有空闲的老师，您可以从不同的组中选择老师，如果您可以为该组分配不同的老师。同样，这只是在老师-组子图中搜索交替图，将学生调整以释放老师似乎不可行。

现在，您要覆盖的整个图形具有三个分区：学生、教师、组。教师和学生不互动，因此有两个层：学生-组、组-教师。这两个层是独立的，除了它们必须覆盖相同的组集合。

- John Dvorak