algorithm - 时间 block 分配算法，私教->学生关系，最大化上课次数

Question

情况如下。

我是一名有几十名学生的私有(private)教师。我的时间有一些限制(例如我不能在周五下午上课)，学生的时间也有很多限制。基于此，我正在尝试以一种我可以尽可能多地进行私有(private)类(class)并同时优化我的时间的方式来制定我的议程。理想情况下，它甚至会考虑到我与学生的距离(他们中的一些人在另一个城市)。类(class)也有可变的持续时间。理想情况下，我希望能够设置我可以教的时间(一周中的每一天)和每个学生可以类的时间(一周中的每一天)，他希望类的时间和频率(即每周 2 次)。

我相信已经有一个算法，但我找不到这个问题的名称。我相信这不是稳定婚姻的情况，也不是这个情况:Teacher time schedule algorithm

如果有人能指出我可以研究的算法或 Material ，以便在不存在的情况下尝试详细说明，我将不胜感激。

非常感谢，祝您有愉快的一天!

Answer 1

这个问题似乎太复杂了，无法应用一些很好的多项式时间解决方案。例如，如果您不关心学生所在的位置、不关心时间碎片等，您可以使用某种最大流算法来解决它。但是，这可能不会产生您最满意的时间表。如果你想模拟真实世界的情况，假设你有少量学生(例如 < 10)并且你有少量时间(例如 < 40)，你应该做 backtracking ，(即蛮力)以尝试不同的分配并优化您拥有的任何约束。由于运行时间是指数级的，您最终可能不得不做一些 Branch and Bound优化。

无论采用何种方法，您都必须以更具体的方式简化或指定问题。例如，如果您决定总是在 2 点、4 点、6 点或 8 点开始上课，那么解决问题就会容易得多。您还需要定义一个公式来给出解决方案的质量(例如，总教学时间减去总旅行时间)。像这样对问题建模并编写解决方案通常很有趣，尤其是如果您是编程或算法爱好者。