有效安排大学课程

Question

我目前正在开发一个网站，让我们大学的学生能够根据他们想参加的课程自动生成有效的时间表。

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

以下是几点澄清：

1. 我们大学的每门课程(我假设是在其他每一所大学)都由一个或多个部分组成。因此，例如，Calculus I目前有4个部分可用。这意味着，取决于章节的数量，以及课程是否有实验室，这将极大地影响调度过程。
2. 我们大学的课程使用主题缩写和课程代码相结合的方式来表示。关于微积分I:数学1110。
3. CRN是一段独特的代码。
4. 我就读的大学不是混合的，这意味着男女在(几乎)分开的校园里学习。我的意思几乎是说校园被分成两部分。
5. datetimes和timeranges旨在减少对datetime.datetime.strptime()的调用，这是一个真正的瓶颈。

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

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

第二种算法与旧算法正好相反。首先，它使用itertools.product()生成所有可能的调度组合的集合。然后，它遍历日程，删除任何无效的。为了确保分类区段，在验证之前对调度组合进行了洗牌(random.shuffle())。同样，也涉及到一些随机性。

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

为了给您一个想法，当我提供一组特定的输入时，可能的组合数量是如此之大，以至于itertools.product()不会在合理的时间内终止，并且在这个过程中消耗掉1GB的内存。

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

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

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

我还有别的选择吗？我是否可以采取一种相对容易理解的方法来解决这个问题？或者，我应该坚持我所拥有的，希望下学期不会有多少人决定上8门课？

我不是一个伟大的作家，所以我对问题中的任何含糊不清之处感到抱歉。请随时要求澄清，我会尽力帮忙的。

这是完整的代码。

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

注意:抱歉使用了误导性标签(日程安排)。

Answer 1

调度是一个非常著名的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

Answer 2

你读过任何关于基因编程的文章吗？它背后的想法是，你让你想要解决的“事情”自行进化，直到它发展到可能的最佳解决方案为止。

您将生成1000个时间表，其中通常为零，在正确的方向上都是有效的。接下来，你随意地改变“一些”课程。从这些新的时间表中，你选择了一些最好的，根据你给出的评分，根据时间表的‘好’。接下来，通过将两个时间表上的一些课程结合起来，让他们进行复制。你最终会有一千份新的时间表，但它们都比你的计划好一小部分。让它重复到您满意为止，并从最后生成的1000次中选择评分最高的计划。

我承认，这涉及到随机性，但无论你让算法运行多长时间，时间表都会变得越来越好。就像现实生活和有机体一样，适者生存也是如此，我们有可能看到同一种时间表中不同的一般“线程”，这与另一种时间表差不多。两个非常不同的时间表最终可以通过杂交来“战斗”出来。

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

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

最后一点:我认为这是一个非常有趣的项目。这是相当困难的，但一旦完成，它只是看到你的解决方案演变，就像现实生活。祝好运!

Answer 3

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