基于贪婪算法的人性化排考算法设计

作者：程媛媛

来源：《科教导刊·电子版》2014年第16期

        摘 要 本文针对在考试安排中学生考试时间尽量平均松散、监考人员监考时间尽量紧凑的不同需求，首先使用顶点着色中的贪婪算法来解决考试安排中的科目不冲突问题，然后在此基础上使用冲突链和约束函数设计出一个既简单合理又符合考生和监考人员实际需求的相对优先级较高的排考算法模型，降低了算法的复杂度。并通过在重庆交通大学的实际测试应用，证明此算法切实有效。

        关键词 不同需求 贪婪算法 冲突链 约束函数 算法模型

        中图分类号：TP393 文献标识码：A

        随着高校的扩招、办学规模的扩大，安排考试的工作量也在日益增大，考试安排已经成为学校教学管理中十分重要，必不可少的环节。考试安排是一个涉及多种因素的组合规划问题，涉及的冲突条件多，要保证在考试安排中教师、学生、教室不能产生冲突，因此是一项繁复、琐碎的工作。目前针对排考算法有很多种算法可以采用，如：遗传算法、蚁群算法等。本文在顶点着色问题的贪婪算法上进一步设计了排考算法，并使用冲突链和约束函数解决了排考问题中的各种冲突问题，降低了算法的复杂度，使考试安排结果更能满足高校师生的需求。

        1算法描述

        1.1顶点着色问题的贪婪算法介绍

        顶点着色问题可描述为：已知某简单图G有n个顶点（对各个顶点编号，依次为1、2、3......n），各顶点的关联情况已知，现对图G进行着色，满足任意关联的两个顶点具有不同的颜色，解决的问题是如何着色使总色素最少 ，最小值为多少？顶点着色问题是一个NP难题，实际工作中和管理中的很多问题都可以转化为顶点着色问题。但是，寻找顶点着色的最优解一直是数学中的一个难题，贪婪算法是求解该问题的一种有效的近似算法，具体描述如下：

        （1）对图G的n个顶点进行排列，记为V1，V2…Vn（具体构造图如图G）。

基于贪婪算法的人性化排考算法设计