基于圖論的高職院校補(bǔ)考排考算法設(shè)計

摘要：隨著高職院校辦學(xué)規(guī)模的擴(kuò)大，為了解決補(bǔ)考排考人力和時間的浪費，該文采用分治法，提出了一種基于圖論的高校補(bǔ)考排考算法，并實現(xiàn)了圖形用戶界面。在實際工作應(yīng)用中，能夠在幾秒時間內(nèi)得到滿意的排考方案，顯著提高了排考效率，使排考工作可以順利且高效地完成，表明了算法的可行性。

關(guān)鍵詞：補(bǔ)考；自動排考；排考算法; 圖論; 圖形用戶界面

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

文章編號：1009-3044（2025）01-0063-02 開放科學(xué)（資源服務(wù)） 標(biāo)識碼（OSID） ：

0 引言

高職院校補(bǔ)考的安排工作是教學(xué)管理過程中的一個重要環(huán)節(jié)，隨著高校的發(fā)展和招生規(guī)模的擴(kuò)大，學(xué)生數(shù)量增多， 專業(yè)不斷更新，課程增加，課程補(bǔ)考的工作量也隨之增多，補(bǔ)考安排受到越來越多的關(guān)注[1]。排考問題屬于一種NP完全問題，現(xiàn)階段還沒有標(biāo)準(zhǔn)的通用算法來完全解決這類難題[2-3]。補(bǔ)考排考與一般排考相似，均屬于NP難題。目前，對于補(bǔ)考排考的算法研究較少，很多高校的補(bǔ)考排考是由人工進(jìn)行補(bǔ)考科目、場次的安排，這種排考方法非常耗時并且可能存在學(xué)生考試科目沖突等問題，隨著人數(shù)及科目的增多，手工排考的難度越來越大且極易出錯。為了減輕考務(wù)人員的工作壓力，提高考試管理水平，本文提出了一種高職院校補(bǔ)考排考算法。本算法采用分治法的思想，基于圖論進(jìn)行算法設(shè)計，可以輔助人工排考，極大地提升了排考的工作效率和準(zhǔn)確度，優(yōu)化排考方案，使排考結(jié)果更加靈活，更好地滿足考試的需求。

1 需求分析

補(bǔ)考通常安排在學(xué)期初，主要是給考試不及格或者緩考的同學(xué)再次提供一次考試機(jī)會[4]。補(bǔ)考排考與期末排考存在顯著差異，補(bǔ)考的學(xué)生雖然規(guī)模較小，但是時間緊、任務(wù)重，存在一位同學(xué)可能同時需要補(bǔ)考多門課程以及每門課程需要補(bǔ)考的人數(shù)也有區(qū)別等諸多復(fù)雜情況。因此，補(bǔ)考排考需要考慮的因素及滿足的約束條件有：

1） 每位考生在同一時間段只能參加一門考試，若某考生有多門補(bǔ)考課程，這些課程不能安排在同一時間段。

2） 補(bǔ)考某一門課程的所有學(xué)生必須安排在相同時間段考試。

3） 不同課程參加補(bǔ)考的人數(shù)也有多有少，甚至可能一門課程只有一位同學(xué)補(bǔ)考，需要多門課程安排在同一考場同一時間段完成。

4） 對于補(bǔ)考多門課的考生安排，要注意課程之間是否存在沖突。

為了更合理地安排教學(xué)資源，滿足考試要求，補(bǔ)考應(yīng)盡可能用最短的時間，最少的場次安排完所有補(bǔ)考，同場次考試課程數(shù)量越多越好。根據(jù)約束條件，最重要的是要求一位考生在一個時間段只有一門考試，避免因考試科目沖突無法完成補(bǔ)考。人工排考要考慮諸多因素，效率低且容易出現(xiàn)各種問題。因此，一個高效的排考算法可以極大地提高排考的效率，提升準(zhǔn)確率，降低時間成本，減少排考工作人員的工作量。同時，能夠更好地滿足師生的要求，節(jié)約教學(xué)資源，使考務(wù)工作更加信息化、智能化。

2 排考系統(tǒng)設(shè)計

2.1 數(shù)據(jù)預(yù)處理

對于補(bǔ)考考場安排，首先需要獲取補(bǔ)考考生名單，一般包括學(xué)號、姓名、課程名稱、專業(yè)班級等信息。不同學(xué)校的原始Excel表格可能包含不同內(nèi)容，但都會包含基本信息。本算法系統(tǒng)采用Python語言進(jìn)行編程實現(xiàn)，讀取的原始數(shù)據(jù)存儲于Excel文件中。為增強(qiáng)本系統(tǒng)的通用性，提高數(shù)據(jù)的處理速度，需要對原始數(shù)據(jù)進(jìn)行預(yù)處理。只須將原始數(shù)據(jù)中考生的學(xué)號及補(bǔ)考課程名稱提取出來，組成新的表格數(shù)據(jù)。同時為方便不同的原始數(shù)據(jù)讀取與使用，降低對數(shù)據(jù)排列順序的要求，對學(xué)號、補(bǔ)考課程名稱等在表格的先后順序沒有要求，可通過本系統(tǒng)自動抓取相關(guān)字段。預(yù)處理可減少數(shù)據(jù)量，避免造成數(shù)據(jù)冗余，節(jié)約排考時間，提高系統(tǒng)的通用性及運(yùn)行效率。

2.2 算法設(shè)計

隨著補(bǔ)考規(guī)模的擴(kuò)大，補(bǔ)考排考的復(fù)雜程度也越來越大。直接排考可能耗時較長，為了降低排考算法的復(fù)雜程度，在排考時首先采用分治法的思想，即將問題空間分解成多個子問題，分別求出各個小空間的解，再組成整個問題的解的方法。具體方法是根據(jù)補(bǔ)考課程將問題分解為多個子空間，再用圖論算法進(jìn)行排考，最后將得到的結(jié)果合并作為本次排考的最終結(jié)果。

在本文提出的排考算法中，依據(jù)圖論做無向圖 G=（V，E），其中V是所有頂點組成的集合，即將需要補(bǔ)考的每門課程構(gòu)成圖中的一個頂點；E表示圖中所有聯(lián)結(jié)頂點的邊的集合，根據(jù)補(bǔ)考學(xué)生與課程之間的關(guān)系，若兩門課程之間存在同一個學(xué)生參加補(bǔ)考，那么就將兩頂點連接起來，即存在一條邊。遍歷所有的補(bǔ)考數(shù)據(jù)，就可得到所有結(jié)點的鄰接關(guān)系，進(jìn)而得到圖G中的集合E。如圖1所示為基于圖論的課程連接關(guān)系示意圖。圖 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同時進(jìn)行考試。

2.3 算法過程：

用 G=（V，E） 表示圖，從圖G中隨機(jī)選取一個頂點vi，即一門補(bǔ)考課程。定義一個臨時集合V'，將vi存放于集合V'中；再尋找與V'非關(guān)聯(lián)的頂點vj，將vj存放于集合V'中，遍歷集合V，直至V中沒有與V'非關(guān)聯(lián)的頂點。此時，V'包含可同時安排的補(bǔ)考課程。從圖G 中刪除集合V'，即刪除可同時安排的補(bǔ)考課程，將剩余課程構(gòu)成新的圖G，重復(fù)循環(huán)上述操作，直至G為空集，跳出循環(huán)。最后輸出最終的排考方案。

算法流程圖如圖2所示。

2.4 程序界面設(shè)計

Tkinter作為Python的標(biāo)準(zhǔn)圖形用戶界面庫，可以快速地創(chuàng)建圖形用戶界面（Graphical User Interface，GUI） 應(yīng)用程序[5-6]。為了提高系統(tǒng)的易用性，讓人機(jī)交互的過程變得更加簡單，使用Tkinter設(shè)計了GUI界面。使用Python進(jìn)行窗口界面的布局和設(shè)計，生成程序窗口，使用了Tkinter庫中的標(biāo)簽控件、文本框控件及按鈕控件[7]，得到如圖3 所示的排考場系統(tǒng)程序界面。

通過該程序界面，可以快速有效地實現(xiàn)考場的編排。使用人員可以通過點擊“選擇文件”按鈕選擇需要進(jìn)行考場編排的原始Excel文件；點擊“保存文件”按鈕選擇最終輸出的排考方案要保存的位置；點擊“運(yùn)行”按鈕系統(tǒng)開始考場的編排，運(yùn)行完成后，系統(tǒng)直接將編排好的排考結(jié)果以Excel表格的形式存儲于之前選擇的保存位置，并且可多次重復(fù)運(yùn)行，得到滿意的排考方案；點擊“退出”按鈕退出整個系統(tǒng)。

3 系統(tǒng)測試

為測試本排考系統(tǒng)的實用性，選取某學(xué)校二級學(xué)院的兩個補(bǔ)考數(shù)據(jù)進(jìn)行測試。數(shù)據(jù)1含有63人次學(xué)生，27門補(bǔ)考課程。其中補(bǔ)考課程人數(shù)最少的補(bǔ)考課程僅一人補(bǔ)考，人數(shù)最多的補(bǔ)考課程有13人補(bǔ)考。補(bǔ)考課程最少的學(xué)生僅需補(bǔ)考一門課程，補(bǔ)考課程最多的學(xué)生有7門課程補(bǔ)考。從補(bǔ)考數(shù)據(jù)來看，因為補(bǔ)考課程最多的學(xué)生有7門課程補(bǔ)考，所以至少需要安排7場不同時間段的考試。將原始補(bǔ)考信息導(dǎo)入系統(tǒng)，系統(tǒng)運(yùn)行3次，得到3種排考方案，補(bǔ)考場次均為7場。數(shù)據(jù)2含有153人次學(xué)生，29門補(bǔ)考課程。補(bǔ)考課程最少的學(xué)生僅需補(bǔ)考一門課程，補(bǔ)考課程最多的學(xué)生有6門課程補(bǔ)考。系統(tǒng)運(yùn)行3次，得到3種排考方案，補(bǔ)考場次均為6場。系統(tǒng)運(yùn)行測試結(jié)果如表1所示。

實驗結(jié)果可以看出，對于不同的數(shù)據(jù)，均可以達(dá)到理想的結(jié)果。多次運(yùn)行中，具體的排考方案會有差別，但沒有出現(xiàn)考場沖突等錯誤，準(zhǔn)確率達(dá)到100%。本文提出的補(bǔ)考排考系統(tǒng)的算法，其排考效果可以達(dá)到設(shè)計要求，具有較高的排考速度、準(zhǔn)確率以及實用性，極大地提高了排考的工作效率。同時每次的隨機(jī)機(jī)制，在實際應(yīng)用中，增加了排考結(jié)果的多樣性，增強(qiáng)了系統(tǒng)的靈活性，以方便使用人員根據(jù)各自實際情況進(jìn)行細(xì)微調(diào)整，體現(xiàn)了人性化的思維及本系統(tǒng)的泛化性能?？芍貜?fù)運(yùn)行幾次，大多數(shù)情況下都會得到滿意的排考方案。

4 結(jié)論

本文采用分治法的思想，提出了一種基于圖論的補(bǔ)考排考算法，使用Python編程實現(xiàn)了該算法，同時為了便于工作人員使用，設(shè)計了圖形用戶界面。從實際出發(fā)，解決了人工排考費時費力的問題，減少了人工排考中多次核對的負(fù)擔(dān)，考場安排合理，極大地提高了排考的效率，為補(bǔ)考排考提供了一種思路和解決方案，有很強(qiáng)的實用性。未來將對系統(tǒng)進(jìn)一步改善與優(yōu)化，例如盡量避免學(xué)生連續(xù)參加多場考試，能夠增加更多個性化的約束條件，增加系統(tǒng)靈活性，使系統(tǒng)更加自動化、智能化。

參考文獻(xiàn)：

[1] 龍麗婧，胡荷芬.基于人性化沖突解決算法設(shè)計模型[J].計算機(jī)與數(shù)字工程，2010，38（12）：57-61.

[2] 張洪旗，鄧正杰.基于多元數(shù)據(jù)的排考系統(tǒng)的設(shè)計與實現(xiàn)[J]. 電腦知識與技術(shù)，2021，17（13）：89-92.

[3] 舒清錄.基于C/S與B/S混合結(jié)構(gòu)的高校智能排考系統(tǒng)設(shè)計與實現(xiàn)[J].信息技術(shù)與信息化，2020（4）：16-19.

[4] 李瑩，陳曉華.基于圖論的高校補(bǔ)考自動排考算法的設(shè)計與實現(xiàn)[J].電腦知識與技術(shù)，2020，16（16）：224-225.

[5] 張朋，咸慶軍，陳俊旗，等.Python在扭轉(zhuǎn)內(nèi)力教學(xué)中的應(yīng)用研究[J].現(xiàn)代信息科技，2023，7（22）：195-198.

[6] 馮桂爾.基于Python的GUI（Tkinter）實例開發(fā)[J].信息與電腦（理論版），2023，35（1）：175-178.

[7] 張林.基于Python的智能組卷設(shè)計[J].電子技術(shù)與軟件工程，2023（3）：25-28.

【通聯(lián)編輯：梁書】