基于圖論的高校補(bǔ)考自動(dòng)排考算法的設(shè)計(jì)與實(shí)現(xiàn)

李瑩 陳曉華

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

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

中圖分類號(hào)：TP311? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：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背景

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

2補(bǔ)考排考分析

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

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

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

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

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

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

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

4算法描述

4.1總體思路

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

4.2算法過(guò)程

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

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

5算法實(shí)現(xiàn)

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

6結(jié)束語(yǔ)

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

參考文獻(xiàn)：

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

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

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

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