基于图论的高职院校补考排考算法设计

摘要：随着高职院校办学规模的扩大，为了解决补考排考人力和时间的浪费，该文采用分治法，提出了一种基于图论的高校补考排考算法，并实现了图形用户界面。在实际工作应用中，能够在几秒时间内得到满意的排考方案，显著提高了排考效率，使排考工作可以顺利且高效地完成，表明了算法的可行性。

关键词：补考；自动排考；排考算法; 图论; 图形用户界面

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

文章编号：1009-3044（2025）01-0063-02 开放科学（资源服务） 标识码（OSID） ：

0 引言

高职院校补考的安排工作是教学管理过程中的一个重要环节，随着高校的发展和招生规模的扩大，学生数量增多， 专业不断更新，课程增加，课程补考的工作量也随之增多，补考安排受到越来越多的关注[1]。排考问题属于一种NP完全问题，现阶段还没有标准的通用算法来完全解决这类难题[2-3]。补考排考与一般排考相似，均属于NP难题。目前，对于补考排考的算法研究较少，很多高校的补考排考是由人工进行补考科目、场次的安排，这种排考方法非常耗时并且可能存在学生考试科目冲突等问题，随着人数及科目的增多，手工排考的难度越来越大且极易出错。为了减轻考务人员的工作压力，提高考试管理水平，本文提出了一种高职院校补考排考算法。本算法采用分治法的思想，基于图论进行算法设计，可以辅助人工排考，极大地提升了排考的工作效率和准确度，优化排考方案，使排考结果更加灵活，更好地满足考试的需求。

1 需求分析

补考通常安排在学期初，主要是给考试不及格或者缓考的同学再次提供一次考试机会[4]。补考排考与期末排考存在显著差异，补考的学生虽然规模较小，但是时间紧、任务重，存在一位同学可能同时需要补考多门课程以及每门课程需要补考的人数也有区别等诸多复杂情况。因此，补考排考需要考虑的因素及满足的约束条件有：

1） 每位考生在同一时间段只能参加一门考试，若某考生有多门补考课程，这些课程不能安排在同一时间段。

2） 补考某一门课程的所有学生必须安排在相同时间段考试。

3） 不同课程参加补考的人数也有多有少，甚至可能一门课程只有一位同学补考，需要多门课程安排在同一考场同一时间段完成。

4） 对于补考多门课的考生安排，要注意课程之间是否存在冲突。

为了更合理地安排教学资源，满足考试要求，补考应尽可能用最短的时间，最少的场次安排完所有补考，同场次考试课程数量越多越好。根据约束条件，最重要的是要求一位考生在一个时间段只有一门考试，避免因考试科目冲突无法完成补考。人工排考要考虑诸多因素，效率低且容易出现各种问题。因此，一个高效的排考算法可以极大地提高排考的效率，提升准确率，降低时间成本，减少排考工作人员的工作量。同时，能够更好地满足师生的要求，节约教学资源，使考务工作更加信息化、智能化。

2 排考系统设计

2.1 数据预处理

对于补考考场安排，首先需要获取补考考生名单，一般包括学号、姓名、课程名称、专业班级等信息。不同学校的原始Excel表格可能包含不同内容，但都会包含基本信息。本算法系统采用Python语言进行编程实现，读取的原始数据存储于Excel文件中。为增强本系统的通用性，提高数据的处理速度，需要对原始数据进行预处理。只须将原始数据中考生的学号及补考课程名称提取出来，组成新的表格数据。同时为方便不同的原始数据读取与使用，降低对数据排列顺序的要求，对学号、补考课程名称等在表格的先后顺序没有要求，可通过本系统自动抓取相关字段。预处理可减少数据量，避免造成数据冗余，节约排考时间，提高系统的通用性及运行效率。

2.2 算法设计

随着补考规模的扩大，补考排考的复杂程度也越来越大。直接排考可能耗时较长，为了降低排考算法的复杂程度，在排考时首先采用分治法的思想，即将问题空间分解成多个子问题，分别求出各个小空间的解，再组成整个问题的解的方法。具体方法是根据补考课程将问题分解为多个子空间，再用图论算法进行排考，最后将得到的结果合并作为本次排考的最终结果。

在本文提出的排考算法中，依据图论做无向图 G=（V，E），其中V是所有顶点组成的集合，即将需要补考的每门课程构成图中的一个顶点；E表示图中所有联结顶点的边的集合，根据补考学生与课程之间的关系，若两门课程之间存在同一个学生参加补考，那么就将两顶点连接起来，即存在一条边。遍历所有的补考数据，就可得到所有结点的邻接关系，进而得到图G中的集合E。如图1所示为基于图论的课程连接关系示意图。图 G=（V，E），其中V={V1，V2，V3，V4，V5}，E={（V1，V2），（V2，V3），（V3，V4），（V4，V5），（V1，V5），（V1，V3），（V3，V5）}。从图中可以看出，若两个课程之间没有边，则可以安排在同一时间段考试。例如课程A和课程B、课程C、课程E 之间有连线，则课程A不能和这几门课程安排在同一时间段，但可以与课程D同时进行考试。

2.3 算法过程：

用 G=（V，E） 表示图，从图G中随机选取一个顶点vi，即一门补考课程。定义一个临时集合V'，将vi存放于集合V'中；再寻找与V'非关联的顶点vj，将vj存放于集合V'中，遍历集合V，直至V中没有与V'非关联的顶点。此时，V'包含可同时安排的补考课程。从图G 中删除集合V'，即删除可同时安排的补考课程，将剩余课程构成新的图G，重复循环上述操作，直至G为空集，跳出循环。最后输出最终的排考方案。

算法流程图如图2所示。

2.4 程序界面设计

Tkinter作为Python的标准图形用户界面库，可以快速地创建图形用户界面（Graphical User Interface，GUI） 应用程序[5-6]。为了提高系统的易用性，让人机交互的过程变得更加简单，使用Tkinter设计了GUI界面。使用Python进行窗口界面的布局和设计，生成程序窗口，使用了Tkinter库中的标签控件、文本框控件及按钮控件[7]，得到如图3 所示的排考场系统程序界面。

通过该程序界面，可以快速有效地实现考场的编排。使用人员可以通过点击“选择文件”按钮选择需要进行考场编排的原始Excel文件；点击“保存文件”按钮选择最终输出的排考方案要保存的位置；点击“运行”按钮系统开始考场的编排，运行完成后，系统直接将编排好的排考结果以Excel表格的形式存储于之前选择的保存位置，并且可多次重复运行，得到满意的排考方案；点击“退出”按钮退出整个系统。

3 系统测试

为测试本排考系统的实用性，选取某学校二级学院的两个补考数据进行测试。数据1含有63人次学生，27门补考课程。其中补考课程人数最少的补考课程仅一人补考，人数最多的补考课程有13人补考。补考课程最少的学生仅需补考一门课程，补考课程最多的学生有7门课程补考。从补考数据来看，因为补考课程最多的学生有7门课程补考，所以至少需要安排7场不同时间段的考试。将原始补考信息导入系统，系统运行3次，得到3种排考方案，补考场次均为7场。数据2含有153人次学生，29门补考课程。补考课程最少的学生仅需补考一门课程，补考课程最多的学生有6门课程补考。系统运行3次，得到3种排考方案，补考场次均为6场。系统运行测试结果如表1所示。

实验结果可以看出，对于不同的数据，均可以达到理想的结果。多次运行中，具体的排考方案会有差别，但没有出现考场冲突等错误，准确率达到100%。本文提出的补考排考系统的算法，其排考效果可以达到设计要求，具有较高的排考速度、准确率以及实用性，极大地提高了排考的工作效率。同时每次的随机机制，在实际应用中，增加了排考结果的多样性，增强了系统的灵活性，以方便使用人员根据各自实际情况进行细微调整，体现了人性化的思维及本系统的泛化性能。可重复运行几次，大多数情况下都会得到满意的排考方案。

4 结论

本文采用分治法的思想，提出了一种基于图论的补考排考算法，使用Python编程实现了该算法，同时为了便于工作人员使用，设计了图形用户界面。从实际出发，解决了人工排考费时费力的问题，减少了人工排考中多次核对的负担，考场安排合理，极大地提高了排考的效率，为补考排考提供了一种思路和解决方案，有很强的实用性。未来将对系统进一步改善与优化，例如尽量避免学生连续参加多场考试，能够增加更多个性化的约束条件，增加系统灵活性，使系统更加自动化、智能化。

参考文献：

[1] 龙丽婧，胡荷芬.基于人性化冲突解决算法设计模型[J].计算机与数字工程，2010，38（12）：57-61.

[2] 张洪旗，邓正杰.基于多元数据的排考系统的设计与实现[J]. 电脑知识与技术，2021，17（13）：89-92.

[3] 舒清录.基于C/S与B/S混合结构的高校智能排考系统设计与实现[J].信息技术与信息化，2020（4）：16-19.

[4] 李莹，陈晓华.基于图论的高校补考自动排考算法的设计与实现[J].电脑知识与技术，2020，16（16）：224-225.

[5] 张朋，咸庆军，陈俊旗，等.Python在扭转内力教学中的应用研究[J].现代信息科技，2023，7（22）：195-198.

[6] 冯桂尔.基于Python的GUI（Tkinter）实例开发[J].信息与电脑（理论版），2023，35（1）：175-178.

[7] 张林.基于Python的智能组卷设计[J].电子技术与软件工程，2023（3）：25-28.

【通联编辑：梁书】