logo标签列表

高效安排大学课程

pythonalgorithmscheduling
15
我目前正在开发一个网站，让我们大学的学生可以根据他们想要上的课程自动生成有效的课程表。
在着手处理网站本身之前，我决定先解决如何高效地安排课程的问题。
需要澄清几点：
1. 我们大学（我认为其他大学也是如此）的每门课程都由一个或多个章节组成。因此，例如，微积分I目前有4个可用章节。这意味着，根据章节数量以及课程是否有实验室，这会极大地影响排课过程。
2. 我们大学使用科目缩写和课程代码的组合来表示课程。例如，在微积分I的情况下：MATH 1110。
3. CRN是唯一标识章节的代码。
4. 我所就读的大学没有混合校区，男女学生（几乎）在不同的校区学习。我的意思是，校园被分成两个部分。
5. datetimes和timeranges字典旨在减少对datetime.datetime.strptime()的调用，后者是真正的瓶颈。
我的第一次尝试是使用循环算法，直到找到30个时间表为止。通过从输入课程中随机选择一个部分，然后尝试将其他课程的部分放置到该部分中来创建时间表。如果不是所有课程都适合时间表，即存在冲突，则放弃该时间表并继续循环。
显然，上述解决方案存在缺陷。算法运行时间太长，并且过于依赖随机性。
第二个算法与旧算法完全相反。首先，它使用itertools.product()生成所有可能的时间表组合集合。然后，通过交叉检查无效的时间表来迭代时间表。为了确保各种部分，验证之前会对时间表组合进行洗牌（random.shuffle()）。同样，涉及了一些随机性。
经过一些优化，我能够使调度程序在平均包含5门课程的时间表下运行不到1秒钟。这很好，但一旦你开始添加更多课程，问题就开始了。
举个例子，当我提供一定的输入集时，可能的组合数量如此之大，以至于itertools.product()在合理的时间内无法终止，并且在此过程中消耗了1GB的RAM。
显然，如果我要将这个变成一个服务，我需要一个更快、更有效的算法。在网上和IRC上出现了两种算法：动态规划和遗传算法。
动态规划无法应用于此问题，因为如果我正确理解概念，它涉及将问题分解为较小的部分，分别解决这些部分，然后将这些部分的解决方案结合起来形成完整的解决方案。就我所见，这在这里不适用。
至于遗传算法，我不太理解它们，并且甚至无法想象如何在这种情况下应用它。我还知道GA对于极大的问题空间更有效，而这并不是那么大。
我有什么替代方案？是否有相对易于理解的方法来解决这个问题？或者我应该坚持现在的做法，希望不会有太多人在下学期选择8门课程？
我不是一个很好的作家，所以对于问题中的任何模糊之处，我很抱歉。请随时要求澄清，我会尽力帮助。
这是完整的代码。

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

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

3
你实际上在问什么？这似乎非常模糊且开放性很大。顺便说一下，调度问题通常是NP难题。已经对这个确切问题进行了很多研究，你尝试过谷歌搜索和查阅相关出版物吗？例如：http://www.aloul.net/Papers/faloul_sch_gcc07.pdf - Austin Henley
1
这看起来就像背包问题。你有一堆课程和一个预定的时间分配，你必须填满一个背包，使得当前背包中的课程没有重叠，并尽可能地占用时间。如果问题是这样提出的，那么可以应用遗传算法来高效（有时）地找到最优的、带误差的课程安排。 - sean
1
这是一个约束满足问题。 - Austin Henley
3
排课难度大是众所周知的，需要安排课程时间和教室等等。但是，楼主已经有了整个大学的课表，对吧？楼主只是在尝试为特定学生的兴趣找到一个兼容的子集。不需要动用核武器来解决这个问题。 - A. Webb
1
@Cyph0n 那么你的最小时间单位是-30分钟。将一天分成30分钟的时间段，从最早的课程到最晚的课程。每周5天* 24个时间段= 120个总时间段。您可以为每个课程分配一个二进制表示（120位长的位数组）的时间，并将其保存在内存中。这样，当您查找日程表时，您只需要执行a|b，如果c的计数不等于a + b的计数，则会发生冲突。使用这种冲突检测方法，6！（720）比较将几乎是瞬间完成的。（没有字符串操作，耶！） - kreativitea
显示剩余13条评论
5个回答
18
以下是翻译的结果：

排班是一个非常著名的约束满足问题，通常是NP完全问题。在这个主题上已经做了很多工作，甚至在与您相同的背景下：使用先进的ILP技术解决大学课程排班问题。甚至有教科书讲述这个主题。

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

您需要减少问题空间和复杂性。尽可能做出许多假设（最大班级数量，基于块的时间安排等）。这个问题没有银弹，但应该可以找到近乎最优的解决方案。

一些较新的出版物:

4
你有没有读过关于遗传编程的文章？其背后的想法是让你想要解决的“事物”自我进化，直到它已经成长为可能的最佳解决方案。
你生成一千个时间表，通常没有一个符合有效性的方向。然后，你随机更改一些课程。从这些新的时间表中，你根据时间表的“好处”给出评分，选择其中一些最好的时间表。接下来，你让它们繁殖，通过组合两个时间表上的一些课程。你最终得到了一千个新的时间表，但它们都比你拥有的那些时间表稍微好一点。重复此过程，直到满意，并从你生成的最后一千个时间表中选择评分最高的时间表。
我承认存在随机性，但无论你让算法运行多长时间，时间表都会变得越来越好。就像现实生活和生物一样，只有适者生存，可以查看相同类型的时间表的不同总体“线索”，这大约与生成的另一个时间表一样好。通过交叉育种，两个非常不同的时间表最终可以“竞争”。
涉及学校时间表和遗传编程的项目： http://www.codeproject.com/Articles/23111/Making-a-Class-Schedule-Using-a-Genetic-Algorithm 我认为他们解释得很好，你需要的内容就在这里。
我的最后一句话：我认为这是一个非常有趣的项目。它相当难以完成，但一旦完成，看到你的解决方案像现实生活一样演化，感觉真的很好。祝你好运！
感谢您提供详细的答案。我一定会查看那篇文章。 - Assil Ksiksi
3

你目前生成章节组合的方式可能会产生大量被多个课程之间冲突所排除的组合。我认为你可以通过仅针对两门课程的章节生成乘积来减少需要处理的组合数量。从该集合中消除冲突，然后引入第三门课程的章节。再次消除，然后引入第四门课程，以此类推。随着所选课程数量的增加，这应该会看到所需处理时间的更线性增长。

2

这是一个难题。如果你搜索“课程排课问题论文”之类的内容，你会找到很多参考资料。遗传算法-不行，动态规划-可以。相比标准DP算法，GAs更难理解和实现。通常使用GAs的人不了解标准技术。做一些研究，你会发现不同的算法。你可能能够找到一些实现。自己想出算法要比花些时间理解DP难得多。

1
你描述的问题是一个约束满足问题（Constraint Satisfaction Problem）。我的方法如下：
  • 检查课程之间是否存在不兼容，如果有，则记录为约束或弧
  • 当没有找到解决方案时：
    • 选择与其他课程不相容最少的课程（即与其他课程不相容性最小的课程）
    • 运行AC-3算法以减少搜索空间

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

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接