研究与开发 文章编号：１００７－１４２３（２０１４）３５—００１７—０４ ＤＯＩ：１０．３９６９／ｊ．ｉｓｓｎ．１００７—１４２３．２０１４．３５．００４ 高校自动排课系统算法比较分析 郭亮，余燕，许雅琳，刘倩，莫露 （西华师范大学计算机学院，南充６３７００９） 摘要： 课程表的编排是高校教务管理中最为重要和复杂的一项工作。通过对几种自动排课算法的合理比较，统筹分析出各 自的优劣，得出贪婪算法的综合适用性是最优的结论。在此基础之上，进一步分析贪婪算法是如何逐步解决排课的现 实问题．并给出基于贪婪算法的自动排课系统算法的具体实现过程。 关键词： 自动排课；贪婪算法；遗传算法；回溯算法；算法复杂度 基金项目： 西华师范大学大学生科技创新基金项目（Ｎｏ．４２７１３０６３） Ｏ 引言 在高校的教学管理中．教季计划和教学质量无疑 是最主要的两个因素。而在教学实施之前．为了保证教 学目的论质论量的实现．排课计划更是其有效进行的 关键点．由此可知排课计划在整个教育教学中举足轻 提高了后续的教学质量．也为教学工作奠定了强有力 的基础。 目前国内外关于教学排课系统实现的算法较多． 主要有遗传算法、贪婪算法、回溯算法、蚁群算法和模 拟退火算法等【１］．以下主要分析了本文中将进行比较的 重的位置 然而。排课计划的制定不仅涉及到教师、教室、班 级、课程，而且与教室使用情况、教师课表、班级课表等 多种实体因素相关。这一系列的因素造成的约束过多， 使得手工编排课程表工程量浩大．编排过程复杂．而且 课程表不易于改动．不具有实用价值。随着时代与科技 的进步．为了统筹各相关要素之间的衔接关系．各种排 三种算法： （１）遗传算法（Ｇｅｎｅｔｉｃ Ａｌｇｏｒｉｔｈｍ） 遗传算法是模拟达尔文生物进化论的自然选择 “物竞天择”和遗传学机理的生物进化过程的计算模 型．它是一种通过模拟自然进化过程搜索最优解的算 法闭。换言之，在这个算法中首先生成一组候选解，根据 约束条件调整某些候选解，生成新的一组候选解，如此 循环得到最终的最优解 课算法的实现与改进是很有用也很有必要的．其为如 今的高校排课系统做出了卓越贡献。 （２）贪婪算法（Ｇｒｅｅｄｙ Ａｌｇｏｒｉｔｈｎ１） 贪婪算法也叫贪心算法．是一种对某些求最优解 问题的更简单、更迅速的设计技术［１】。它是指解决排课 问题的时候．不会最初就考虑整体的最优，而是采用了 一１ 现状与排课算法分析 现阶段．国内大多数高校仍然采用的是人工排课， 这种方式效率低、工作量冗杂，并且也容易产生遗漏和 教学资源的多层次冲突．最终产生的排课效果也是差 强人意。合理地使用排课算法来初步编排课程表．进而 进行人工微调．这样不仅在提高教学计划制定的同时 种改进的分级处理方法．依次逐步构造出最优解。也 就是说．把要解决的问题分解为一系列模块，化整体为 局部．通过满足各个局部最优的方式来逐步逼近最终 目标．求得整个问题的最优解围。当算法中的某一步不 能再继续前进时则停止．并且在算法过程中某些情况 现代计算机 ２０１４．１２中 ＼＼＼ 竺 下无法取得最优解．但是也能得到相对更好的解。 （３）回溯算法（Ｂａｃｋ—Ｔｒａｃｋ Ａｌｇｏｒｉｔｈｍ） 回溯算法也叫试探法．它是一种系统地搜索问题 的解的方法 。它的算法与贪婪算法的过程相逆，其采 用了一种“走不通就掉头”思想作为其控制结构。它解 决问题的思路是先选择某一可能的线索进行试探，每 一步试探都有多种方式．将每一方式都一一试探．如有 问题就返回纠正．反复进行这种试探再返回纠正．直到 得出全部符合条件的答案或是问题无解为止 ２ 排课算法比较分析 正如我们以上所提及到的．排课系统中涉及的算 法确实有很多种．但是由于每一种算法都有自身的突 出优点和条件．至今仍然没有一种算法能适用于 所有高校的排课计划．以下我们将从算法与实现复杂 度来比较贪婪算法、遗传算法以及回溯算法： （１）算法复杂度 贪婪算法是一种最为直接的排课算法技术．可以 产生整体最优解 具体来说．通常所求问题的最优解是 从贪婪选择开始的．而且每做一步选择之后．原问题可 简化成一个相对规模更小的子问题．经过多次贪婪选 择，最终得到最优解。例如简单的删数问题中：将正整 数１７８５４３删除任意４个数字后．算出可得到的最小 数。采用贪婪算法来解决问题的思路是：首先第一步贪 婪选择去删除最大数字８．再依次进行３次贪婪选择． 将整数逐步简化成更小的最终得到问题的最优解１３。 可见这种算法思维复杂度低．代码量小．空间复杂度较 低，便于问题的理解和实施。 遗传算法具有良好的全局搜索能力．可以快速地 将解空间中的全体解搜索出．而不会陷入局部最优解 的快速下降陷阱；并且利用它的内在并行性．可以方便 地进行分布式计算．加快求解速度阁 在上文的删数问 题中．采用遗传算法首先用简单的两两组合来生成初 始种群ｆ１７，８５，４３ｌ，根据适应度函数淘汰ｆ８５ｌ，通过交 叉，再生成新的种群组成一组新候选解ｆｌ７，ｌ４，１３， ７４，７３，４３１，采用“优胜劣汰”最终得到最优解｛１３ｌ。这种 算法的实现能快速随机地搜索整体解集．具有可扩展 性，但相对贪婪算法来说代码量较大．编程实现比较复 杂．且对初始解集的选择有很强的依赖性 回溯算法的解题思路可以被认为是一个有过剪枝 ＠ 现代计算机２０１４．１２中 的ＤＦＳ（深度优先搜索）过程。与贪婪算法相逆，首先它 会按优先条件向前搜索．以达到目标．但当搜索到某一 步时．发现原先的路径并不优或者达不到目标，就往回 退一步重新进行选择以得到最优解。在之前的删数问 题中，回溯算法可很快得到最优解是｛１３ｌ，因为问题中 的ｌ是最优先条件（最小数），向前搜索可很快得出问 题的最优解。此算法结构清晰，类似于数学知识中的归 纳证明．所有调试程序比较方便。但如果针对复杂的问 题要存储全部解空间的话．再多的空问也不够用．时间 复杂度和空间复杂度均较大．不利于处理多数高校的 复杂排课问题 ｆ２）实现复杂度 一般来说．使用排课算法编排课程表有很多约束 条件．在排课中绝对不能发生的事情属于最基本的约 束，从硬约束方面：一个教室在同一时间只能安排一门 课程：一个学生在同一时间只能上一门课程：一个教师 在同一时间只能教授一门课程等：从软约束方面：课程 因为特殊原因的调节、教室因为临时暂用的分配等也 是需要排课系统考虑实现的 基于此．排课系统使用的 算法应易于更改。方便协调，编程代码尽量简单。然而 如今已有的排课算法并未完全克服这些弊端和不足 贪婪算法的缺点集中表现在针对某复杂的排课体 系来说．通常很难找到一个简单可行并且保证完全正 确完全简易的贪心思路：贪婪算法也缺乏考虑整体最 优的考虑．不是对所有问题都能得到整体最优解．但是 这种算法对范围很广、许多问题都能得出整体最优解 或是近似解［３１ 就遗传算法来看．本身实现较为复杂．附加排课问 题的约束条件之后．其算法的效率较低．当遇到排课要 求十分严格的话．极有可能造成未知解：此算法的程序 编码往往不能很好地联系排课的理论实际．操作较为 不方便：算法倾向于对求解问题的边界定义考虑排课 一般条件的情况．实用程度相对较低．在现今的高校排 课系统中的引用率也相比贪婪算法要低 而回溯算法的算法思路是得出预计最优解空间． 可读性强。当排课系统中的约束条件清楚．排课资源简 单可按照图或树的形式进行回溯达到最优解：但从其 算法思路可得知如果排课资源复杂或规模过大时．排 课工程量巨大．效率极低．且不易满足多种约束条件或 是满足程度不够．从而排除的课程表适应度较低．常常 ＼＼＼＼ １ 情况．选择在基于贪婪算法上的排课系统来实现西华 师范大学的办公自动化排课。 ４ 结语 本文通过对贪婪算法、遗传算法及回溯算法的相 关比较和分析．并结合普通高等院校教学管理的实际 参考文献： 『１１聂小东，基于贪婪算法的排课系统的研究与实现，广东工业大学工学硕士学位论文，２００６．４ 【２】范文广，基于遗传算法的排课设计［Ｊ］，齐齐哈尔大学学报，２０１１，２７（５） 『３１刘明，贪婪算法在排课问题中分析与应用ｆＪ１．信息与电脑，２０１２．１ １杨建。基于优先级回溯算法的高校排课系统设计与实现，华中科技大学硕士学位论文，２０１２．７ 【５】韦玉，冯速．免疫遗传算法在排课问题中的应用［Ｊ］．北京师范大学学报（自然科学版），２００８，４４（２） 作者简介： 郭亮（１９９４一），男，四川南充人，本科，就读专业为计算机科学与技术 余燕（１９９１一），女，四川自贡人，本科，就读专业为计算机科学与技术 许雅琳（１９９３一），女，四川Ｉ达州人，本科，就读专业为计算机科学与技术 刘倩（１９９２一），女，四川遂宁人，本科，就读专业为计算机科学与技术 莫露（１９９２一），女，四川Ｉ广安人，本科，就读专业为计算机科学与技术 收稿日期：２０１４—１１－１１ 修稿日期：２０１４一ｌ１—１９ Ｃｏｍｐａｒｉｓｏｎ ａｎｄ Ａｎａｌｙｓｉｓ ｏｆ Ａｕｔｏｍａｔｉｃ Ｃｏｕｒｓｅｓ Ａｒｒａｎｇｅｍｅｎｔ Ｓｙｓｔｅｍ Ａｌｇｏｒｉｔｈｍｓ ｉｎ Ｕｎｉｖｅｒｓｉｔｙ ＧＵＯ Ｌｉａｎｇ，ＹＵ Ｙａｎ，ＸＵ Ｙａ－ｌｉｎ，ＬＩＵ Ｑｉａｎ，ＭＯ Ｌｕ （Ｓｃｈｏｏｌ ｏｆ Ｃｏｍｐｕｔｅｒ，Ｃｈｉｎａ Ｗｅｓｔ Ｎｏｒｍａｌ Ｕｎｉｖｅｒｓｉｔｙ，Ｎａｎｃｈｏｎｇ ６３７００９） Ａｂｓｔｒａｃｔ： Ｃｏｕｒｓｅ ａｒｒａｎｇｅｍｅｎｔ ｉｓ ｏｎｅ ｏｆ ｔｈｅ ｍｏｓｔ ｉｍｐｏｒｔａｎｔ ａｎｄ ｃｏｍｐｌｅｘ ｗｏｒｋ ｉｎ ｔｈｅ ｕｎｉｖｅｒｓｉｔｙ ｅｄｕｃａｔｉｏｎａｌ ｍａｎａｇｅｍｅｎｔ．Ｃｏｍｐａｒｅｓ ａｎｄ ａｎａｌｙｚｅｓ ｓｅｖｅｒａｌ ａｌｇｏｒｉｔｈｍｓ ｉｎ ｃｏｕｒｓｅ ａｒｒａｎｇｅｍｅｎｔ ｃａｒｅｆｕｌｌｙ，ａｎｄ ｄｒａｗｓ ａ ｃｏｎｃｌｕｓｉｏｎ ｔｈａｔ ｇｒｅｅｄｙ ａｌｇｏｒｉｔｈｍ ｉｓ ｍｏｒｅ ｓｕｉｔａｂｌｅ ｆｏｒ ｃｏｍｐｒｅｈｅｎｓｉｖｅ ａｐ— ｐｌｉｃａｂｉｌｉｔｙ．Ｆｕｒｔｈｅｒ ａｎａｌｙｚｅｓ ｏｆ ｔｈｅ ｇｒｅｅｄｙ ａｌｇｏｒｉｔｈｍ ｔｈａｔ ｈｏｗ ｔｏ ｇｒａｄｕａｌｌｙ ｓｏｌｖｅ ｐｒａｃｔｉｃａｌ ｐｒｏｂｌｅｍｓ ｉｎ ａｒｒａｎｇｉｎｇ ｃｏｕｒｓｅｓ ａｎｄ ｐｒｅｓｅｎｔｓ ｔｈｅ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｐｒｏｃｅｓｓ ｉｎ ｓｃｈｅｄｕｌｉｎｇ ｓｙｓｔｅｍ ｂａｓｅｄ ｏｎ ｇｒｅｅｄｙ ａｌｇｏｒｉｔｈｍ． Ｋｅｙｗｏｒｄｓ： Ａｕｔｏｍａｔｉｃ Ｃｏｕｒｓｅｓ Ａｒｒａｎｇｅｍｅｎｔ；Ｇｒｅｅｄｙ Ａｌｇｏｒｉｔｈｍ；Ｇｅｎｅｔｉｃ Ａｌｇｏｒｉｔｈｍ；Ｂａｃｋ—Ｔｒａｃｋ Ａｌｇｏｒｉｔｈｍ；Ａｌｇｏｒｉｔｈｍ Ｃｏｍｐｌｅｘｉｔｙ ④ 现代计算机２０１４．１２中
