14

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

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

一些澄清：

  1. 我们大学的每门课程（我假设在其他每所大学）都包含一个或多个部分。因此，例如，微积分 I 目前有 4 个部分可用。这意味着，根据部分的数量，以及课程是否有实验室，这会极大地影响调度过程。

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

  3. CRN 是一个部分的唯一代码。

  4. 我就读的大学不是混合的，这意味着男性和女性在（几乎）不同的校区学习。我的意思几乎是校园一分为二。

  5. datetimes 和 timeranges 字典旨在减少对 datetime.datetime.strptime() 的调用，这是一个真正的瓶颈。

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

显然，上述解决方案是有缺陷的。该算法运行时间过长，并且过于依赖随机性。

第二种算法与旧算法完全相反。首先，它使用 itertools.product() 生成所有可能的计划组合的集合。然后它遍历时间表，划掉任何无效的。为了确保分类的部分，计划组合在被验证之前会被打乱（random.shuffle()）。同样，涉及到一些随机性。

经过一些优化，我能够让调度程序在 1 秒内运行，平均安排由 5 门课程组成。这很好，但是一旦您开始添加更多课程，问题就开始了。

给你一个想法，当我提供一组输入时，可能的组合数量非常大，以至于 itertools.product()不会在合理的时间内终止，并在此过程中占用 1GB 的 RAM。

显然，如果我要将此作为一项服务，我将需要一个更快、更有效的算法。在网上和 IRC 中出现了两个：动态编程和遗传算法。

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

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

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

我不是一个伟大的作家，所以对于问题中的任何含糊之处，我深表歉意。请随时要求澄清，我会尽力提供帮助。

这是完整的代码。

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

注意：很抱歉使用了误导性标签（调度）。

4

5 回答 5

18

Scheduling is a very famous constraint satisfaction problem that is generally NP-Complete. A lot of work has been done on the subject, even in the same context as you: Solving the University Class Scheduling Problem Using Advanced ILP Techniques. There are even textbooks on the subject.

People have taken many approaches, including:

You need to reduce your problem-space and complexity. Make as many assumptions as possible (max amount of classes, block based timing, ect). There is no silver bullet for this problem but it should be possible to find a near-optimal solution.

Some semi-recent publications:

于 2012-11-06T19:35:20.447 回答
4

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

您生成一千个计划，其中通常为零是在正确方向有效的任何地方。接下来，您随机更改“一些”课程。从这些新的时间表中，您可以根据您根据时间表的“优点”给出的评级选择一些最好的时间表。接下来，通过结合两个时间表上的一些课程，让它们重现。你最终得到了一千个新的时间表，但它们都比你原来的好一点点。让它重复直到您满意为止，然后从您生成的最后一千个中选择具有最高评分的时间表。

我承认，这涉及到随机性，但是无论您让算法运行多长时间，时间表都会越来越好。就像现实生活和生物一样，适者生存，可以查看同一种时间表的不同一般“线程”，这与生成的另一个线程差不多。两种截然不同的时间表最终可以通过杂交来“对抗”它。

一个涉及学校时间表和基因编程的项目：http: //www.codeproject.com/Articles/23111/Making-a-Class-Schedule-Using-a-Genetic-Algorithm

我认为他们很好地解释了您的需求。

最后一点：我认为这是一个非常有趣的项目。制作起来相当困难，但一旦完成，很高兴看到您的解决方案不断发展，就像现实生活一样。祝你好运！

于 2012-11-06T19:32:18.527 回答
3

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

于 2012-11-06T20:13:52.903 回答
2

这是一个难题。如果你用谷歌搜索“课程安排问题论文”之类的东西，你会发现很多参考资料。遗传算法 - 不，动态规划 - 是的。GA 比标准 DP 算法更难理解和实施。通常开箱即用 GA 的人不了解标准技术。做一些研究，你会发现不同的算法。您也许可以找到一些实现。想出自己的算法比花一些精力理解 DP 要困难得多。

于 2012-11-06T19:32:43.933 回答
1

您描述的问题是约束满足问题。我的方法如下：

  • 检查课程之间是否有任何不兼容，如果有，将它们记录为约束或弧
  • 虽然没有找到解决方案：
    • 选择约束较少的课程（即与其他课程的不兼容性较少）
    • 运行 AC-3 算法以减少搜索空间

我已经尝试过这种解决数独问题的方法，它奏效了（在不到 10 秒的时间内解决了世界上最难的数独问题）

于 2017-05-13T18:50:06.497 回答