浅谈贪心算法在排课系统中的应用

邓曦辉

（晋中学院计算机系，山西晋中030600）

1.排课问题概述

高校的课表编排是一个非常复杂的工程，涉及到学校的几十个专业、上千名教师和上万名学生。课表的编排要处理好教师、学生、教室、时间等多种冲突，编排的合理与否、科学与否，将直接影响课堂教学的效率和教学的整体效果。为了合理安排几百门课程，排课人员必须充分认识课程表功能，掌握任课教师的情况及排课的需求，并且依照以下编排原则科学编制。

（1）课程表是一所高校开展教学工作的运行指挥图，全校师生正是依据课程表来进行教学活动的。课程表要根据教学计划，将讲授课程的教师、实施教学活动的教室和学习课程的学生等资源遵守时间不冲突的原则在某个时间片段结合起来。课表是面向全校学生，要安排上百门课程，因此必须从全局保证整体利益。

（2）在保证时间无冲突的情况下，尽量将课程安排在上此类课效果最好的时间。每周的周二、周三、周四是最佳学习日，每天上午是教学的最佳课时，应该把难度大、关键的课程安排在此时间段。其它课程，例如体育课则安排在下午教学。

（3）根据人类大脑皮层活动的优势规律，应该交替编排课程。理论课与实践课要交替编排；人文学科与自然学科课程交替编排；同一门课程不应连排，中间应该保持适当的时间间隔。

（4）尽量使每个班级一周所上课程安排均衡。

总之，编排课表有很强的原则性、科学性和技术性，必须依照学校的实际情况来编排，既要照顾学科的特点，又要符合学生心理与活动规律。要将课程表编排得科学、合理，以促使教学工作优化、高效。

2.贪心算法的基本思想

贪心算法是一种简化解题复杂度的算法。它的基本思想是：从问题的某一个初始解出发，采用逐步构造当前状态下最优解，以尽可能快的速度逐步逼近给定的目标的搜索方法[1]。贪心算法不在整体上考虑最优，而是把整个问题分成若干个阶段，保证在每个阶段做出当前看来的最优决策，并且一旦做出决策就不再更改。使用贪心算法省去了为找到整体最优解穷尽所有可能而耗费的大量时间，并且可以快速得到较为满意的解。

3.排课系统算法分析

排课问题是一个涉及时间、教师、班级、课程、教室五个因素的典型排列组合问题。在排课时，最基本的要求就是避免班级、教师在时间和空间上面的冲突，即依次为对学校所开设的每门课程，搜索到该课程班级、授课教师、上课教室同时具有共同的空闲时间片安排上课即可。根据前面的分析，排课算法的实质就是依次为所有课程安排合适的上课时间和合适的上课地点。如果在排课过程中同时考虑上课时间和上课地点会使得课表的编排方案数量急速增加，甚至会引起“组合爆炸”，为了避免这种情况发生，简化算法的复杂度，排课算法将排课任务分解为时间安排和地点安排两个步骤。使用两次贪心选择的方法，首先根据该课程指定的时间片分配方案为该课程搜索当前最优上课时间，上课时间确定后，再为课程搜索当前满足约束条件的最优上课教室[2]。

4.排课系统算法的实现

（1）初始化

就是删除系统数据库中部分或全部数据表中的内容，以便于新学期开始时输入新的数据。采用手工输入方式时，应保留班级、教师、教室等基本数据，以减小输入工作量；而采用自动导入方式时，应清空所有数据表，以避免数据重复。

（2）读取记录

将教室、教师、课程、班级以及教学任务安排等信息通过手工输入或自动导入的方式存入数据库，并设置好各类系统参数存入数据库。

（3）选定上课时间

随机选定上课时间，查看相关的班级、教师、教室三个课表中的相应授课时间是否空闲，若都空闲，则写入课表。

（4）记录回滚

记录回滚是在某项记录无法排下去的情况下启动的，提取该记录的班级、教师、教室信息向回找已经排过的最近的相同信息，提取该信息对应的记录，重新从这条记录开始编排[3]。

4.总结

本文讨论了影响排课问题中的各种因素，总结排课问题的硬性约束和软性约束，结合实际情况，设计了基于贪心算法的排课系统。算法将排课任务分解为时间安排和地点安排两个步骤。使用两次贪心选择的方法，首先根据该课程指定的时间片分配方案为该课程搜索当前空闲的最优上课时间，然后为课程搜索当前满足约束条件的最优上课教室。

[1] 唐洪英，周敏.基于分层分次贪心算法的排课系统的设计与实现[J].微计算机信息，2006(12):237-240

[2] 王伟，余利华.基于贪心法和禁忌搜索的实用高校排课系统[J].计算机应用，2007，11(21):2873-2876

[3] 聂小东，李振坤，陈平华.基于贪婪算法的排课系统的探讨与实现[J].现代计算机，2007，11:109-112