大学课程的有效排课

Question

我目前正在一个网站上工作，该网站将允许我所在大学的学生根据他们想修的课程自动生成有效的课程表。

在网站上工作之前，我决定解决如何有效地安排课程的问题。

一些澄清：

1. 我们大学的每门课程 大学）由一个或多个部分组成。比如说， 微积分I目前有4个部分可用。这意味着，取决于课程的节数，以及课程是否有实验室，这会极大地影响排课过程。

2. 我们大学的课程用学科缩写和课程代码的组合来表示。在微积分I中：数学1110。

3. CRN是一个区段特有的代码。

4. 我就读的大学不是男女混合的，意思是男女在（几乎）不同的校园学习。我几乎是说校园被分成了两部分。

5. datetimes和timeranges dict旨在减少对datetime.datetime.strTime（）的调用，这是一个真正的瓶颈。

我的第一次尝试是算法不断循环，直到找到30个调度。通过从一个输入的课程中随机选择一个部分，然后尝试从其余课程中放置部分来构建有效的计划，创建计划。如果不是所有课程都符合时间表，即存在冲突，则取消时间表并继续循环。

显然，上述解决方案存在缺陷。算法运行时间太长，而且过于依赖随机性。

第二种算法与旧算法完全相反。首先，它使用itertools.product（）生成所有可能的计划组合的集合。然后，它遍历计划，删除所有无效的。为了确保分类的部分，计划组合在被验证之前被洗牌（random.shuffle（））。同样，也有一些随机性。

经过一点优化，我能够让调度程序在1秒内运行，平均调度由5个课程组成。那很好，但一旦你开始增加更多的课程，问题就开始了。

给你一个想法，当我提供一组特定的输入时，可能的组合量非常大，以至于itertools.product（）不会在合理的时间内终止，并且在这个过程中会消耗1GB的RAM。

显然，如果我想让它成为一个服务，我需要一个更快更高效的算法。两个已经出现在网上和IRC：动态规划和遗传算法。

动态规划不能应用于这个问题，因为如果我正确理解这个概念，它涉及到将问题分解成更小的部分，单独解决这些部分，然后将这些部分的解决方案组合在一起形成一个完整的解决方案。据我所见，这不适用于这里。

至于遗传算法，我不太了解它们，甚至无法理解如何在这种情况下应用它们。我也知道，对于一个非常大的问题空间，遗传算法会更有效，而这不是的大。

我有什么选择？有没有一种相对可以理解的方法来解决这个问题？或者我应该坚持我所拥有的并希望下学期没有多少人决定选修8门课程？

我不是一个伟大的作家，所以我很抱歉在这个问题上有任何模棱两可的地方。请随时要求澄清，我会尽力帮助你的。

这是完整的代码。

http://bpaste.net/show/ZY36uvAgcb1ujjUGKA1d/

注意：很抱歉使用了误导性的标签（日程安排）。

Answer 1

当前生成节组合的方式可能是抛出大量组合，这些组合被多个课程之间的冲突排除在外。我认为你可以先为两门课程生成部分的乘积，从而减少需要处理的组合数。从这个集合中消除冲突，然后介绍第三个课程的章节。再次消除，然后引入第四个，依此类推。随着所选课程数量的增加，所需的处理时间应呈线性增长。

Answer 2

你读过关于基因编程的书吗？它背后的想法是，你让你想要解决的“东西”自己进化，直到它成长为可能的最佳解决方案。

您生成了一千个计划，其中通常零是有效的正确方向上的任何地方。下一步，你随机地改变一些课程。从这些新的时间表中，你选择一些最好的，根据你给予的评级，根据'善良'的时间表。接下来，通过将两个时间表中的一些课程组合起来，让它们重现。你最终得到了上千个新的日程安排，但所有的都比你原来的好一小部分。让它重复，直到您满意为止，并从您生成的上千个计划中选择评分最高的计划。

我承认，这涉及到随机性，但无论你让算法运行多长时间，日程安排都会越来越好。就像现实生活和有机体一样，适者生存，也有可能看到同一种时间表中不同的一般“线索”，这与生成的另一个时间表差不多。两个完全不同的时间表最终可以通过杂交来“对抗”它。

一个涉及学校时间表和遗传规划的项目： http://www.codeproject.com/Articles/23111/Making-a-Class-Schedule-Using-a-Genetic-Algorithm

我认为他们很好地解释了你需要什么。

最后一点：我认为这是一个非常有趣的项目。这是很难做到的，但一旦做到了，它只是伟大的看到你的解决方案演变，就像现实生活。祝你好运！

Answer 3

调度是一个非常著名的constraint satisfaction problem，通常是NP-Complete。在这个问题上已经做了很多工作，甚至在与您相同的上下文中：Solving the University Class Scheduling Problem Using Advanced ILP Techniques。甚至还有关于这个主题的textbooks。

人们采取了许多方法，包括：

• Dynamic programming
• Genetic algorithms
• Neural networks

你需要减少你的问题空间和复杂性。尽可能多地假设（类的最大数量、基于块的计时等）。这个问题没有银弹，但应该可以找到一个接近最优的解决方案。

一些半近期出版物：

• QUICK scheduler a time-saving tool for scheduling class sections
• Scheduling classes on a College Campus