贪心算法在高校排课系统中的应用精编2篇

【导言】此例“贪心算法在高校排课系统中的应用精编2篇”的范文资料由阿拉题库网友为您分享整理，以供您学习参考之用，希望这篇资料对您有所帮助，喜欢就复制下载支持吧！

常用的几种高校排课算法1

关键词：民办高校 排课 算法研究

当前或者之前的一段时间里，大多数民办高校采用的是手动排课的方式进行课程安排，但是这种手动排课的方式只是适用于很小的教学集体，当学校学生基数比较大教师比较多的时候手动排课显得非常不合适，运作效率非常低。利用计算机进行排课具有时间短人力省和质量高的优点，不但能使教务人员从繁杂的排课任务中解脱出来，而且对于教学的发展也起到非常重要的作用。下面介绍几种常用的排课算法：

一、基于优先级的排课算法

从数学上讲，排课问题是一个在时间、教师、学生和教室四维空间，以教学计划和各种特殊要求为约束条件的组合规划问题。其实质就是解决各因素之间的冲突。在设计算法时，为了降低课程调度的算法复杂性，主要采用了化整为零的思想及优先级算法。

（一）排课的预处理

等价类的划分：将具有共同听课对象的任务划分在同一等价类中，在每个等价类之间只存在地点上的冲突，而没有时间上的冲突。然后按照的大小，从大到小进行处理。等价类的划分可以先按年级分，然后再按系别分。

教室分类：为了合理使用教室，我们采用了教室分类的办法，以便尽可能在课程编排过程中避免上课人数少的课程盲目强占容量大的教室现象。

（二）时间预处理

1.构造时间模式库

时间模式是根据教务人员的经验，为各种周学时数不同的课程指定的一种时间组合方式。例如，一门课程的周学时数为4，那么它的时间组合方式可以有：“11”，“41”；表示该课程一周上两次，分别为周一的12节和周四的12节L同时，为了达到较好的上课效果，也要对这些时间模式进行分级。

2.时间数组

为了表示班级、教师、教室的可排课时间，分别为他们建立一维数组。例如，某位教师的初始可排课时间数组为（123456 123456 123456 123456 123456）。其中共有五组数据，分别表示一周中的五天；而一组数据共有6个字符“1、2、3、4、5、6”分别表示一天中的六个时间单元。当为某位教师分配时间后，相应的那位字符就置为0L例如，某位教师的可排课时间数组为（020456 103456 003456 120456 023456），则表示这位教师在周一的12节和56节，周二的34节，周三的12节和34节，周四的56节，周五的12 节已经安排了课程，如果要再安排课程的话，就应该安排在非0的时间单元L对于班级和教室也可以进行同样的处理，分别标出可排课时间。

（三）每一子类的排课处理

在对每个子类的排课处理中，我们结合了分治法、贪婪法、回溯法三者的思想。首先，根据分治法的思想把整个排课过程分成时间分配和教室分配两个阶段。然后，依据贪婪法的算法思想，在时间分配时，总是在尚未分配的时间单元中选择上课效果最好的单元。而在时间分配发生死锁时，会向上回溯搜索到发生冲突的最近一个记录，然后对它进行重排以解决冲突。

（四）查找适当的时间模式

找到可排课时间后，就应根据课程的周学时数在时间模式库中匹配适当的时间模式。完成以上工作后，就确定了课程的上课时间和地点。如果在处理中发生死锁，则可根据回溯法的思想向上回溯搜索到发生冲突的最近一个记录，然后对它进行重排以解决死锁，如果仍不能解决死锁问题，则可以将该课程信息输出到冲突列表中。

（五）人工干预的处理

本算法所设计的人工干预过程有：等价类划分中参数的设置，教室类型的设置，时间模式库的设置，优先级函数中参数的设置。用户可以根据自己的具体要求对这些参数和库进行设置。另外，对于计算机排出的课程表，用户也可以通过人机交互进行适当调整，从而得到用户满意的课程表。

二、冲突检测算法

此算法对班级及教室划分等价类，对学校资源进行了合理的利用，以课程为中心，进行搜索匹配，取最先匹配的值；具有占有空间少，运算速度快的特点。

三、遗传算法

遗传算法是一种随机的全局搜索和优化算法。它从一个种群（Population）开始的，该群种可能是问题的一个可能潜在解集。而一个群种是由经过一系列基因（Gene）编码（Coding）的一定数目的个体（Individual）组成。每个个体可以看作带有某些特征的染色体实体（Chromosome）。生物学中，染色体是多个基因的集合，是遗传物质的主要载体，决定其内部表现。实质上在内部，染色体是某种基因组合，比如染色体中控制皮肤头发颜色这一特征的基因经过组合，就决定了生物个体的皮肤是白色的还是黑色的。因此在工作之初，需要把实体表现出来的信息特征抽象为一些位串来表示，实现外部特征和位串的映射，并且为了简化采用二进制编码。产生了初始种群之后，将“适者生存，优胜劣汰”的生物进化原理应用到实际问题的解决中。

四、PSO算法

PSO算法是基于群体的，根据对环境的适应度将群体中的个体移到好区域。将每个个体看作是具有唯一速度在多维搜索空间中飞行的没有体积的粒子，每个个体的速度由它飞行的经验和同伴的飞行经验来动态调整。进一步分析出用来结束迭代过程的条件。

粒子群优化算法PSO（Particle Swarm Optimization）是由Kennedy和Eberhart通过对鸟群、鱼群和人类社会某些行为的观察研究，于1995年提出的一种新颖的进化算法与遗传算法类似，它也是基于群体迭代。变异算子，群体在解空间中追随最优粒子进行搜索。PSO的优势在于简单且容易实现，同时又有深刻的智能背景，既适合科学研究，又适合工程应用。鉴于PSO的发展历史尚短，它在理论基础与应用推广上都还存在一些问题，有待解决。当前PSO算法存在的问题，如：收敛速度慢、求解多峰函数优化问题时易陷入局部极小以及早熟收敛的缺点，提出了一种新的基于专业化分工与协作的寻优策略，以期对PSO算法做出改进。

粒子群优化算法是一种基于群体迭代的进化算法，以往的PSO改进方法使PSO算法的性能得到了提高，但是没能充分发挥粒子群的群体优势，我们希望就是在现有方法的基础上，充分利用粒子群的群体优势， 使之较好地适应复杂的实际环境。

参考文献

[1]李赫男。粒子群优化算法综述[J].现代计算机，2009，301（2）：22-27.

[2]陈冬亮。排课的数学模型和算法在教务管理系统中的应用研究。电脑知识与技术，2006，（6）.

[3]陈洁。学校教务部门排课问题的数学模型及算法。1999，（3）：53-56.

[4]张忠。课程表问题中的应用[J].华南金融电脑。2007（06）.

（作者单位：1青岛科技大学；2青岛黄海学院）

排课系统算法及功能的实现2

摘 要：文中介绍了回溯算法的基本思想和特点，分析了回溯算法在排课系统应用与其他算法的不同之处。针对排课系统理念分析，解决排课时教师时间、班级时间与教室利用时间三者之间冲突的判断方式。对排课系统的各项功能进行了设计。

关键词：回溯算法 排课 冲突

中图分类号：G434 文献标识码：A 文章编号：1672-3791（2016）08（a）-0108-02

课表是学校教学工作和其他活动的“调度指挥表”，是教师、学生上课的依据。不论学校是何等规模，都会有课表编排问题。传统的人工排课方式以其繁重的工作量和低下的效率为诟病。排课具有复杂性及系统性，目前仍然没有一个完美的解决办法。该文回顾国内外排课系统应用的发展现状，总结了各种常见算法在排课问题上的优缺点，选择回溯算法来解决这一问题。

1 回溯算法简介

回溯算法的基本思想

回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。八皇后问题就是回溯算法的典型，第一步按照顺序放一个皇后，然后第二步符合要求放第2个皇后，如果没有符合条件的位置符合要求，那么就要改变第1个皇后的位置，重新放第2个皇后的位置，直到找到符合条件的位置就可以了。回溯在迷宫搜索中使用很常见，就是这条路走不通，然后返回前一个路口，继续下一条路。回溯算法实质就是穷举法。回溯算法使用剪枝函数，剪去一些不可能到达最终状态（即答案状态）的节点，从而减少状态空间树节点的生成。回溯法是一个既带有系统性又带有跳跃性的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根节点出发搜索解空间树。算法搜索至解空间树的任一节点时，总是先判断该节点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该节点为根的子树的系统搜索，逐层向其祖先节点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根节点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法 [1]，它适用于解一些组合数较大的问题。

回溯算法的求解步骤

回溯算法求解过程包括如下步骤：（1）定义一个解空间，它包含问题的解。（2）利用适于搜索的方法组织解空间。（3）利用深度优先法搜索解空间。（4）利用限界函数避免移动到不可能产生解的子空间。问题的解空间通常是在搜索问题的解的过程中动态产生的，这是回溯算法的一个重要特性。

回溯算法在排课系统上的特点

回溯算法是一个既带有系统性又带有跳跃性的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根节点出发搜索解空间树。算法搜索至解空间树的任一节点时，总是先判断该节点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该节点为根的子树的系统搜索，逐层向其祖先节点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根节点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。它适用于解一些组合数较大的问题。高校排课的组合就是很巨大的，使用回溯算法能更好地保证排课的正确性与实用性。

2 排课系统算法分析

排课问题是涉及教师、教室、班级、课程和时间五个因素的排列组合问题。排课时，最基本的要求（硬性约束）就是避免教师、班级在时间和空间上产生冲突。解决的办法就是依次为开设的每门课程搜索到该课程教师、班级和教室共同空闲的时间片[2]。

排课算法的实质就是为课程安排上课时间和上课地点。但是，如果同时考虑这两者，必然会引起“组合爆炸”现象。所以为了避免这种情况，笔者采用回溯算法进行排课，首先算出符合时间要求的老师，然后选出符合时间要求的教室。

3 排课过程

自动排课系统，采用回溯算法，一层一层地进行查找合适的时间以及教室。

确定上课时间

首先确定上课的时间。上课的教师时间是否已被占用，没有占用，则进行下一步；如果被占用，则查找下一个时间片教师时间是否被占用。

确定上课教师

确定完上课时间后，还要确定上课地点。安排上课地点的原则是时间片不能与其他课程冲突。所以如果时间片不能满足要求，要重新进行时间安排。回溯算法中要对教师时间和教室时间是否被占用进行判断。教师和教室的时间片标记事先是写好在数据库里的，根据不同的代码和时间片代码从数据库中读取标记位，然后进行判断就可以了。教师时间冲突判断代码如下：

string mystr = ["myconnstring"]；

OleDbConnection myconn = new OleDbConnection（）；

OleDbCommand mycmd1 = new OleDbCommand（）；

OleDbCommand mycmd2 = new OleDbCommand（）；

= mystr；

（）；

string mysql1 = "SELECT 教师ID FROM 课程信息 WHERE ID='"+kid+"'"；

mandText = mysql1；

= myconn；

string id = （）.ToString（）；

string mysql2 = "SELECT t"+ ti +" FROM 教师时间 WHERE 教师ID='" + id + "'"；

mandText = mysql2；

= myconn；

string flag = （）.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.