排课系统开发中贪婪和回溯算法的应用

李 雄

(江西财经职业学院，江西九江 332000)

要根据高校现有的教学资源信息，编排出一个行之有效的、科学合理的、符合自身实际情况的课表，是每一个高校不断追求的目标。排课系统在设计开发中算法的采用是关键，而目前排课算法中主要有贪婪和回溯算法。

一、贪婪和回溯算法设计的思想

排课算法具备以下的特点:

(1)有限性:算法在执行相关的运算时，它的执行过程不能是无尽进行的，存在有解;

(2)确定性:算法在执行运算过程中每一个阶段得到的结果是明确的，不应该存在不确定性的结果;

(3)通用性:采用某一个算法它主要是对问题的整体进行求解，不是某一层面的求解;

(4)不唯一性:在系统中采用的算法求得的问题解不能是单一的，必须存在各种的求解方法。

贪婪算法的设计思想:在求解问题中，将问题分解化处理，求得每一个分解层面的最好的解，然后综合分析每一分解层面的最好求解，从而得到问题的整体最好的解。即在采用贪心算法的对相关问题求解的过程中一定要根据存在的制约因素达到以下前提要求:

(1)问题的最好求解能通过将整体性问题分层，对分层问题得到最好求解，然后在所有分层求解中经过分析找到问题整体的最好求解;

(2)在求解问题中将问题分层处理，确保所分层问题求解过程中都存在最好的求解。

回溯算法的设计思想:要得到问题的解，首先要将问题执行科学合理的转换，将问题的求解形成状态空间树，先从其中某一种情况进行试探，在试探过程中，一旦发现原来的选择是错误的，那么就退回一步重新选择，直到找到存在的解。

二、排课算法分析

排课问题的关键是算法，同时也是关键点和难点。排课问题的关键点和难点是如何将有限排课要素资源进行有效的整合，得到最优的结果，避免它们之间出现任何的冲突出现，而编排课表就成为一个开课班、授课老师和开课地点之间的组合排列问题。这个组合排列的求解，就要满足教师、教室和班级时间上是否存在共同点，从而确定课程的安排定位。这样形成教师、教室和班级空闲时间的三维空间关系，而得到三者经过相关约束条件在三维空间上的交集点C就是该课程的安排定位。如图1所示授课老师、开课地点和开课班空闲时间的三维空间关系。

图1 授课老师、开课地点和开课班空闲时间的三维空间关系

三、贪婪算法和回溯算法的设计

根据上述算法的分析，在排课系统开发中采用贪婪算法和回溯算法的主要原因是，根据上述内容的描述获得，排课问题实质就是班级、授课老师和开课地点三维空间寻找空闲时间交点集的组合排序任务。

1.贪婪算法的使用好处

在存在的班级、教师和教室三位空间组合中，如学院的安排数据有5000到6000条，每一条安排数据有可能多老师和多个行政班合成，相关特殊约束条件也很多:一门课程只能允许一个时段内一个授课老师进行授课;一个班级只允许在相同时间内使用一个教室;一个时段只允许唯一的班级只能进行开设一科课程;一个时间内所安排班级数不能超过教室容纳总数;教室类型必须满足开课班级授课要求等等条件约束，如果采用其它算法，用户在时间效率上无法接受，可能排1到2天。所以采用了贪婪算法，保证在排每条安排时找到较佳的满足要求的时间和地点。

贪婪算法的步骤:

(1)从开课班、授课老师和教室三维空间集合中的班级、教师和教室其中的某一项个因素求解出发，如此类推，找到他们三者之间的集合点;

(2)在班级、教师和教室三维空间组合中为找到他们的集合点，利用循环指令，对所求问题分层求得每层的解，求出每层问题的最好解，然后在每层的求解中在根据需求条件继续对整体问题进行求解;

(3)将班级、教师和教室三位空间组合所有部分解综合起来，得到问题的最终解。

2.回溯算法采用的因素具体表现

排课问题涉及开课班级、课程、时间、教师、上课地点多各因素相互制约，是一个典型的排列组合问题。而根据教学计划的预期安排，授课教师与课程是一一对应关系，从而在排课时，只需对学校所有班级开设的课程，安排课程、教师、教室具有共同的空闲时间片上课即可，排课算法也就简化为开课班级、授课教师、开课地点三个方面因素在具有共同的空闲时间片前提下的排列组合问题，为求满足各因素存在的制约条件，利用回溯算法在开课班、授课老师和开课地点所组成的三维空间组合中寻找到最优的交点C即存在的教学安排。回溯算法根据排课问题存在的约束规则，在这个三维空间搜索空闲时间片集合，如果该集合存在，说明排课问题有解。

回溯算法执行的具体表现:

(1)设定编排课表各相关的要素求解的方式，设定开课班、授课老师和开课地点排列组合的解空间，它包含编排课表问题存在各种解。

(2)构造状态空间树。

(3)构造约束函数 (用于杀死节点)。

排课的部分约束条件:

(1)避免上课班连上相同的课程。

(2)课间更换上课教室时，更换的教室相隔不能太远。

(3)必须在周课时中人性化的设定班级和老师的授课。

(4)专用功能教室尽量安排专业课程使用。

(5)对于年纪较大或身体不好的教师尽量安排合适的低楼层教室。

四、贪婪算法和回溯算法详解

(1)读取排课相关数据

将读取的教学计划的学期课表以及学分要求，并与相关课程数据结合计算出一个班的课程及课时数。

(2)数据的预处理

①时间的预处理:根据学校实际情况，上课时间为每星期5天，星期一至星期五。划分每天为若干个时间片，即对应为每天的8节课。分别代表上午1～2节、下午3～4节等等。

②教师的预处理:从数据库中读取教师数据，并按教师的工号排列，针对某一个课程id建立对应教师的课程列表。

③教室的预处理:在数据库中创建某种类别的教室集合表。

④课程的预处理:将读取信息库中课程信息存放入课程链表中。

⑤约束规则的预处理:从数据库表中读取所有约束规则，然后按约束规则的优先级priority降序排列并存放到约束条件的链表里。

(3)贪婪算法和回溯算法运用经过

①读取编排课表中教学计划和课程相关数据，得到班级的开课计划。接着从中挑选一门授课，得到其相应的课时数。

②依据步骤①选择课程，查询教师链表，选择符合该门课程和约束规则的教师，求出该门课程的任课教师集合。随机或者按某种规则优先的方式选择一位任课教师。若此阶段无法找到满足要求的教师则回溯至执行①。

③依据步骤①选择课程，查询教室链表。考虑到课程对教室的要求，应获取对应类型的教室的集合，并从该集合中剔除掉其容量小于班级人数的教室。若此阶段没有获得相应的教室就回溯到步骤②。

④遍历选择时间片。检测生成的排课信息数据，查看是否存在冲突。首先检测教师存在的时间段内有没有其他课程，有没有空闲教室，开课班级有没有闲空时间。若冲突检测完成，即检测特殊约束以及相对制约因素，两种制约的测试方式是相同的，区别只是优先级不同。检测通不过就直接选择下个时间片，如果检测成功，则排课记录就新生成一个。若所有时间片都不能通过检测，则回溯至步骤③。

(4)结果存储

如果一个班的所有课程都按照上述算法生成了相应的课表记录，就可以永久性的将课表记录经过ADO.NET接口将数据持存储到数据库。

五、贪婪和回溯算法整体流程图

贪婪算法主要是采取将问题分层处理，求解出每层问题的最好解，在结合每层的解得到问题整体性的最好求解结果;回溯算法它即属于对问题求解从整体性和对问题随机试探寻解的一种求解方法。根据其算法的执行程序步骤，在求解问题中，探索寻到某一个结果就完成其求解工作。在排课系统开发中贪婪算法和回溯算法的整合将有助于更好的解决高校在排课中的繁重问题。

图2 贪婪和回溯算法整体流程图

〔1〕宋晓飞，王鹏，贺敏佳.基于回溯算法的高校排课系统 ［J］.科技信息，2009，(07).

〔2〕曾光清.贪婪算法在高校排课系统中的运用 ［J］.福建金融管理干部学院学报，2007，(06).

〔3〕聂小东，李振坤，陈平华.基于贪婪算法的排课系统的探讨与实现［J］.现代计算机，2007，(11).

〔4〕张慧如，郎静.计算机排课问题分析与排课算法的研究 ［J］.现代企业教育，2011，(08).