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

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

  •  1
     
  •   klo424 · 156 天前 · 1761 次点击
    这是一个创建于 156 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

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

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

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

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