回溯算法在排课系统中的应用研究

罗月映

广西大学，广西　南宁　530226



回溯算法在排课系统中的应用研究

罗月映*

广西大学，广西南宁530226

摘要：排课系统是现代高校教务管理系统的重要组成部分之一，好的排课系统不仅能够减少教务管理人员的工作量，还可以极大地提高工作效率。本文在认真分析回溯算法实现思想的基础上，给出了回溯算法在排课系统中的具体应用过程，有一定的实用价值。

关键词：回溯算法；排课系统

一、引言

排课问题是一个人们一直都在研究的课题，但目前所有高校所使用的排课系统都各不相同，即排课系统不具有通用性，目前解决排课问题所使用的算法主要有模拟退火算法、贪心算法、遗传算法以及回溯算法，各种算法各有其优缺点以及它们的实用范围。本文将对回溯算法加以适当的改进，采用基于优先级的回溯算法实现排课问题的处理。

二、回溯算法分析

回溯法也称为试探法，是一种搜索解空间和寻求最优解的方法。回溯法的基本实现思想是：构造一棵解空间树，从树的根结点沿着一条选定的路径一直往下走，能走则会沿着指定线路一直前进，否则就会按照原路返回，换一条路线继续行走，它的实质是对解空间树进行搜索的过程。该算法的主要优点主要包括：

(一)对空间的消耗较少，当其与分支定界法共同使用时，对所求最优解在解答树中层次较深的问题时会获得比较理想的效果。

(二)使用中依据贪心算法的思想，在时间分配时总是在未分配的时间片中选择排课效果最好的课程，并在时间分配冲突时，向上回溯搜索到发生冲突的前一个记录，对其进行重新选择以解决问题。

三、排课问题分析

排课问题是NP完全问题和组合规划问题的结合，具有相应的复杂性和不确定性。求解排课问题时，时间、课程、教室作为三个相互制约的主要因素和教学资源。排课的过程主要是针对教师、班级、课程、时间和教室这五个基本要素，根据不同的满足条件进行组合与规划的问题，并且课表的编排要求不能有教师、班级和教室这三个要素之间的冲突。课程表的编排还应该充分考虑教师的时间安排、教学设备和教学资源的利用率、是否符合教学规律等相关因素，因此课表的编排必须遵循一些“硬性约束”和“软性约束”。

此外，排课问题实质上是时间片、教师、班级、教室、课程这五维关系的冲突问题，要合理的解决这个问题首先要了解排课中的一些基本原则以及排课的一些基本要求。其中时间片的涵义是以课表的每一大节课(包含两小节)为单元来记作一个时间片，如某一天的某一大节课。本文将影响排课的五个要素按照对象、时间与空间的关系划分为：对象资源、时间资源和空间资源。其中，教师，班级和课程称为对象资源；时间片称为时间资源；教室称为空间资源。

四、回溯算法在排课问题中的实际应用

在排课的过程中需要指定教师和班级的优先级，并且教室要按照其人数的容量从小到大进行排列。其中，教师优先级=老师上课数/总课时，当优先级大于1时报错，教师按其优先级从大到小排列。班级优先级=该班级所有课程的老师的优先级总和，班级按其优先级从大到小排列。

此外，算法在实现的过程中，需要做好三个基本表的设置工作，即教室使用表、课程安排限制表及教师排课限制表。设置工作主要包括教室使用、课程安排及教师排课在每天(周一到周五)每个时段(一天包括五大节课)使用情况。

依据排课问题的相关设置及回溯法的的实现思想，可以得到回溯算法在排课问题中的具体伪代码如下：

int paike()

{ while(遍历时间片)

{

if(排序失败) return 1；// 调用优先级排序函数重新排序

while(遍历班级)

{

得到一个班级；

if(该班级已分配){ continue；}//已经分配，继续下一个，否则尝试分配

while(遍历该班级的课程)

{

得到一门课程；

if(任课教师已分配或该课程已安排){ continue；}

while(遍历教室)

{

得到一个教室；

if(教室已分配或教室总容量不够)

{ continue；}

else

{

设置教师已经分配标志位；

设置班级已经分配标志位；

设置班级本周已经上课课时；

设置教室已经分配标志位；

添加课表；

函数递归；

if(返回值== 2)

{

还原教师已经分配标志位；

还原班级已经分配标志位；

还原班级本周已经上课课时；

还原教室已经分配标志位；

还原课表；

continue；

}

if(返回值 == 0)

{ return 0；}

}

}

}

}

更换时间片，并设置各标志位为假；

}

时间片遍历完；

while(遍历全部班级)

{

得到一个班级；

while(遍历该班级课程)

{

得到一门课程

if(本门课程没上完)

{ return 2；}

}

}

return0；}

}

paike()函数在执行完毕以后会有相应的返回值，其中0代表排课完成，1代表排序失败，2代表课程没上完。

五、结束语

本文主要针对回溯算法在排课问题中的一些用进行了相关探讨研究，其主要思路是对回溯算法进行了一些改进，加入了优先级，做了一些限定条件，提高了算法的实现效率。但排课问题是非常复杂的NP完全问题和组合规划问题的结合，其实现方式多种多样，并且到目前为止没有一个统一的解决方案，因此本文的研究只是对排课问题解决的一种尝试，具体还需要做更多的改进。

[参考文献]

[1]刘彦.基于优先级与回溯算法的排课系统的设计与实现[D].黑龙江大学，2012.

[2]甘茂杰.教务排课系统的设计与实现[D].电子科技大学，2012.

作者简介：罗月映(1987-)，女，广西百色人，广西师范学院师园学院，助理研究员，广西大学2012级在读工程硕士，从事教育管理工作。

中图分类号：TP311.52

文献标识码：A

文章编号：1006-0049-(2016)07-0069-02