李瑩 陳曉華

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

關(guān)鍵詞：補考;排考;圖論

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

補考工作是高校教務(wù)管理工作中的常規(guī)性工作，補考一般需要合并多個科目在同一場次考試。目前，大部分高校的補考工作安排是利用學校的教務(wù)管理軟件輔助完成，由人工在系統(tǒng)中逐門進行補考科目的安排，軟件進行課程、教室、監(jiān)考教師等排考要素的沖突檢測。這種排考方法基本以人的隨機操作與試錯為主，比較耗時，不同的人排考的結(jié)果差距很大，很難評估排考方案。本文提出了基于圖論的自動排考算法，可以輔助人工排考，大大提高排考效率，優(yōu)化排考方案。

2補考排考分析

補考一般在學期初進行，對上學期期末考試不及格或者申請緩考的同學，再增加一次考試機會。補考與正考相比，涉及的補考課程多，每門課補考的學生少，每名學生的補考課程從數(shù)量到科目差異較大，補考安排時間高度集中，以便盡快結(jié)束考試，教師閱卷后及時錄入補考成績，為開學后的選課、學籍處理等工作做好準備。為節(jié)省教學資源，同場次考試盡可能排進較多的補考課程，用最少的場次來完成補考工作。根據(jù)補考的這些特點，排考的主要約束條件在于同一時間段內(nèi)，一個考生只能有一場考試，否則，會產(chǎn)生沖突，學生無法參加考試。

3數(shù)據(jù)映射圖

3.1數(shù)據(jù)E-R模型

補考數(shù)據(jù)的數(shù)據(jù)源多種多樣，有的是數(shù)據(jù)庫表，有的是Excel文件形式的表，無論何種形式的數(shù)據(jù)，無論數(shù)據(jù)結(jié)構(gòu)如何，我們都可以將補考數(shù)據(jù)進行分解，抽象得到最簡化的實體-關(guān)系概念模型如圖1：

3.2創(chuàng)建數(shù)據(jù)沖突圖

圖論在各行各業(yè)的工程實踐中應(yīng)用廣泛，圖論通過點和線組成的圖形來模擬現(xiàn)實世界的問題，并可根據(jù)圖的性質(zhì)進行鄰接、連通、成本、規(guī)模、規(guī)劃、沖突等分析研究，為不同的研究領(lǐng)域提供了科學工具。

在解決排考問題中，我們依據(jù)數(shù)據(jù)E-R模型及實例數(shù)據(jù)，做無向簡單圖G=;其中V是結(jié)點集合，由課程實體中的數(shù)據(jù)構(gòu)成，每門課程構(gòu)成圖中的一個結(jié)點;E是聯(lián)結(jié)結(jié)點的邊的集合，由學生-課程關(guān)系映射得到，也就是在概念模型中的“補考”關(guān)系中找到某一位學生需要補考的所有課程，這些課程全部兩兩具有鄰接關(guān)系，每一個領(lǐng)接關(guān)系構(gòu)成一條邊;遍歷所有學生數(shù)據(jù)，得到全部課程的鄰接關(guān)系，構(gòu)成G中邊的集合E。

4算法描述

4.1總體思路

算法的目標是在G=中，把可以排在同一場次的課程結(jié)點涂上相同的顏色。首先第一步選擇G中度數(shù)最大的結(jié)點Vi，涂上顏色;選擇與Vi無關(guān)聯(lián)的點構(gòu)成集合Vk，刪除全部與結(jié)點Vi關(guān)聯(lián)的邊，Vi=0;然后對于Vk中的結(jié)點集合，在G中重復(fù)上述第一步操作，直至Vk為空。此時未涂色的結(jié)點與留下的邊構(gòu)成圖Gw，Gw=，Gw[?]G;在Gw中重復(fù)第一步的操作，直到整個Vw為空，此時，G中的全部端點都被染上顏色，所有的邊都被刪除，端點顏色相同的結(jié)點所代表的課程，可以排在同一場次考試。

4.2算法過程

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

算法結(jié)束后，集合Vs==V，E=[?，]全部的結(jié)點涂完顏色，顏色填涂相同的結(jié)點在G的原圖中不鄰接，也即學生的考試時間不會沖突，可以安排在同一場次考試。

5算法實現(xiàn)

各高?？梢砸罁?jù)本校的數(shù)據(jù)格式及編程工具使用掌握情況，選擇不用的平臺和開發(fā)工具，利用不同的數(shù)據(jù)結(jié)構(gòu)，實現(xiàn)排考算法。我們從學校教務(wù)系統(tǒng)下載學生補考excel表數(shù)據(jù)， 依照E-R模型整理數(shù)據(jù)為三個表頁，分別為學生信息表、課程信息表、學生-課程關(guān)系表，以這三張表頁中的數(shù)據(jù)作為源數(shù)據(jù)，在VBA編寫程序，實現(xiàn)上述排考算法。

6結(jié)束語

本文提出的基于圖論的排考算法，解決了大數(shù)據(jù)量下高校人工逐門排補考的不確定性，減輕了排考人員的工作量，在實際應(yīng)用中，提高了排考效率，優(yōu)化了考試方案，為自動排補考提供了一種思路和解決方案。

參考文獻：

[1] 田嶺. 大學自動排考算法設(shè)計與實現(xiàn)[J]. 計算機工程與設(shè)計， 2007， 28（10）： 2443-2445.

[2] 張健. 基于圖論的高校排課系統(tǒng)實現(xiàn)[J]. 重慶師范大學學報（自然科學版）， 2005， 22（1）： 35-38.

[3] 王東. 高校補考自動排考算法的設(shè)計與實現(xiàn)[J]. 貴州師范學院學報， 2012， 28（12）： 20-22.

【通聯(lián)編輯：謝媛媛】