基于志愿優(yōu)先的選課算法研究

摘要：選課系統(tǒng)在選課過(guò)程中出現(xiàn)網(wǎng)絡(luò)擁堵、選課結(jié)果的公平性難以保證、課程冷熱程度不均等問(wèn)題均與系統(tǒng)選用的選課算法密切相關(guān)。本文在對(duì)現(xiàn)階段各高校普遍采用的選課算法進(jìn)行對(duì)比分析后，設(shè)計(jì)了一種基于志愿優(yōu)先的選課算法。并引入實(shí)時(shí)動(dòng)態(tài)選中機(jī)率和上次選課課程靜態(tài)選中機(jī)率等兩種機(jī)率來(lái)對(duì)學(xué)生的選課進(jìn)行一定的引導(dǎo)，并將這種選課算法與傳統(tǒng)算法進(jìn)行比較，得出采用這種新算法的優(yōu)越性。

關(guān)鍵詞：網(wǎng)絡(luò)擁堵 志愿優(yōu)先 選課算法 選中機(jī)率

0 引言

教務(wù)管理系統(tǒng)是高校教學(xué)、教務(wù)管理應(yīng)用軟件，選課系統(tǒng)是其中一個(gè)重要的子系統(tǒng)。選課系統(tǒng)的出現(xiàn)，使教學(xué)管理人員從繁重的教務(wù)工作中脫離出來(lái)，大大的提高了工作效率。當(dāng)前，各高校的選課系統(tǒng)普遍存在有選課高峰期網(wǎng)絡(luò)擁堵、選課結(jié)果的公平性難以保證、課程冷熱程度不均等問(wèn)題。這些問(wèn)題與系統(tǒng)所選擇的選課算法密切相關(guān)，為了保證系統(tǒng)運(yùn)行的高效性和選課的相對(duì)公平性，有必要設(shè)計(jì)一種合理的選課算法。

1 現(xiàn)階段選課算法分析

現(xiàn)階段各高校所采用的選課算法大致有時(shí)間優(yōu)先算法、按名額比例分配算法、專(zhuān)業(yè)優(yōu)先算法等等[1]。表1是對(duì)這幾種算法的對(duì)比分析。

從表1來(lái)看，幾種選課算法各有它的優(yōu)點(diǎn)，但同時(shí)也均存在一定程度上的缺陷，為了提高選課結(jié)果的公平性，緩解網(wǎng)絡(luò)擁堵，避免網(wǎng)絡(luò)崩潰，本文設(shè)計(jì)了一種基本志愿優(yōu)先的選課算法。

2 志愿優(yōu)先算法基本思想

整個(gè)選課分為志愿填報(bào)、系統(tǒng)集中處理、補(bǔ)選等三個(gè)階段。第一階段參與選課的學(xué)生根據(jù)自己想選的課程填報(bào)五個(gè)志愿；第二階段是系統(tǒng)以學(xué)生為單位按志愿進(jìn)行處理，并對(duì)結(jié)果進(jìn)行統(tǒng)計(jì)，把沒(méi)有選滿(mǎn)課程的學(xué)生名單以及因沒(méi)有達(dá)到課程下限人數(shù)的選課者清理出來(lái)；第三階段是根據(jù)第二階段的處理結(jié)果，被清理出來(lái)的學(xué)生進(jìn)行補(bǔ)選[2]-[11]。

2.1 志愿填報(bào)階段

在志愿填報(bào)階段，每位參與選課的學(xué)生按自己的興趣愛(ài)好在課程庫(kù)中選擇課程，并按志愿排序，每人可填報(bào)五個(gè)志愿，分別為：第一志愿、第二志愿、第三志愿、第四志愿、第五志愿。在該過(guò)程中，系統(tǒng)不僅會(huì)向同學(xué)們顯示上一次選課中該門(mén)課的選中幾率，同時(shí)會(huì)根據(jù)當(dāng)前狀態(tài)，動(dòng)態(tài)的向大家顯示當(dāng)前狀態(tài)下選中該課程的幾率又是多少。假設(shè)某一門(mén)課程的容量為S，當(dāng)前填報(bào)該科目的學(xué)生人數(shù)為Ni(第i志愿的填報(bào)人數(shù))，那么在當(dāng)前情況下再填報(bào)該課程的選中幾率見(jiàn)表2。在此階段，系統(tǒng)會(huì)為所有參與選課學(xué)生的每一個(gè)志愿都分配一個(gè)隨機(jī)數(shù)據(jù)“簽”，以便于在志愿人數(shù)大于課程容量時(shí)采用平均分布幾率算法來(lái)選取其中的一部分學(xué)生。

2.2 系統(tǒng)集中處理階段

志愿填報(bào)結(jié)束后，計(jì)算機(jī)將對(duì)學(xué)生的志愿進(jìn)行集中處理。對(duì)于每一位參與選課的學(xué)生都用一個(gè)二維數(shù)組來(lái)表示當(dāng)前的錄取狀態(tài)，數(shù)組值為1時(shí)為已錄取，為0時(shí)為未錄取；課程的錄取狀態(tài)用一個(gè)一維數(shù)組來(lái)表示，錄取完成數(shù)組值為1，未完成數(shù)組值為0。

系統(tǒng)檢測(cè)并統(tǒng)計(jì)所有的第一志愿，對(duì)第一志愿所涉及的課程科目及相對(duì)應(yīng)的人數(shù)ni1。將人數(shù)與課程容量mi1進(jìn)行比較：若人數(shù)ni1少于或等于課程容量mi1，則全部選中，對(duì)應(yīng)的課程容量變?yōu)閙i1-ni1；對(duì)應(yīng)課程錄取狀態(tài)為0，進(jìn)入下一輪志愿篩選。若人數(shù)ni1大于課程容量mi1，則按原始數(shù)據(jù)“簽”從小到大進(jìn)行處理。選中mi1位學(xué)生。對(duì)應(yīng)的課程容量變?yōu)?，課程錄取狀態(tài)為1，不再進(jìn)入下一輪志愿篩選。系統(tǒng)檢測(cè)并統(tǒng)計(jì)所有的第二志愿，對(duì)第二志愿所涉及的課程科目及相對(duì)應(yīng)的人數(shù)ni2。將對(duì)應(yīng)課程容量mi1-ni1與ni2進(jìn)行比較：若人數(shù)ni2少于等于課程容量mi1-ni1，則全部選中，對(duì)應(yīng)的課程容量變?yōu)閙i1-ni1-ni2，對(duì)應(yīng)課程錄取狀態(tài)為0，進(jìn)入下一輪志愿篩選。若人數(shù)ni2大于課程容量mi1-ni1，則按原始數(shù)據(jù)“簽”從小到大進(jìn)行處理選中mi1-ni1位學(xué)生。對(duì)應(yīng)的課程容量變?yōu)?，課程錄取狀態(tài)為1，不再進(jìn)入下一輪志愿篩選。

系統(tǒng)對(duì)于第三志愿、第四志愿和第五志愿的處理與前面的第一、二志愿處理方法一致。系統(tǒng)流程圖如圖1。

3 志愿優(yōu)先算法的實(shí)現(xiàn)

該算法由靜態(tài)選中幾率算法、動(dòng)態(tài)選中幾率算法和選課錄取算法三個(gè)子算法組成。其中靜態(tài)選中幾率算法和動(dòng)態(tài)選中幾率算法是為學(xué)生填報(bào)選課志愿時(shí)提供選中幾率參考，使學(xué)生在填報(bào)選課志愿既要考慮到自己的愛(ài)好又要考慮到選中的幾率，這樣學(xué)生就不會(huì)太過(guò)于集中選課。選課錄取算法是學(xué)生填報(bào)選課志愿之后系統(tǒng)采用的錄取規(guī)則算法，該算法主要考慮盡可能滿(mǎn)足學(xué)生的選課志愿要求。

3.1 靜態(tài)選中幾率算法

靜態(tài)選中幾率算法是該課程的上年度(或上一學(xué)期)的最終選課選中幾率，主要目的是提供學(xué)生作為本次選課的參考，防止學(xué)生選課太過(guò)于集中。

靜態(tài)選中幾率可用公式K=s/( N1+N2+N3+N4+N5)來(lái)表示。

3.2 動(dòng)態(tài)選中幾率算法

動(dòng)態(tài)選中幾率算法是該課程的本次選課過(guò)程中的動(dòng)態(tài)選課選中人數(shù)，由學(xué)生自己分析選中該課程的選中可能性，主要目的是提供學(xué)生作為本次選課的參考，防止學(xué)生選課太過(guò)于集中。

動(dòng)態(tài)選中幾率可用以下公式來(lái)表示：

①一志愿錄取幾率

②二志愿錄取幾率

③三志愿錄取幾率

④四志愿錄取幾率

⑤五志愿錄取幾率

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

選用志愿優(yōu)先篩選算法的選課系統(tǒng)，學(xué)生可以在規(guī)定時(shí)間內(nèi)的任意時(shí)間去選課，不論時(shí)間先后，每個(gè)學(xué)生的選中機(jī)會(huì)都是一樣的，這樣的算法實(shí)現(xiàn)起來(lái)不是很復(fù)雜，對(duì)于系統(tǒng)的運(yùn)算速度和運(yùn)行效率也就不會(huì)有多大影響。其中的篩選工作由系統(tǒng)根據(jù)預(yù)先設(shè)定的程序自動(dòng)執(zhí)行，減少系統(tǒng)管理工作強(qiáng)度。相比來(lái)說(shuō)它具有以下幾個(gè)優(yōu)點(diǎn)：

①選課結(jié)果與選課時(shí)間無(wú)關(guān)。這樣既解決了選課高峰期網(wǎng)絡(luò)擁堵問(wèn)題，也提高了選課結(jié)果的公平性。②設(shè)計(jì)了動(dòng)態(tài)和靜態(tài)兩個(gè)選中機(jī)率，能動(dòng)態(tài)的調(diào)節(jié)課程之間的平衡，不至于出現(xiàn)熱門(mén)課程更熱、冷門(mén)課程更冷的現(xiàn)象。

通過(guò)對(duì)比實(shí)驗(yàn)，基于志愿優(yōu)先的選課算法與現(xiàn)有其它選課算法相比較，具有容易實(shí)現(xiàn)、算法思路清晰、運(yùn)算速度快等優(yōu)點(diǎn)，是一種可行而又優(yōu)秀的選課算法。

參考文獻(xiàn)：

[1]黃海東.網(wǎng)上選課系統(tǒng)的算法分析與改進(jìn)[[J].淮南職業(yè)技術(shù)學(xué)院學(xué)報(bào).2009，(1)：27-28.

[2]王卿.高等院校學(xué)分制教學(xué)排考問(wèn)題算法設(shè)計(jì)[J].上海理工大學(xué)學(xué)報(bào)，2007(6)：583-587.

[3]陳利平.排除論在高校選課系統(tǒng)服務(wù)臺(tái)模型設(shè)計(jì)中的應(yīng)用[J].計(jì)算機(jī)技術(shù)與發(fā)展，2008，(9)：60-62.

[4]胡順仁，鄧毅，王錚.基于高校排課系統(tǒng)中的圖論問(wèn)題研究[J].計(jì)算機(jī)工程與應(yīng)用，2002（38）：221-222.

[5]王貴翔.數(shù)據(jù)倉(cāng)庫(kù)技術(shù)在招生決策系統(tǒng)中的應(yīng)用[J].貴州大學(xué)學(xué)報(bào)，2006，(11)：389-391.

[6]駱炎發(fā)，張全伙.XML的關(guān)系數(shù)據(jù)庫(kù)技術(shù)與應(yīng)用[J].華僑大學(xué)學(xué)報(bào)，2003（3）：325-330

[7]康慨.公平合理選課方式探討[J].北京理工大學(xué)學(xué)報(bào)，2007(5)：26-28.

[8]徐明.志愿隨機(jī)篩選算法在選課系統(tǒng)中的應(yīng)用[J].南通紡織職業(yè)技術(shù)學(xué)院學(xué)報(bào)，2007，(7)：33-35.

[9]李斌.網(wǎng)上交易系統(tǒng)性能優(yōu)化算法[[J].華中科技大學(xué)學(xué)報(bào).2008（10）：78-81.

[10]肖瀟.志愿選課算法分析與最優(yōu)決策[J].科技資訊，2009 (10)：172-173.

[11]譚浩強(qiáng).C語(yǔ)言程序設(shè)計(jì)（第三版）[M].清華大學(xué)出版社，2001：21-194.

作者簡(jiǎn)介：劉蓮輝（1976-），女，湖南婁底人，湖南人文科技學(xué)院講師，主要從事大學(xué)物理和大學(xué)物理實(shí)驗(yàn)教學(xué)及研究工作。

基金項(xiàng)目:湖南人文科技學(xué)院教改項(xiàng)目（RKJGY1037）