学文网摘 要：文中介绍了回溯算法的基本思想和特点，分析了回溯算法在排课系统应用与其他算法的不同之处。针对排课系统理念分析，解决排课时教师时间、班级时间与教室利用时间三者之间冲突的判断方式。对排课系统的各项功能进行了设计。
关键词：回溯算法 排课 冲突
中***分类号：G434 文献标识码：A 文章编号：1672-3791（2016）08（a）-0108-02
课表是学校教学工作和其他活动的“调度指挥表”，是教师、学生上课的依据。不论学校是何等规模，都会有课表编排问题。传统的人工排课方式以其繁重的工作量和低下的效率为诟病。排课具有复杂性及系统性，目前仍然没有一个完美的解决办法。该文回顾国内外排课系统应用的发展现状，总结了各种常见算法在排课问题上的优缺点，选择回溯算法来解决这一问题。
1 回溯算法简介
1.1 回溯算法的基本思想
回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。八皇后问题就是回溯算法的典型，第一步按照顺序放一个皇后，然后第二步符合要求放第2个皇后，如果没有符合条件的位置符合要求，那么就要改变第1个皇后的位置，重新放第2个皇后的位置，直到找到符合条件的位置就可以了。回溯在迷宫搜索中使用很常见，就是这条路走不通，然后返回前一个路口，继续下一条路。回溯算法实质就是穷举法。回溯算法使用剪枝函数，剪去一些不可能到达最终状态（即答案状态）的节点，从而减少状态空间树节点的生成。回溯法是一个既带有系统性又带有跳跃性的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根节点出发搜索解空间树。算法搜索至解空间树的任一节点时，总是先判断该节点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该节点为根的子树的系统搜索，逐层向其祖先节点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根节点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法 [1]，它适用于解一些组合数较大的问题。
1.2 回溯算法的求解步骤
回溯算法求解过程包括如下步骤：（1）定义一个解空间，它包含问题的解。（2）利用适于搜索的方法组织解空间。（3）利用深度优先法搜索解空间。（4）利用限界函数避免移动到不可能产生解的子空间。问题的解空间通常是在搜索问题的解的过程中动态产生的，这是回溯算法的一个重要特性。
1.3 回溯算法在排课系统上的特点
回溯算法是一个既带有系统性又带有跳跃性的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根节点出发搜索解空间树。算法搜索至解空间树的任一节点时，总是先判断该节点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该节点为根的子树的系统搜索，逐层向其祖先节点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根节点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。它适用于解一些组合数较大的问题。高校排课的组合就是很巨大的，使用回溯算法能更好地保证排课的正确性与实用性。
2 排课系统算法分析
排课问题是涉及教师、教室、班级、课程和时间五个因素的排列组合问题。排课时，最基本的要求（硬性约束）就是避免教师、班级在时间和空间上产生冲突。解决的办法就是依次为开设的每门课程搜索到该课程教师、班级和教室共同空闲的时间片[2]。
排课算法的实质就是为课程安排上课时间和上课地点。但是，如果同时考虑这两者，必然会引起“组合爆炸”现象。所以为了避免这种情况，笔者采用回溯算法进行排课，首先算出符合时间要求的老师，然后选出符合时间要求的教室。
3 排课过程
自动排课系统，采用回溯算法，一层一层地进行查找合适的时间以及教室。
3.1 确定上课时间
首先确定上课的时间。上课的教师时间是否已被占用，没有占用，则进行下一步；如果被占用，则查找下一个时间片教师时间是否被占用。
3.2 确定上课教师
确定完上课时间后，还要确定上课地点。安排上课地点的原则是时间片不能与其他课程冲突。所以如果时间片不能满足要求，要重新进行时间安排。回溯算法中要对教师时间和教室时间是否被占用进行判断。教师和教室的时间片标记事先是写好在数据库里的，根据不同的代码和时间片代码从数据库中读取标记位，然后进行判断就可以了。教师时间冲突判断代码如下：
string mystr = ConfigurationManager.AppSettings["myconnstring"]；
OleDbConnection myconn = new OleDbConnection（）；
OleDbCommand mycmd1 = new OleDbCommand（）；
OleDbCommand mycmd2 = new OleDbCommand（）；
myconn.ConnectionString = mystr；
myconn.Open（）；
string mysql1 = "SELECT 教师ID FROM 课程信息 WHERE ID='"+kid+"'"；
mandText = mysql1；
mycmd1.Connection = myconn；
string id = mycmd1.ExecuteScalar（）.ToString（）；
string mysql2 = "SELECT t"+ ti +" FROM 教师时间 WHERE 教师ID='" + id + "'"；
mandText = mysql2；
mycmd2.Connection = myconn；
string flag = mycmd2.ExecuteScalar（）.ToString（）；
if（flag=="0"）
{
return true；
}
else
return false；
教室时间冲突与教师时间冲突代码一致。
在时间冲突解决之后就是对课程进行记录了，在算法中有一个自定义类Jilukecheng（），其返回值就是已经排列完成的课程的名称和上课的教师以及上课的教师的字符串。
4 结语
系统设计在校教务部门试验应用，经测试，系统能够基本满足教务工作人员排课工作需求，减轻了教务部门的工作量，对高校办公自动化起到了推进作用。
参考文献
[1] 杨兴旺.基于回溯法的排课算法[J].电脑知识与技术，2009，5（19）：5196-5197.
[2] 陈树敏，叶涛.教务管理信息系统后台数据库的设计与实现[J].自动化与信息工程，2009，30（2）：46-47.
转载请注明出处学文网 » 排课系统算法及功能的实现