基于回溯算法的智能排课系统

薛　峰

【摘 要】 排课问题是一个典型的组合优化和不确定性调度问题。本文研究了排课问题中的约束条件及数学模型,从回溯算法的基本理论着手,解决排课系统中的资源冲突、优化等问题,给出了基于回溯法的排课算法。

【关键词】回溯法;数学模型;排课算法

一、引言

排课问题,从一般意义上说,就是在给定教师和教室资源、学生人数和开课计划的前提下,合理为课程安排时间与地点的问题。对于规模较小,教师、教室、学生人数不多的情况下,进行人工排课还较顺利,但对于规模较大,复杂的排课问题(如高等院校),进行人工排课,则费时费力,其科学合理性更是无法保证,计算机技术的普及给排课问题搭建了一个平台,用计算机进行排课已经势在必行。本文充分利用回溯算法的特点,给出了利用计算机进行排课的有效求解方法。

二、回溯算法

回溯法是一种选优搜索法。按选择最优解的条件向前搜索,以达到目的。但每当搜索到某一步时,发现其达不到预期的效果,就退回一步重新选择。这种行不通就退回再搜索的技术称为回溯法。

回溯法就其算法的逻辑思路可表示为一棵树,根结点是初始状态,每搜索到一个结点都有若干个可供选择的后继结点,没有任何能达到到目标的暗示,只有走着瞧,不行了就回溯到上一层结点,恢复原来刚使用过的参数,再走另一条路径,所以回溯法其本质是穷举与试探,找到从根结点到叶子结点中所有的正确结果。基于回溯算法的许多优点,其应用范围也较为广泛。

三、排课问题中的约束条件及数学模型

排课问题的关键就是为了解决课程安排对时间和空间资源的有效利用并避免相互冲突。排课的优化目标就是使得各类冲突为零,并且尽可能满足教师、学生的要求,达到较好的教学效果。这就要求在实际排课过程中,需要考虑到教师、学生、班级、教室、教室的大小、实验设备等方面的问题。要满足班级、教师、教室上课不冲突;教室的座位应该满足上课班级学生的需要等等。所以对排课问题的基本约束条件如下:

1.同一时间,同一个教师,同一个学生,同一个教室不允许同时上一门以上课程;

2.教室必须有足够的座位容纳学生;

3.某些课程需要安排在特定的教室;

4.对于需要试验设备的课程,教室需要有相应的配套设备。比如生化课需要生化仪器。

通过对排课问题约束条件的分析,可以看到排课问题实际上是将某种定量资源分配给不同的需求个体,并同时满足一定的约束条件,因此其数学模型可概括为一个资源分配模型,该数学模型的几个要素:

1.需求集。其集合中的元素就是需要安排时间、教室与教师的课程,其特征有课程名称,上课人数,授课教师等等。

2.资源集。上课时间集合与教室集合就是两个最根本的资源集。对于时间资源集中的元素,时间序数就是唯一也是最基本的特征。而教室资源集中的元素,可以有教室大小(座位数)、教室用途等多种特征。

3.约束条件群。需求集中的元素特征与资源集中的元素特征相互作用形成的数学关系,构成了约束条件群。根据不同特征的性质,可以将约束条件分为两类:

映射约束。映射约束是一个Z[M,N]的矩阵,其中M是需求集中的元素个数,N是资源集中的元素个数,矩阵元素值是将资源元素i分配该需求元素j的满意度,是一个权值。由于在排课问题中,资源具有独占性,不可再分配,故应有M

软约束。需求集中的元素特征与资源集中的元素特征形成的多维,不定型约束。

4.解集,其形式为符合约束条件的一组解,实质就是需求集与资源集之间的对应关系,称为分配向量。

四、排课算法

排课系统中,选优条件即为排课数学模型中的约束条件群。换而言之,若不满足约束条件群,该选择即为不优或达不到目标。当遍历该步骤的所有可能仍未满足约束条件群,则该状态满足了回溯条件,该状态点即为回溯点。

具体的排课算法如下:

1.建立资源集合Y[N],并进行排序;

2.建立需求集合X[M],并进行排序;

3.建立映射约束矩阵Z[M,N],若元素值假定为0或1,则满意度为一个二元选择;

4.定义变量i=1;j=1;

5.为分配,其中,(i<=M,j<=N);

6.检查是否满足约束(包括映射约束条件群和软约束条件群);

7.若不满足,则为其分配Y中的第j+l个元素;

8.若Y中所有资源都被分配过,仍不满足约束条件群,则此状态作为回溯点,重新为X中第i-1元素分配资源(将i减1,回到第5步);

9.分配X中下一个元素(将i加1,回到第5步)。以此下去,直至X中所有元素均合理分配。

五、结束语

本文在回溯算法的基础上设计实现了智能排课系统,从排课的结果分析得出所编排的课程表满足排课原则,有效解决冲突问题,课时安排比较均匀。但对实际排课中的一些模糊因素,其更规范的数学描述有待研究。算法的性能有待于进一步提高。

参考文献

[1]吴志斌,陈淑珍等.回溯算法与计算机智能排课[J].计算机工程,1999,25(3):79-80.

[2]夏小云,高武军.基于遗传算法的高校智能排课系统[J].人工智能及识别技术,2008,4(1):175-177.

[3]王健,董改芳,许道云.自动排课系统的模型与实现[J].贵州大学学报:自然科学版,2004,21(2):34-36.

[4] Lander SE.Issues in Multiagent Design Systems, IEEE Expert, 1997, 12(5):18-26.