摘 要:在選課系統(tǒng)中，當(dāng)同一門課程有多個教學(xué)班或要求學(xué)生選課必須有多個志愿時，適合使用志愿分級篩選算法。為了使選課過程更加科學(xué)化、人性化，對該算法進行了系統(tǒng)的分析，并從選課前準備工作、預(yù)選和正選三方面提出了改進措施，從而得到一個實用性更強，更加完善的選課算法。用改進后志愿分級篩選算法設(shè)計的選課系統(tǒng)，使優(yōu)秀的學(xué)生可以優(yōu)先選到自己感興趣的課程，使選課系統(tǒng)更加人性化，更加適合學(xué)生學(xué)習(xí)的需求。關(guān)鍵詞:選課系統(tǒng); 志愿分級篩選算法; 平均分布概率算法; 權(quán)重

中圖分類號:TN911-34; TP311文獻標識碼:A

文章編號:1004-373X(2010)16-0026-03

Improvement of Voluntary Screening Algorithm for Classification in Course-selecting System

LI Chun-jie1，2， LIU Jie2， LI Dian-kui1， GUO Ji-ping1

(1.Commonality Teaching Department of Computer， Jiamusi University， Jiamusi 154007， China;

2.College of Computer Science and Technology， Harbin Engineering University， Harbin 154001， China)

Abstract: In course-selecting system， the voluntary screening algorithm for classification is suitable for the situation that there is a course with several classes or a student must select more than one courses as he makes selection. The algorithm is analyzed in this paper for making the process of the course selection more scientific and humane. The improvement measures are proposed in three aspects: preparation before course selection， pre-selection and formal selection， which allow the course selection algorithm to be more perfect. The course-selecting system designed with the improved voluntary screening algorithm for classification causes the good students to have priority in course selection to their own interest， and makes the elective system more humane and more appropriate to the students.Keywords: course-selecting system; voluntary screening algorithm for classification; average distribution probabilistic algorithm; weight

0 引 言

目前在高校中大多都已經(jīng)實行了選課制，隨著網(wǎng)絡(luò)的普及，網(wǎng)上選課系統(tǒng)的出現(xiàn)，隨之而來的選課算法也不斷地出現(xiàn)和改進，而且越來越體現(xiàn)出選課的公平和公正性。

最簡單的先來先服務(wù)算法是根據(jù)選課時間的先后進行選課操作，當(dāng)選課人數(shù)達到最大限選人數(shù)時即結(jié)束;若學(xué)生為了選到自己喜歡的課都在同一時間段內(nèi)進行選課，容易造成網(wǎng)絡(luò)擁堵，而且由于網(wǎng)速的問題也可能出現(xiàn)學(xué)生先選的不一定先得到服務(wù)[1]。抽簽算法主要用于處理選課人數(shù)超過限選人數(shù)的情況。對于抽簽算法，抽簽的方法又不盡相同，總結(jié)起來有隨機抽取、按權(quán)重高低抽取和各種優(yōu)先排列抽取等[2]。目前常用的優(yōu)先排列抽取主要有專業(yè)優(yōu)先算法，成績優(yōu)先算法，按名額分配比例算法，志愿分級篩選算法等。長期實踐表明，不同的算法各有其優(yōu)缺點，適合于不同的選課處理。

由于學(xué)生每學(xué)期的權(quán)重值區(qū)分不大，按權(quán)重高低抽取方式的抽簽算法也不是很實用或?qū)嵱糜诤苄〉姆秶?。專業(yè)優(yōu)先算法比較適用專業(yè)選修課的選課處理，適用于小范圍的專業(yè)課選課，不適合全校性公共課選課。而按名額比例分配算法類似于平均主義，沒有真正考慮到學(xué)生的需求，該算法在具體的實現(xiàn)上還比較復(fù)雜。志愿分級篩選算法原理清晰，是目前網(wǎng)絡(luò)選課的主流算法，該算法實現(xiàn)起來較容易，而且操作簡單，系統(tǒng)開銷也不大，運算速度較快，是性能優(yōu)越的選課算法[3]。

1 志愿分級篩選算法

志愿分級篩選算法采用實時選課處理和后臺批處理相結(jié)合的方法來實現(xiàn)的，即分為預(yù)選和正選兩個階段。

1.1 預(yù)選階段

在指定的時間內(nèi)，學(xué)生登錄選課系統(tǒng)進行選課操作。此時在選課過程中允許每個學(xué)生在選課時對于有多個課程班(課程名稱、任課教師、上課時間和上課地點相同的學(xué)生稱為一個課程班)的課程或要求學(xué)生選課必須有多個(一般3個)志愿時，可以有3個優(yōu)先級不同的志愿選擇，其原理類似于高考錄取時數(shù)據(jù)的處理[4]。預(yù)選課期間每個學(xué)生都具有平等的選課權(quán)利，當(dāng)預(yù)選結(jié)束后，才進行后臺正選處理。這樣就防止了學(xué)生集中時間登錄選課，克服了先來先服務(wù)算法的弊病。

1.2 正選階段

計算機按不同的志愿相繼進行處理。首先處理第一志愿，若第一志愿人數(shù)(N1)超過該課程限選人數(shù)(M)，即N1>M時，采用平均分布概率算法來進行處理，從N1人中篩選出M人，此時不再處理二、三志愿;若第一志愿人數(shù)(N1)小于等于該課程限選人數(shù)(M)，即N1≤M時，全部選中。當(dāng)所有第一志愿課程班遍歷完后，對于未選滿的課程班再遍歷第二志愿，此時第二志愿的最大限選人數(shù)是M-N1，處理方法同第一志愿，以此類推，接著再遍歷第三志愿[5-6]。如果該門課名額未滿，可以公布選課結(jié)果進行補報，若補報后選課總?cè)藬?shù)超過該門課的限選人數(shù)時，先前處理的有效選課記錄不參加下一輪篩選，后來補報的學(xué)生采用平均分布概率算法來進行處理，若有需要，選課將采用多輪篩選。經(jīng)過預(yù)選和正選兩個階段后，可能有少數(shù)學(xué)生3個志愿都未選中，此時需人工干預(yù)處理，最終產(chǎn)生課表[7]。

1.3 志愿分級篩選算法優(yōu)缺點

該算法是當(dāng)所有學(xué)生預(yù)選均結(jié)束后，才進行處理的，選課結(jié)果與選課先后次序無關(guān)，從而可以緩解學(xué)生之間搶先選課的矛盾，而且選課結(jié)果分布均勻，落選的機會少，做到了選課的公平。

由于學(xué)生的情況各不相同，有的學(xué)生對整個大學(xué)學(xué)習(xí)有一個完整的計劃，而且在此計劃前提下，能夠有較高的積極性并在選擇的課程上取得較好的成績。而一部分學(xué)生是沒有計劃的，只是選擇人多的熱門課程或認為容易通過的課程，這部分學(xué)生的學(xué)習(xí)成績通常是較差的，他們只是跟著感覺走，甚至不考慮自己的研究方向，不考慮課程本身的學(xué)習(xí)前提或課程的性質(zhì)。

第一志愿往往表現(xiàn)出學(xué)生學(xué)習(xí)的熱情，有些學(xué)生對該門課程十分感興趣，尤其一些學(xué)習(xí)成績優(yōu)異，有很強上進心的學(xué)生。當(dāng)?shù)谝恢驹溉藬?shù)超過該課程限選人數(shù)時，采用的是平均分布概率算法，在分配隨機數(shù)時，雖然是系統(tǒng)自動篩選的，但一些渴望學(xué)習(xí)的學(xué)生有可能就會失去選修該門課的機會，會打消學(xué)習(xí)的積極性。對于這種情況，在進行篩選的時候應(yīng)該給予考慮，應(yīng)該盡量滿足有計劃、學(xué)習(xí)好的學(xué)生的選課要求，以鼓勵他們完成自己的學(xué)業(yè)，實現(xiàn)人生目標。

2 志愿分級篩選算法的改進

這里主要從選課前準備工作、預(yù)選和正選三方面進行改進。

2.1 選課前準備工作

在選課之前，最好是在上一學(xué)期的期末發(fā)布下一學(xué)期選課信息和各門課程的相關(guān)介紹;有條件的還可以使用選課推薦系統(tǒng)對學(xué)生進行課程的推薦[8]，這樣選課不再盲目，還可以幫助學(xué)生選擇自己感興趣的課程，提高學(xué)生的學(xué)習(xí)積極性。

2.2 預(yù)選階段

在預(yù)選課期間，固定時間進行選課統(tǒng)計，隨時發(fā)布預(yù)選課信息，如各門課限選人數(shù)，目前預(yù)選人數(shù)，積分排名等。學(xué)生可以在預(yù)選課期間自行調(diào)整，可以使學(xué)生第一志愿選中率提高。

2.3 正選階段

對正選時使用的志愿分級篩選算法進行了改進，改進后的算法如下:

若第一志愿人數(shù)(N1)小于等于該課程限選人數(shù)(M)，即N1≤M時，全部選中，不再處理二、三志愿;當(dāng)?shù)谝恢驹溉藬?shù)(N1)超過該課程限選人數(shù)(M)時，即N1>M時，進行如下處理:

首先查看學(xué)生的積分，統(tǒng)計積分大于等于θ的學(xué)生人數(shù)為N11，則積分小于θ的學(xué)生人數(shù)為N1-N11。這里的閾值θ，一般已經(jīng)存在默認值，即程序運行前已經(jīng)初始化。根據(jù)學(xué)校的不同情況，不同的積分規(guī)則設(shè)定的方法可以不同。例如按積分排序，取前10%的學(xué)生中最低分，或按以往的經(jīng)驗來確定等。若N11≤M，則全部選中，再在未選中的學(xué)生中使用平均分布概率算法選出M-N11名學(xué)生;若N11>M，則使用平均分布概率算法選出M名學(xué)生，添加到正選表中，流程圖如圖1所示。

圖1 改進后的算法流程圖

當(dāng)所有第一志愿課程班遍歷完后，對于未選滿的課程班再遍歷第二志愿，此時第二志愿的最大限選人數(shù)是M-N1，處理方法同第一志愿，以此類推，接著再遍歷第三志愿。

其中學(xué)生積分的設(shè)置是根據(jù)學(xué)生學(xué)習(xí)成績，該門課程的前驅(qū)課選課情況等，可依據(jù)本校的實際情況而定，積分的判斷值也可根據(jù)各校的不同而定。

該算法可以保證積分高的學(xué)生優(yōu)先入選，與先前的算法相比較，參加隨機篩選的人數(shù)相對減少。所以在進行平均分布概率算法時，產(chǎn)生的隨機數(shù)的數(shù)量減少，即改進后算法中平均分布概率算法的時間復(fù)雜度是O(N1-N11)，和改進前該算法的時間復(fù)雜度O(N1)相比，提高了篩選速度和運行效率。

經(jīng)驗表明:優(yōu)秀的學(xué)生只占少數(shù)，一般情況下能夠全部選中，而且剩下的名額數(shù)量還很多，即流程圖中大多執(zhí)行的是①②③。

以第一志愿人數(shù)(N1) 100人為例，其中前10名學(xué)生積分最大值為3，最小值為1，設(shè)定θ值為1，由于第11到第30名學(xué)生積分值是1，所以積分大于等于θ的學(xué)生人數(shù)占30%)，該課程限選人數(shù)(M)為80，分別對改進前后的算法進行的測試。采用原算法產(chǎn)生隨機數(shù)為100，優(yōu)秀學(xué)生選中率為66.7%，其他學(xué)生選中率為85.7%;采用改進后算法產(chǎn)生隨機數(shù)為80，優(yōu)秀學(xué)生選中率為100%，其他學(xué)生選中率為71.4%。由此表明，改進后的選課算法可以滿足大多數(shù)學(xué)生選課的愿望，減少了優(yōu)秀學(xué)生落選的幾率。

3 結(jié) 語

實踐證明，用改進后志愿分級篩選算法設(shè)計的選課系統(tǒng)，更加適合學(xué)生學(xué)習(xí)的需求，使優(yōu)等生可以優(yōu)先選到自己感興趣的課程。與此同時，其他學(xué)生為了選到自己滿意的課程也會努力學(xué)好前驅(qū)課程，這樣更好地激發(fā)了學(xué)生的學(xué)習(xí)積極性，提高了學(xué)生的學(xué)習(xí)熱情。

參考文獻

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

[2]Ferland J A， Fleruent C. SAPHIR: A decision support system for coursescheduling[J]. Interfaces， 1994， 24(2): 105-111.

[3]趙波.選課管理系統(tǒng)的設(shè)計與開發(fā)[J].云南民族學(xué)院學(xué)報:自然科學(xué)版，2002，11(4):245-248.

[4]楊海榮.基于校園網(wǎng)的網(wǎng)上選課系統(tǒng)的設(shè)計與實現(xiàn)[J].湖南稅務(wù)高等?？茖W(xué)校學(xué)報，2003(9):55-57.

[5]李冰穎，夏利民，舒遠仲.學(xué)分制模式下網(wǎng)上選課系統(tǒng)的算法探析[J].江西科學(xué)，2004，22(5):358-360.

[6]關(guān)慧，由德凱，侯建梅.網(wǎng)上選課系統(tǒng)的設(shè)計與實現(xiàn)[J].沈陽化上學(xué)院學(xué)報，2004，18(4):295-298.

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

[8]王艷，劉雙紅，李玲玲.基于加權(quán)關(guān)聯(lián)規(guī)則的選課推薦系統(tǒng)的構(gòu)建[J].鄭州輕工業(yè)學(xué)院學(xué)報:自然科學(xué)版，2009(5):44-47.