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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

V2EX 提问指南

这是一个创建于 802 天前的主题，其中的信息可能已经有所发展或是发生改变。

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

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

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

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

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

课时

班级

算法

节教

20 条回复 • 2022-09-05 08:43:20 +08:00

Tamio

2022-09-03 17:48:44 +08:00

K12 是什么

yanyumihuang

2022-09-03 17:50:04 +08:00 via Android

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

jdhao

2022-09-03 17:50:23 +08:00 via Android

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

jackma0571

2022-09-03 17:59:52 +08:00

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

learningman

2022-09-03 18:13:34 +08:00 via Android

建议学习背包九讲

wbrobot

2022-09-03 18:35:17 +08:00

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

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

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

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

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