V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
klo424
V2EX  ›  问与答

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

  •  1
     
  •   klo424 · 2022-09-03 16:58:03 +08:00 · 2875 次点击
    这是一个创建于 812 天前的主题,其中的信息可能已经有所发展或是发生改变。

    给学校开发自动排课的工具,会有很多规则限制,计算起来相当复杂。网上搜到了遗传算法,但是加了繁多的规则后计算就会很慢,可能计算 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
        1
    Tamio  
       2022-09-03 17:48:44 +08:00
    K12 是什么
    yanyumihuang
        2
    yanyumihuang  
       2022-09-03 17:50:04 +08:00 via Android
    @Tamio k12 就是 12 年也就是小学到高中
    jdhao
        3
    jdhao  
       2022-09-03 17:50:23 +08:00 via Android
    你这应该属于规划问题,可以考虑专门的规划软件,lingo 不知道是否可行
    jackma0571
        4
    jackma0571  
       2022-09-03 17:59:52 +08:00
    就不该自动排课,提供个版面,自己手动去选每节是什么课,最多加个自动应用到每一周
    learningman
        5
    learningman  
       2022-09-03 18:13:34 +08:00 via Android
    建议学习背包九讲
    wbrobot
        6
    wbrobot  
       2022-09-03 18:35:17 +08:00   ❤️ 3
    我的想法:
    1, 肯定是全年级一起排, 把班级编号-[教师]连起来算一个萝卜(如果教师带多个课程,那就把教师课程组合起来)
    2, 按照 班级编号-教师, 循环一个课程数量, 做成一个总数组.
    3, 全年级的课程按照 班级编号-周几-第几节课,算坑.
    4, 开始填坑, 填坑简单规则: 班级编号相等即可.

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

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

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

    这样就不用搞什么复杂的算法了, 就是发挥计算机的特长-不知疲劳,热爱重复计算... 就是费电...当然这个求解的过程,要看复杂度, 我预估了一下,十几个班的话, 应该还好(具体需要自己跑一遍试试)
    woctordho
        7
    woctordho  
       2022-09-03 18:43:09 +08:00 via Android
    我估计光靠背包问题之类的动态规划还解决不了,楼主用的遗传算法的大方向应该没错,但是具体实现的速度还可以优化
    hsfzxjy
        8
    hsfzxjy  
       2022-09-03 18:46:27 +08:00 via Android   ❤️ 1
    用 prolog ?
    line
        9
    line  
       2022-09-03 18:48:39 +08:00
    通过神经网络应该可以, 每个不违反规则的排课都得分, 求最小损失。
    zxCoder
        10
    zxCoder  
       2022-09-03 19:09:21 +08:00
    遗传算法那些其实就是随机算法。规则一多慢是正常的
    paopjian
        11
    paopjian  
       2022-09-03 20:03:21 +08:00   ❤️ 1
    试一下 ortools?谷歌的能解决背包问题工具
    locochen
        12
    locochen  
       2022-09-03 20:04:21 +08:00 via iPhone
    感觉生产上面排场排程也类似
    jiang42
        13
    jiang42  
       2022-09-03 22:32:50 +08:00   ❤️ 1
    前面提到的 prolog ,ortools 都可以
    还可以把这个问题转成 sat 问题用 sat solver 求解
    这种级别的数据量不会算不出来的。。。
    7zlid
        14
    7zlid  
       2022-09-03 22:36:17 +08:00 via Android
    反过来,按老师排,之后转换
    dlsflh
        15
    dlsflh  
       2022-09-03 22:59:08 +08:00 via Android
    最近有新闻讲 NBA 是怎么排赛程的,挺复杂的事情。
    7zlid
        16
    7zlid  
       2022-09-03 23:42:10 +08:00 via Android
    @7zlid
    转换成:1 某个老师不排某几个课
    2.某个老师必须上某几个课
    3.这个老师每天的课不多于多少节
    7zlid
        17
    7zlid  
       2022-09-03 23:43:47 +08:00 via Android
    @7zlid 4 这个老师每天有两个班
    之后给老师一个优先级别,非常轻易就可以计算出来了了
    调换优先级,就能产生不同的课表
    joApioVVx4M4X6Rf
        18
    joApioVVx4M4X6Rf  
       2022-09-04 13:36:14 +08:00
    以前上学的时候就想写一个这个东西给学校的教务系统,结果没啥思路。。。关注一下楼主
    statumer
        19
    statumer  
       2022-09-04 14:30:20 +08:00 via iPhone   ❤️ 1
    这个其实很简单,蒙特卡洛搜索就行了,什么神经网络就是搞笑的
    反正一学期只排一次,跑个两三天也无所谓。
    klo424
        20
    klo424  
    OP
       2022-09-05 08:43:20 +08:00
    @wbrobot @hsfzxjy @paopjian @jiang42 @statumer 感谢提供思路!
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1082 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 31ms · UTC 18:50 · PVG 02:50 · LAX 10:50 · JFK 13:50
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.