这是一个创建于 1136 天前的主题，其中的信息可能已经有所发展或是发生改变。
给学校开发自动排课的工具，会有很多规则限制，计算起来相当复杂。网上搜到了遗传算法，但是加了繁多的规则后计算就会很慢，可能计算 1 个小时都没有个完美的结果，所以特来请教一下 V 站大佬们有没有好的算法？
规则有很多，列出几个 K12 必须要有的：
- 禁止排课：设置一些班级星期几的第几节课不能排某个课程，例如每天的前两节不能排体育课。
- 必须排课：设置一些班级星期几的第几节课必须排某个课程，例如周一的第一节课必须排数学课。
- 课时分散：保证课程在每天平均分配课时，使课程尽量分散不在同一天上 2 节课，例如该班语文课一周共有 5 个课时，就要把这 5 个课时分配到每天 1 个课时，如果是只有 3 个课时，则每个课要隔一天在排，即周一 /周三 /周五。
- 教案齐头：保证每个教师的教的每个班级最好连着上课，例如教师 A 教 1 班和 2 班两个班级，如果 A 在周一 3 节教 1 班，则在周一 4 节教 2 班，尽量不要分成两天教，方便教师备课。
我不知道对这几个规则理解的是不是到位，但大致上差不多是这样的。
就这 4 个规则就很复杂了，用遗传算法要算好久，求帮助！
 | 1 Tamio 2022-09-03 17:48:44 +08:00 K12 是什么 |
 | 2 yanyumihuang 2022-09-03 17:50:04 +08:00 via Android @Tamio k12 就是 12 年也就是小学到高中 |
 | 3 jdhao 2022-09-03 17:50:23 +08:00 via Android 你这应该属于规划问题，可以考虑专门的规划软件，lingo 不知道是否可行 |
 | 4 jackma0571 2022-09-03 17:59:52 +08:00 就不该自动排课，提供个版面，自己手动去选每节是什么课，最多加个自动应用到每一周 |
 | 5 learningman 2022-09-03 18:13:34 +08:00 via Android 建议学习背包九讲 |
 | 6 wbrobot 2022-09-03 18:35:17 +08:00  3 我的想法: 1, 肯定是全年级一起排, 把班级编号-[教师]连起来算一个萝卜(如果教师带多个课程,那就把教师课程组合起来) 2, 按照 班级编号-教师, 循环一个课程数量, 做成一个总数组. 3, 全年级的课程按照 班级编号-周几-第几节课,算坑. 4, 开始填坑, 填坑简单规则: 班级编号相等即可. 以上过程, 通过随机萝卜,生成课表. 然后按照后续苛刻条件一个个检查, 课表不符合就重新随机萝卜 如, 条件一: 前两节有体育课, return false; 条件二: 周一第一节不是数学, return false; ... 好处是,通用性强, 苛刻条件就是增加检查函数而已 这样就不用搞什么复杂的算法了, 就是发挥计算机的特长-不知疲劳,热爱重复计算... 就是费电...当然这个求解的过程,要看复杂度, 我预估了一下,十几个班的话, 应该还好(具体需要自己跑一遍试试) |
 | 7 woctordho 2022-09-03 18:43:09 +08:00 via Android 我估计光靠背包问题之类的动态规划还解决不了，楼主用的遗传算法的大方向应该没错，但是具体实现的速度还可以优化 |
 | 8 hsfzxjy 2022-09-03 18:46:27 +08:00 via Android 1 用 prolog ？ |
 | 9 line 2022-09-03 18:48:39 +08:00 通过神经网络应该可以， 每个不违反规则的排课都得分， 求最小损失。 |
 | 10 zxCoder 2022-09-03 19:09:21 +08:00 遗传算法那些其实就是随机算法。规则一多慢是正常的 |
 | 11 paopjian 2022-09-03 20:03:21 +08:00 1 试一下 ortools?谷歌的能解决背包问题工具 |
 | 12 locochen 2022-09-03 20:04:21 +08:00 via iPhone 感觉生产上面排场排程也类似 |
 | 13 jiang42 2022-09-03 22:32:50 +08:00 1 前面提到的 prolog ，ortools 都可以 还可以把这个问题转成 sat 问题用 sat solver 求解 这种级别的数据量不会算不出来的。。。 |
 | 14 7zlid 2022-09-03 22:36:17 +08:00 via Android 反过来，按老师排，之后转换 |
 | 15 dlsflh 2022-09-03 22:59:08 +08:00 via Android 最近有新闻讲 NBA 是怎么排赛程的，挺复杂的事情。 |
| 16 7zlid 2022-09-03 23:42:10 +08:00 via Android |
| 17 7zlid 2022-09-03 23:43:47 +08:00 via Android |
 | 18 joApioVVx4M4X6Rf 2022-09-04 13:36:14 +08:00 以前上学的时候就想写一个这个东西给学校的教务系统，结果没啥思路。。。关注一下楼主 |
 | 19 statumer 2022-09-04 14:30:20 +08:00 via iPhone 1 这个其实很简单，蒙特卡洛搜索就行了，什么神经网络就是搞笑的 反正一学期只排一次，跑个两三天也无所谓。 |
style type="text/css">.wwads-cn { border-radius: 3px !important; } .wwads-text { color: var(--link-color) !important; }
Select Language