基于圖論的高校補考自動排考算法的設計與實現

李瑩 陳曉華

摘要：課程補考安排是高校教務管理工作中的常規性工作，該文提出了基于圖論的自動排考算法，并設計了計算機程序，用來輔助人工排考，在實踐中進行了應用，大大提高排考效率，優化了排考方案。

關鍵詞：補考;排考;圖論

中圖分類號：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.

【通聯編輯：謝媛媛】