辅导事件的算法开发

Question

我正在尝试创建一种算法，在每一轮辅导中，将被辅导者与不同的1-4个导师组配对。

该算法将接受3个输入：

• 被辅导者的数量--介于1到35之间的整数。
• 导师人数--总是大于或等于被辅导者的人数，但不超过35人。
• 要执行的辅导次数

给定这三种输入，该算法将使每个被辅导者与1-4个导师匹配，但有以下限制：

• 如果有可能通过给定的输入来做到这一点，那么被辅导者绝不能与同一个导师配对不止一次。
• 如果在给定的输入下可以这样做，则导师绝不能与另一位导师同属同一组导师。

注意:该算法不需要向被辅导者随机分配导师。代码可以在每次使用相同的输入集运行时给出相同的输出。

下面是一个成功算法的输出示例，包括2轮、4次被辅导者和11次导师：

| Round | Mentee | 1 | 2 | | 1 | 1, 2, 3| 4, 7, 10| | 2 | 4, 5, 6| 1, 8, 11| | 3 | 7, 8, 9| 2, 5 | | 4 |10, 11 | 3, 6, 9 |

请告诉我，如果你有任何问题，或如果我要求的是事实上是不可能的。非常感谢您的时间和帮助，并祝您愉快的一天。

真诚的，泰罗瓦

Answer 1

有趣的问题！

不幸的是，它不太可能有一个快速的解，因为它与一些长期存在的组合问题有关，这些问题没有我所知道的有效的建设性解。

您可以从两个方面考虑这个问题：(1)确定每个回合的导师组，然后(2)将这些组与被辅导者配对。

将n称为指导者的数量，将m <= n称为被辅导者的数量。并假设m均分n。(如果不是，你只需添加m - (n mod m)的“假”导师，即空椅子。)

然后，仅仅第一部分(1)计算出每一轮中的指导者组，就相当于找到一个S(2, n/m, n) Steiner三重系统 (有足够多的回合)。对这些组合对象进行了大量的研究，并发表了一些算法，但据我所知，它们中没有一个是快速的，甚至是多项式时间。

然而，对于合理的参数大小，您可以希望用一种贪婪的算法方法生成指导者组:对于每个导师，保持跟踪(在set数据结构中)，而导师已经与其组成小组。对于每一轮，开始建立一组尚未组成小组的导师，然后将这些小组成员添加到每个列表中。然而，如果这一方法失败，你可能不得不求助于一种蛮力的方法来找到这些群体。

一旦您有了导师组，在每一轮中将他们与被辅导者配对成为二部完全匹配问题的一个实例，其中有一些合理有效的解决方案，包括Hopcroft-Karp算法。同样，您希望跟踪每个被辅导者所见过的导师，并在每一轮中更新这些内容。

因此，总的来说，我建议的做法是：

1. 为每个导师和每个被辅导者创建一个set，最初是空的。
2. 贪婪地选择m/n组的n导师，每个小组以前没有在同一组中。如果你被“卡住”了，那就对所有可能的分组进行暴力搜索，直到你找到合适的。
3. 创建一个二分图，每个指导者有一个顶点，在当前一轮中，每个指导者组有一个顶点，如果小组中没有一个导师看到这个指导者，则创建他们之间的一个边。
4. 在该图表中找到一个最大匹配--这是当前一轮中导师与被辅导者的配对。
5. 对剩下的回合重复第2-4步.

您可能还想看看柯克曼的女学生问题，它与您所要求的内容密切相关，并且很好地简单地说明了为什么通常很难解决这个问题。