基于回溯算法制作自动排课系统.docx

基于回溯算法制作自动排课系统摘要：随着技工院校的课程改革编排课程表这项工作变得越来越复杂。如果还采用人工排课的话不仅费时费力还容易出现冲突、错漏等问题。为了有效地解决排课表问题本文采用回溯算法来解决复杂的排课表问题先创建优先级再根据优先级从高到低的进行依次编排课程。最终生成课表。回溯法方便简单易于软件实现。关键词：回溯算法自动排课应用软件中图分类号：G71文献标识码：A文章编号：1673-9795（2013）09（b）-0133-02技工院校的课表安排是一项复杂又叫人头痛的工作具体表现在以下几个方面：（1）老师、学生、场地三者要保持协调统一；（2）个别专业实行模块化教学即在一定周期内上完一门课接下来的周期再上另一门课对授课场地造成极大浪费；（3）同一个老师专业跨度大同时任教不同专业甚至跨系部如公共类课程；（4）招生规模的不稳定性使得教学设备数量无法完全满足学生需求。基于以上复杂多变的情况要想人工调整课表是极困难的。现在已有很多种自动排课系统但大多不适合技工院校的自动排课系统。其主要原因是：现在一些比较成功的自动排课系统适合中小学的课程安排。技工院校的课程多采用一体化教学模式却没有一个科学的、合理的算法解决这个排课问题。笔者在2012年采用了回溯算法制作了一个自动排课系统通过遍历搜索确定优先级然后将课程进行合理的排列从而避免发生冲突和矛盾经过三个学期的运行该系统的可行性强易操作在教学实践中发挥了重要作用。1排课基本原则如何排出科学、合理和实用的课程表呢？必须从实际出发笔者根据本校的课程安排实际情况制定了下列规则：（1）同一教师不能在同一时间节点安排两个或以上授课任务；（2）同一场地不能在同一时间节点安排两个或以上授课任务；（3）小班教室或实训室不能在同一时间节点安排两名或以上教师授课；（4）教场的工位数要大于等于上课的人数；（5）教室的类型要与课程的类型一致。如机房课与上机课、舞蹈室与舞蹈课等；（6）尽量安排实训课4节连上这符合多数一体化教学的要求；（7）尽量将文化理论课的教学安排在上午而将实训课体育课等课程安排在第3节到第6节之间；（8）尽量避免教师的连续工作即不能让一个教师在一天或连续几天内完成多个教学工作；（9）在某个特定的时间段不要安排教学任务以便教师和学生都能够利用这个时间进行一些教学工作以外的活动；（10）可根据特殊要求对特殊的教师安排特定的时间；（11）避免同一班级的同一门理论课连续出现。2基于回溯算法自动排课的核心思想回溯算法也叫试探法它是一种系统地搜索问题的解的方法。它的基本思想是：从问题的某一种状态（初始状态）出发搜索从这种状态出发所能达到的所有“状态”当一条路走到“尽头”的时候（不能再前进）再后退一步或若干步从另一种可能“状态”出发继续搜索直到所有的“路径”（状态）都试探过。这种不断“前进”、不断“回溯”寻找最优解的方法就称作“回溯法”。2.1确定优先级回溯算法在很多自动课表系统上应用较多回溯算法是排课系统寻找最优解的有效算法。根据课程安排的要求先确定优先级优先级的确定要根据专业课的安排优先于非专业课、参与班级较多的课程优先调度、阶段课程周次靠前的优先于周次靠后的、需四节连上的一体化课程优先于两节连上的课程、对时间有特殊要求的课程先调度、对教室有特殊要求的课程优先调度。根据以上原则设计了一个优先级函数为：G（x）=C1×J（x）+C2×W（x）+C3×S（x）+C4×T（x）+C5×L（x）+C6×P（x）其中G（x）表示优先级函数；J（x）表示课程的级别；W（x）表示该课程开始于第几周；S（x）表示该课程的参与班级数；T（x）表示教师承担课程的任务量；L（x）表示需特殊安排的教师；P（x）表示教室的级别；C1C2C3C4为可调整的参数由G（x）可知课程级别越高课程开始周数越靠前参与班越多教师任务越重有特殊要求的课程的优先级超高这样按优先级进行降序排序优先级高的优先处理。函数说明见表1。2.2核心算法流程确定好优先级数据后就可按回溯算法进行排课表了。在排课表过程中首先从课程数据表中取出优先级别高的课程再从教室信息表中查找合适的教室然后添加数据到课程表中并将总课节数减2或减4。如遇到固定时间的课程领导的课程应先安排。同时还要考虑教室的利用率即上课人数与教室资源的比值比值越大越好最大值为1。基本查找思路如下流程图如图1所示：（1）根据G（X）函数创建优先级并按降序转向（2）；（2）按照优先级从大到小进行排课如都排完转向（12）；否则转向（3）；（3）取出需要安排的课程数据并将课节数赋给变量S转向（4）；（4）根据课程