基于图论的高校补考自动排考算法的设计与实现

李莹 陈晓华

摘要：课程补考安排是高校教务管理工作中的常规性工作，该文提出了基于图论的自动排考算法，并设计了计算机程序，用来辅助人工排考，在实践中进行了应用，大大提高排考效率，优化了排考方案。

关键词：补考;排考;图论

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

文章编号：1009-3044（2020）16-0224-02

Abstract：Make-up examination arrangement is a routine work in the teaching administration management of universities. This paper proposes an automatic examination arrangement algorithm based on graph theory， and designs a computer program to assist manual examination arrangement。It is applied in practice to improve the efficiency of examination arrangement and optimize the plan.

Keywords：make-upexamination;examination arrangement;graph theory

1背景

补考工作是高校教务管理工作中的常规性工作，补考一般需要合并多个科目在同一场次考试。目前，大部分高校的补考工作安排是利用学校的教务管理软件辅助完成，由人工在系统中逐门进行补考科目的安排，软件进行课程、教室、监考教师等排考要素的冲突检测。这种排考方法基本以人的随机操作与试错为主，比较耗时，不同的人排考的结果差距很大，很难评估排考方案。本文提出了基于图论的自动排考算法，可以辅助人工排考，大大提高排考效率，优化排考方案。

2补考排考分析

补考一般在学期初进行，对上学期期末考试不及格或者申请缓考的同学，再增加一次考试机会。补考与正考相比，涉及的补考课程多，每门课补考的学生少，每名学生的补考课程从数量到科目差异较大，补考安排时间高度集中，以便尽快结束考试，教师阅卷后及时录入补考成绩，为开学后的选课、学籍处理等工作做好准备。为节省教学资源，同场次考试尽可能排进较多的补考课程，用最少的场次来完成补考工作。根据补考的这些特点，排考的主要约束条件在于同一时间段内，一个考生只能有一场考试，否则，会产生冲突，学生无法参加考试。

3数据映射图

3.1数据E-R模型

补考数据的数据源多种多样，有的是数据库表，有的是Excel文件形式的表，无论何种形式的数据，无论数据结构如何，我们都可以将补考数据进行分解，抽象得到最简化的实体-关系概念模型如图1：

3.2創建数据冲突图

图论在各行各业的工程实践中应用广泛，图论通过点和线组成的图形来模拟现实世界的问题，并可根据图的性质进行邻接、连通、成本、规模、规划、冲突等分析研究，为不同的研究领域提供了科学工具。

在解决排考问题中，我们依据数据E-R模型及实例数据，做无向简单图G=;其中V是结点集合，由课程实体中的数据构成，每门课程构成图中的一个结点;E是联结结点的边的集合，由学生-课程关系映射得到，也就是在概念模型中的“补考”关系中找到某一位学生需要补考的所有课程，这些课程全部两两具有邻接关系，每一个领接关系构成一条边;遍历所有学生数据，得到全部课程的邻接关系，构成G中边的集合E。

4算法描述

4.1总体思路

算法的目标是在G=中，把可以排在同一场次的课程结点涂上相同的颜色。首先第一步选择G中度数最大的结点Vi，涂上颜色;选择与Vi无关联的点构成集合Vk，删除全部与结点Vi关联的边，Vi=0;然后对于Vk中的结点集合，在G中重复上述第一步操作，直至Vk为空。此时未涂色的结点与留下的边构成图Gw，Gw=，Gw[?]G;在Gw中重复第一步的操作，直到整个Vw为空，此时，G中的全部端点都被染上颜色，所有的边都被删除，端点颜色相同的结点所代表的课程，可以排在同一场次考试。

4.2算法过程

说明：本算法中的“=“表示赋值操作，”==“表示相等。

算法结束后，集合Vs==V，E=[?，]全部的结点涂完颜色，颜色填涂相同的结点在G的原图中不邻接，也即学生的考试时间不会冲突，可以安排在同一场次考试。

5算法实现

各高校可以依据本校的数据格式及编程工具使用掌握情况，选择不用的平台和开发工具，利用不同的数据结构，实现排考算法。我们从学校教务系统下载学生补考excel表数据， 依照E-R模型整理数据为三个表页，分别为学生信息表、课程信息表、学生-课程关系表，以这三张表页中的数据作为源数据，在VBA编写程序，实现上述排考算法。

6结束语

本文提出的基于图论的排考算法，解决了大数据量下高校人工逐门排补考的不确定性，减轻了排考人员的工作量，在实际应用中，提高了排考效率，优化了考试方案，为自动排补考提供了一种思路和解决方案。

参考文献：

[1] 田岭. 大学自动排考算法设计与实现[J]. 计算机工程与设计， 2007， 28（10）： 2443-2445.

[2] 张健. 基于图论的高校排课系统实现[J]. 重庆师范大学学报（自然科学版）， 2005， 22（1）： 35-38.

[3] 王东. 高校补考自动排考算法的设计与实现[J]. 贵州师范学院学报， 2012， 28（12）： 20-22.

【通联编辑：谢媛媛】