最近在做课程表的排课，涉及很复杂的计算，有没有算法大牛能给点建议或者提示吗？

[klo424]

给学校开发自动排课的工具，会有很多规则限制，计算起来相当复杂。网上搜到了遗传算法，但是加了繁多的规则后计算就会很慢，可能计算 1 个小时都没有个完美的结果，所以特来请教一下 V 站大佬们有没有好的算法？

规则有很多，列出几个 K12 必须要有的：

• 禁止排课：设置一些班级星期几的第几节课不能排某个课程，例如每天的前两节不能排体育课。
• 必须排课：设置一些班级星期几的第几节课必须排某个课程，例如周一的第一节课必须排数学课。
• 课时分散：保证课程在每天平均分配课时，使课程尽量分散不在同一天上 2 节课，例如该班语文课一周共有 5 个课时，就要把这 5 个课时分配到每天 1 个课时，如果是只有 3 个课时，则每个课要隔一天在排，即周一 /周三 /周五。
• 教案齐头：保证每个教师的教的每个班级最好连着上课，例如教师 A 教 1 班和 2 班两个班级，如果 A 在周一 3 节教 1 班，则在周一 4 节教 2 班，尽量不要分成两天教，方便教师备课。

我不知道对这几个规则理解的是不是到位，但大致上差不多是这样的。

就这 4 个规则就很复杂了，用遗传算法要算好久，求帮助！

[Tamio]

K12 是什么

[yanyumihuang]

@Tamio k12 就是 12 年也就是小学到高中

[jdhao]

你这应该属于规划问题，可以考虑专门的规划软件，lingo 不知道是否可行

[jackma0571]

就不该自动排课，提供个版面，自己手动去选每节是什么课，最多加个自动应用到每一周

[learningman]

建议学习背包九讲

[wbrobot]

我的想法:
1, 肯定是全年级一起排, 把班级编号-[教师]连起来算一个萝卜(如果教师带多个课程,那就把教师课程组合起来)
2, 按照 班级编号-教师, 循环一个课程数量, 做成一个总数组.
3, 全年级的课程按照 班级编号-周几-第几节课,算坑.
4, 开始填坑, 填坑简单规则: 班级编号相等即可.

以上过程, 通过随机萝卜,生成课表.

然后按照后续苛刻条件一个个检查, 课表不符合就重新随机萝卜.
如,
条件一: 前两节有体育课, return false;
条件二: 周一第一节不是数学, return false;
...

好处是,通用性强, 苛刻条件就是增加检查函数而已

这样就不用搞什么复杂的算法了, 就是发挥计算机的特长-不知疲劳,热爱重复计算... 就是费电...当然这个求解的过程,要看复杂度, 我预估了一下,十几个班的话, 应该还好(具体需要自己跑一遍试试)

[woctordho]

我估计光靠背包问题之类的动态规划还解决不了，楼主用的遗传算法的大方向应该没错，但是具体实现的速度还可以优化

[hsfzxjy]

用 prolog ？

[line]

通过神经网络应该可以， 每个不违反规则的排课都得分， 求最小损失。

[zxCoder]

遗传算法那些其实就是随机算法。规则一多慢是正常的

[paopjian]

试一下 ortools?谷歌的能解决背包问题工具

[locochen]

感觉生产上面排场排程也类似

[jiang42]

前面提到的 prolog ，ortools 都可以
还可以把这个问题转成 sat 问题用 sat solver 求解
这种级别的数据量不会算不出来的。。。

[7zlid]

反过来，按老师排，之后转换

[dlsflh]

最近有新闻讲 NBA 是怎么排赛程的，挺复杂的事情。

[7zlid]

@7zlid
转换成:1 某个老师不排某几个课
2.某个老师必须上某几个课
3.这个老师每天的课不多于多少节

[7zlid]

@7zlid 4 这个老师每天有两个班
之后给老师一个优先级别，非常轻易就可以计算出来了了
调换优先级，就能产生不同的课表

[joApioVVx4M4X6Rf]

以前上学的时候就想写一个这个东西给学校的教务系统，结果没啥思路。。。关注一下楼主

[statumer]

这个其实很简单，蒙特卡洛搜索就行了，什么神经网络就是搞笑的
反正一学期只排一次，跑个两三天也无所谓。

[klo424]

@wbrobot @hsfzxjy @paopjian @jiang42 @statumer 感谢提供思路！