哪种算法用于为学校生成时间表

Question

我正在研究一个简单的应用程序,它将为学校生成时间表(每日计划).我已经阅读了算法的基础知识,但对于从哪里开始感到困惑.

问题:
考虑到很多限制,将教师分配到课堂上:
1)学科
2)教师的专业知识
3)不超过2个班级等等

不言而喻,应该没有重叠.基本上我需要将N名教师分配到每天有固定工作时数的M班(8).

输入:
1)班级总数
2)教师及其专业知识
3)每个班级的科目/课程
4)每班每天的讲座数量
5)其他灵活的约束条件,如教师每天的最小/最大工作时间,每位教师每周的总工作时间等

我的问题:
1)将它视为具有多个约束的赋值问题是否正确？
2)我应该使用哪种算法？(匈牙利算法？)
3)我应该从一开始就获得整套约束,然后生成表,还是应该在中间步骤中完成？

我是学习/实现算法的初学者,所以任何指导我正确方向的帮助都值得赞赏!谢谢.

Answer 1

你开始选择了一个问题.像这样的调度优化是NP完成的.有很多关于如何处理这类问题的论文,这类问题被称为约束满足.您可以进行详尽的搜索,这是最简单的,但也非常耗时,如果您有一些以上的课程将无法正常工作.您可以查看求解器基础,它是.net的一套工具,用于解决这些问题.Scott Hanselman在这里播放了一个关于它的播客http://www.hanselminutes.com/default.aspx?showID=209,你可以在这里找到更多关于它的信息 http://code.msdn.microsoft.com/solverfoundation.如果您喜欢自己尝试,请尝试查看GSAT或其他一些演化算法看起来很有趣http://www.springer.com/engineering/book/978-3-540-48582-7.