4

鉴于学生和导师的可用性，我正在编写一个程序来组建辅导小组。可用性在以字母表示的阻塞时间列表中给出。例如，如果学生将他的空闲时间指定为 [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,utor1] 和 [4, 5, 6,utor2]。这会将每个学生分配到某个小组，最好是说，将 1-5 人放在一个小组中，而将 6 人排除在外。

4

2 回答 2

1

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

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

  2. 找到最“流行”的可用时间，并首先匹配该时间。然后是下一个最受欢迎的，等等。

  3. 找到最不“流行”的可用时间，并首先匹配该时间。然后是下一个最不受欢迎的，等等。

免责声明：我假设您正在从事与学习/爱好/管理便利相关的工作，换句话说，您的项目没有太多的钱。如果我的假设是错误的，我建议你需要更多地研究算法，或者聘请有专业知识的人。

于 2013-01-07T19:18:07.740 回答
1

你可以把这个问题看成一个图问题：通过一组不相交的子图覆盖一个二分图，同时尊重两个分区（学生、组）并最大化一个分区的覆盖（学生）

我正在考虑这个启发式：

  • 从一个空的解决方案开始
  • 虽然有未分配的学生和开放（少于六个成员）组：
    • 按空闲位置的顺序对未分配的学生进行排序
    • 从列表顶部挑选六名学生（从顶部开始阅读列表，直到找到六名学生可以参加的小组）并将他们作为一个小组使用。
    • 如果您不能选择六个学生，请选择尽可能多的学生。
    • 如果你找不到三个学生组成一个小组，但你有两个：
      • 为该组找到第三个学生，该学生当前分配到您可以从（超过三个人）带走的组中，并使用他来填充该组。首选可以从未分配集中重新填充的组
      • 如果您找不到第三个人，请从不同的 3 人小组中选择一个。在该组中递归搜索他的替代者（或放弃）。您可以尝试同时从不同的三人组中移除。
    • 如果你只有一个学生，看看你是否可以让其他小组的另外两个人填补他的任何一个小组。如果需要，递归替换它们或放弃。
    • 如果您有一个学生的所有候选组都已满，请在这些组中的任何一个不能移动到未满组的人中寻找一个人。如果所有替换组都已满，则递归。
    • 如果您无法找到一种方法来调动人员以满足任何未分配的学生，请完成

请注意，这归结为：

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

  • 在已使用和未使用的配对之间交替
  • 从学生开始
  • 在一堂课结束

请注意，这与在二分图中寻找交替路径是同构的，并且可以这样优化。

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

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

更新：我没有注意到你也想指派老师。

在这种情况下，您需要在将学生分配到组时将教师分配到组。这将阻止创建某些组，但是如果没有空闲的老师，您可以从不同的组中选择老师，如果您可以为该组分配不同的老师。同样，它只是在寻找一个交替图，这次是在教师组子图中——让学生四处移动以腾出教师似乎并不可行。

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

于 2013-01-07T19:46:10.803 回答