第２３卷第３期 连云港职业技术学院学报 Ｖｏ１．２３ Ｎｏ．３ ２０１０年９月 Ｊｏｕｒｎａｌ ｏｆ Ｌｉａｎｙｕｎｇａｎｇ Ｔｅｃｈｎｉｃａｌ ＣｏＨｅｇｅ Ｓｅｐｔ．２０１０ 文章编号：１００９—４３１８（２ＯＬＯ）Ｏ３一ｏｏ２１—０２ 关联规则排课算法的研究与实现 王振 （连云港职业技术学院，江苏连云港２２２００６） 摘要：使用关联规则算法描述自动排课问题的实现步骤，并进行了排课的需求分析，结合高校教务管理系统对排课问 题的需求，设计出适合高校课程的智能编排，算法简单，易于实现，具有一定的实用性。 关键词：关联规则；排课；算法；数据库 中图分类号：Ｇ４７３．４ 文献标识码：Ａ 排课是将课程、教师和学生在合适的时间段内分配到合 （ｓｉ）Ｈ（Ａ（ｔ）Ｈ）；对于每门课程有一个可安排时间集Ａ（１）Ｈ 适的教室。排课工作在教学管理中很重要也很繁琐，计算机 （集合中含Ｉｌｌ【个元素），对于每一个门课程有一个场地集ｒ（１） 自动排课系统，可以降低排课人员的工作量，减少排课中的 Ｒ（其包含有ｎｋ个元素），并且对于每一个四元组（Ｓｉ，ｔ，ｌ，ｒ）∈ 人为因素。但排课问题早在上课世纪７０年代就证明是一个 Ｓ×Ｔ×Ｌ×Ｒ，有一个“要求教学时间数目”ｘ（Ｓｉ，ｔ，ｌ，ｒ）∈ｚ＋０ ＮＰ问题，即算法的计算时间是呈指数增长的，这一论断确立 （ｚ＋０表示非负整数集）。且ｘ（ｓｉ，ｔ，ｌ，ｒ）Ａ（１）。要排定课表， 了排课问题的理论深度。通常ＮＰ问题虽无答案，却有算法， 即求函数ｆ（ ，ｔ，１，ｒ，ｈ）一｛０，ｌ｝（其中ｆ（ｓｊ，ｔ，ｌ，ｒ，ｈ）＝１表示 算法不能直接告诉答案，但可以用来判断可能的结果是否正 班级ｓｉ，教师ｔ，在时间ｈ内，场地ｒ上课程１）。 确可行。因此，要做好排课工作，提高排课效率，研究排课算 课表排定应满足： 法是必不可少的。 ①给定ｓｉ时，第一门课程排定时应满足：ｈｉ６ Ｈ（在整个 本文采用关联规则算法作为排课管理子系统的设计方 教学时间内抽取随机时间点）。取ｌｉ∈Ｌ使得Ａ（１ｉ）＝ 法。通过实验，证明关联规则算法在减少人工干预排课次 Ｈｉａｘ｛Ａ（１）ｌ在整个Ａ（Ｓｉ）＝Ｈ内使ｆ（Ｓｉ，ｔ，ｌ，Ｉｔ＂，ｈ）＝１。以后课 数、在时间和教室的利用、尽量满足约束条件、班级和教师的 程的排定则循环：ｌｊ（ｊ＃ｉ），Ａ（ ）＝ｒ嗽｛Ａ（１）一Ａ（１ｉ）｝（每排出 同负荷均衡等方面，能够产生很好的效果，大大提高了排课 －ｆ－］课程ｈｎ，Ａ（１ｊ）为原｛Ａ（Ｉ）｝除去已排课程Ａ（１ｍ））。在Ａ 效率。 （ｓｉ）＝Ｈ—Ａ（１ｉ）（每排出一门课程ｌｍ，Ａ（Ｓｉ）为原Ｈ除去Ａ １关联规则排课算法实现 （１ＩＩ１））中使ｆ（ｓｉ，ｔ，１，ｒ，ｈ）＝１，直至Ａ（ｓｉ）＝０，其中ｆ（Ｓｉ，ｔ，１，ｒ， １．１算法框架描述 ｈ）＝１仅需ｓｉ∈ｓ，ｔ∈Ｔ，ｌ∈Ｌ，ｈＥＨ，ｒＥＲ。 该算法由以下几个主要的过程组成： ②对于ｉ∈［Ｉ，璐］，Ｓｉ依次循环步骤①，直至Ａ（Ｓｉ）＝ （１）系统数据初始化，形成本期教学信息二维数据库； Ｏ（ｉ∈［１，舾］）。 （包含数据属性、条件属性及信息编码等）。 （２）资源冲突的处理 （２）课程定位，按照预排算法，形成无任何决策信息的课 按权均值算法，使得每个班级排定课表更自动，高效。 表样本视图。 但由于制约条件多，各班级初次混排的课表中按权均值算法 （３）按构建规则对课表样本库进行课表混排。 并没有解决资源冲突问题。该系统采用了第二个子算法对 （４）用ＦＰ—ｇｒｏｗｔｈ算法定位课表混排库中出现的冲突。 该问题进行处理：查找和定位课表中的冲突元素，对冲突元 （５）按优先处理冲突计数值最高元素的原则消除冲突。 素按其冲突次数值降序排列，并将各个班级的冲突元素集生 （６）系统综合检测原始信息和约束条件，输出结果。 成相应的冲突树，再对树进行遍历查找，按照冲突最高的元 １．２算法描述 素优先处理原则进行处理，直至冲突树的节点为空。即采用 虽然排定课表问题及其复杂，但可以采用一种分而治之 关联规则思想，使得该系统能高效、正确地排出满足所有约 的观点来看待它。将其分为两个不同的部分，分阶段来解决 束条件的课表，使算法更具智能化。 它。即将排课算法分为两个子算法：按权均值算法排定基本 输入：混排课表数据库Ｄ。 课表；通过建立冲突树对资源冲突进行处理算法。 ‘ 输出：以冲突计数值降序排列的冲突元素集。 （１）基本课表的排定 方法： 设“可安排教学时间集”为Ｈ，“班级集”为ｓ（１ ｓｆ＿Ｔｌｓ）， ①扫描数据库Ｄ，查找冲突元素 并计数（这里的下标 “教师集”为Ｔ，“课程集”为Ｌ（ＩＬＩ＝ｎｋ），“场地集”为Ｒ。 用于对冲突元素ｃ定位）；按冲突计数值降序排列冲突元素 对于每个班级ｓｉ（教师ｔＥ Ｔ），有一个“未排定时间集”Ａ 存入Ｌ表中； ｝收稿日期：２０１０—０９一Ｏ１ ・ ２２ ・ Ｌ＝｝ＣＩｌ，Ｃ１２，…， ，…，Ｃｎｍ｝ 连云港职业技术学院学报 ２０１０年第３期 且较适于开发高校排课的实际要求，所以本排课系统选择关 联规则算法。采用具有智能概念的关联规则算法思想设计 ②创建ＦＰ—ｔｒｅｅ的根节点标记为ｎｕｌｌ，对每一个班级的 课表执行如下操作： 依据Ｌ中的冲突元素及其顺序对每个班课表中的ｃ 作 选择和排序操作；形成各班课表的冲突元素集Ｔｒａｎ：ａＩＡ。 这里的ａ是Ｔｒａｎ中的第一个元素，Ａ是Ｔｒａｎ的剩余部分；调 的按权均值随机排课算法方案，比常规的递归排序方法设计 的方案效率提高近ｌ０倍，显著提高了系统效率。排课流程 如图１所示。 ２关联规则排课算法的数据库结构 用ｉｎｓｅｒｔ—ｔｒｅｅ（ａｌＡ，Ｔｒａｎ）过程将Ｔｒａｎ中的元素加入到ＦＰ— ｔｒｅｅ中。如果Ｔｒａｎ中有一个分枝Ｎ，它的节点名与ａ相同，则 该算法建立了一个数据库，所有具体的数据项都以表的 形式存放在该数据库中。这些表中包括：班级信息表、教师 对Ｎ的计数值加１，否则为Ｔｒａｎ创建一个新的分枝Ｎ，该Ｎ中 各节点的计数值为１；如果Ａ非空，再次调用ｉｎｓｅｒｔ—ｔｒｅｅ（Ａ， 信息表、课程信息表、教室信息表、时间模式表，还有两个代 码表分别记录教师和课程、班级课程和周课时量。根据对排 课问题的求解方法，定义数据库Ｅ—Ｒ图，如图２所示。 Ｎ）过程处理。与遗传算法、蚁群算法等相比，ＦＰ—Ｇｒｏｗｔｈ算 法是所有搜索算法中最为基本的一种算法，相对比较简单， 图ｌ排课算法流程图 图２关联规则排课算法Ｅ—Ｒ图 采用本算法开发高校自动排课系统并进行排课，各种约 束条件都得到了满足，而且时间分配比较均匀，课表比较科 学合理，可以满足配课系统的优化实现。 参考文献： 根据数据流图分析，得到如下结果： （１）数据模型实体 系统中包含的数据模型实体主要有：班级、课程、教师、 教室。 其实体属性包含以下内容。 ①班级：班级编号、班级人数、所属专业、所属年级。 ②课程：课程编号、课程名称、课程性质、考查方式、学 分、总学时、周学时。 ③教师：教师编号、教师姓名、教师所属教研室、教师简 介、周课时量。 ④教室：教室编号、教室名称、教室类型、教室容量。 ［１］ 李力东，王春光．基于遗传算法的自动排课问题的研究 ［Ｊ］．农业与技术，２００９，（６）：１８０～１８３． ［２］ 彭复明．基于矩阵优化的机房自动排课算法［Ｊ］．中国 制造业信息化，２００９，（２１）：５２—５４． ［３］马虹，施正一．教师排课的数学优化模型的研究［Ｊ】．中 国科教创新导刊，２００８，（３３）：１８５—１８７． （２）数据字典及数据表的构造 基本信息设置需要１Ｏ个数据表，有班级信息表、上课时 间表、课程信息表教师信息表、教室信息表、教研室信息录入 表、管理员表、用户表、两个代码表分别记录教师与课程和教 室与课程。 ３结束语 ［４］ 高峰，谢剑英．多值属性关联规则的理论基础［Ｊ］．计算 机工程，２０００，（１】）：４７—４９． 作者简介：王振（１９８１一），男，江苏连云港人，连云港职业技 术学院信息工程学院教师。主要从事计算机应用技术研究。 Ｒｅｓｅａｒｃｈ ａｎｄ Ｐｒａｃｔｉｃｅ ｏｆ Ｃｏｕｒｓｅ Ｓｃｈｅｄｕｌｉｎｇ Ａｌｇｏｒｉｔｈｍ ｔｈｒｏｕｇｈ Ａｓｓｏｃｉａｔｉｏｎ Ｒｕｌｅｓ Ｗ＿ＡＮＧ Ｚｈｅｎ （Ｌｉａｎｙｕｎｇａｎｇ Ｔｅｃｈｎｉｃａｌ Ｃｏｌｌｅｇｅ，Ｌｉａｎｙｕｎｇａｎｇ ２２２００６，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｅ ａｌｇｏｒｉｔｈｍ ｔｈｒｏｕｇｈ ａｓｓｏｃｉａｔｉｏｎ ｍｌｅｓ ｉｓ ｕｓｅｄ ｔｏ ｄｅｓｃｒｉｂｅ ｔｈｅ ｐｒｏｃｅｓｓ ｏｆ ｃｏｕｒｓｅ ｓｃｈｅｄｕｌｉｎｇ．Ｍｅａｎｗｈｉｌｅ ｉｔｓ ｄｅ－ ｍａｎｄ ａｎａｌｙｓｉｓ ｉｓ ｍａｄｅ ａｓｓｏｃｉａｔｅｄ ｗｉｔｈ ｔｈｅ ｃｏｌｌｅｇｅ ｔｅａｃｈｉｎｇ ｍａｎａｇｅｍｅｎｔ ｓｙｓｔｅｍ ｎｄ ｔａｈｅ ｉｎｔｅｌｌｉｇｅｎｔ ｓｃｈｅｄｕｌｉｎｇ ｓｕｉｔａｂｌｅ ｆｏｒ ｃｏｌｌｇｅ ｃｏｕｒｅｓｅｓ ｉｓ ｄｅｓｉｇｎｅｄ，ｗｈｉｃｈ ｉｓ ｅａｓｙ ｔｏ ＵＳｅ ａｎｄ ｐｒａｃｔｉｃａｌ ｔｏ ｓｏｍｅ ｄｅｇｒｅｅ． Ｋｅｙ ｗｏｒｄｓ：ａｓｓｏｃｉａｔｉｏｎ ｒｕｌｅｓ；ｃｏｕｒｓｅ ｓｃｈｅｄｕｌｉｎｇ；ａｌｇｏｒｉｔｈｍ；ｄａｔａｂａｓｅ
