背景
业务上需要做一个排课系统,先调研了业内友商的排课系统,同时做了算法的对比和可行性分析。
需求
排课任务:设置任务名称、学期、排课年级集合;
节次设置:设置每周上课天数,以及每天上课节次数(上午节次数、下午节次数、晚上节次数);
课程设置:设置排课科目集合,以及各个科目的总课时、连堂课时;
教师设置:设置排课老师集合,以及各个老师所带科目、所带班级;
排课规则设置:
不排课规则:支持多维度不排课;
班级不排课:某班级不允许在选择的节次排课;
教师不排课:某老师不允许在设置的节次排课;
课程不排课:某科目不允许在设置的节次排课;
不连堂规则:选择两个相邻节次,不允许排连堂课;例如:选择上午第一节、第二节,则不允许排连堂课;
优先规则:支持多维度优先;
课程优先:在某节次内排课,遵循某课程优先选择原则;
教师优先:在某节次内排课,遵循某教师优先选择原则;
合班规则:设置科目、班级合班后,多个班级某科目的上课时间在同一个节次;
单双周规则:设置某年级的单、双周课程组合;例如:单周上道法课,双周上自然课;
课程互斥规则:可以给多个课程设置互斥规则,设置规则的课程不会在一天内排课;
预排规则:预先给部分课程和老师进行排课;
其它规则:
教案齐平规则
周任课规则:某科目的课程分布:周内分散,周内集中;
日任课规则:某科目的课程分布:日内分散,日内集中;
算法
排课算法选择:
贪心算法: 贪心算法可以用于一些简单的排课问题,例如按照某种优先级安排课程。但在实际应用中,可能需要结合其他算法来处理更复杂的约束条件。
遗传算法: 遗传算法在优化问题上表现优异,可以用于优化排课方案。通过模拟自然选择和基因变异的过程,遗传算法能够搜索到比较好的解。
模拟退火算法: 模拟退火算法是一种全局搜索算法,适用于在搜索空间中找到全局最优解的问题。在排课系统中,可以用于搜索满足各种约束条件的最优排课方案。
贪心算法
贪心算法是一种简单而直观的算法,但它也有一些明显的局限性:
局部最优不一定导致全局最优:贪心算法每步都选择当前状态下的最优解,但这种局部最优并不保证最终得到全局最优解。有些问题需要考虑长远影响,贪心算法无法预测未来的局势。
不适用于所有问题:贪心算法通常适用于某些特定类型的问题,但对于某些问题,贪心策略可能导致次优解或者不可行解。例如,某些涉及到约束条件的问题可能无法通过简单的贪心选择解决。
没有回溯:贪心算法做出选择后就无法撤销,它不具备回溯的能力。如果之前的选择导致后续无法找到解,贪心算法无法进行修正。
对问题的依赖性:贪心算法的效果也取决于问题的性质。在某些情况下,贪心算法可能表现良好,但在另一些情况下可能效果较差。
可能需要排序:对于某些问题,贪心算法可能需要对元素进行排序以选择最优解。排序本身可能引入额外的复杂度。
总体而言,贪心算法是一种简单而快速的近似算法,但在解决一些复杂问题时可能表现不佳。在设计算法时,需要仔细考虑问题的特性,选择合适的算法以获得更好的解决方案。
模拟退火算法
模拟退火算法(Simulated Annealing)是一种基于统计力学中的退火过程的全局优化算法。它被广泛应用于解决组合优化问题,包括排课、旅行商问题等。
基本思想:
模拟退火算法通过模拟固体退火时的温度变化过程,逐步降低系统能量(目标函数值),以接受较差的解,防止陷入局部最优解。
主要步骤:
初始化: 随机生成初始解,并设置初始温度和