我目前正在建立一个网站,允许我大学的学生根据他们想要的课程自动生成有效的时间表.
在开展网站工作之前,我决定解决如何有效安排课程的问题.
一些澄清:
我们大学的每门课程(我假设在其他所有大学)都包含一个或多个部分.因此,例如,微积分I目前有4个部分可用.这意味着,根据部分的数量,以及课程是否有实验室,这会极大地影响调度过程.
我们大学的课程使用主题缩写和课程代码的组合来表示.在微积分I的情况下:MATH 1110.
CRN是一个部分唯一的代码.
我所在的大学并不喜欢,这意味着男性和女性在(几乎)不同的校园里学习.我的意思几乎就是校园分为两部分.
datetime和timeranges dicts旨在减少对datetime.datetime.strptime()的调用,这是一个真正的瓶颈.
我的第一次尝试包括连续循环算法直到找到30个时间表.通过从一个输入的课程中随机选择一个部分,然后尝试从剩余的课程中放置部分来尝试构建有效的时间表来创建时间表.如果并非所有课程都符合时间表,即存在冲突,则会取消时间表并继续循环.
显然,上述解决方案存在缺陷.该算法运行时间太长,并且过于依赖随机性.
第二种算法与旧算法完全相反.首先,它使用itertools.product()生成所有可能的计划组合的集合.然后,它会遍历计划,将任何无效的计划交叉.为了确保各个部分,在验证之前调度计划组合(random.shuffle()).同样,涉及到一些随机性.
经过一些优化后,我能够让调度程序在1秒内运行,平均时间表包含5个课程.这很好,但一旦你开始添加更多课程,问题就开始了.
为了给你一个想法,当我提供一组输入时,可能的组合数量太大,以至于itertools.product()不会在合理的时间内终止,并且在此过程中会占用1GB的RAM.
显然,如果我要将其作为服务,我将需要更快,更有效的算法.在线和IRC中出现了两个:动态编程和遗传算法.
动态编程不能应用于这个问题,因为如果我正确地理解了这个概念,它会将问题分解成更小的部分,单独解决这些部分,然后将这些部分的解决方案结合在一起形成一个完整的解决方案.据我所知,这不适用于此.
至于遗传算法,我对它们了解不多,甚至无法理解如何在这种情况下应用它.我也理解GA对于一个非常大的问题空间会更有效,而且这并不是那么大.
我有什么替代品？我可以采取一种相对可以理解的方法来解决这个问题吗？或者我应该坚持我所拥有的并希望下个学期没有多少人决定参加8门课程？
我不是一个伟大的作家,所以我很抱歉这个问题含糊不清.请随时要求澄清,我会尽力帮助.
这是完整的代码.
http://bpaste.net/show/ZY36uvAgcb1ujjUGKA1d/
注意:很抱歉使用误导性标记(计划).