志愿分級篩選算法在選課系統中的分析與改進

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

中圖分類號: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 引 言

目前在高校中大多都已經實行了選課制，隨著網絡的普及，網上選課系統的出現，隨之而來的選課算法也不斷地出現和改進，而且越來越體現出選課的公平和公正性。

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

由于學生每學期的權重值區分不大，按權重高低抽取方式的抽簽算法也不是很實用或實用于很小的范圍。專業優先算法比較適用專業選修課的選課處理，適用于小范圍的專業課選課，不適合全校性公共課選課。而按名額比例分配算法類似于平均主義，沒有真正考慮到學生的需求，該算法在具體的實現上還比較復雜。志愿分級篩選算法原理清晰，是目前網絡選課的主流算法，該算法實現起來較容易，而且操作簡單，系統開銷也不大，運算速度較快，是性能優越的選課算法[3]。

1 志愿分級篩選算法

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

1.1 預選階段

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

1.2 正選階段

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

1.3 志愿分級篩選算法優缺點

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

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

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

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

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

2.1 選課前準備工作

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

2.2 預選階段

在預選課期間，固定時間進行選課統計，隨時發布預選課信息，如各門課限選人數，目前預選人數，積分排名等。學生可以在預選課期間自行調整，可以使學生第一志愿選中率提高。

2.3 正選階段

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

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

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

圖1 改進后的算法流程圖

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

其中學生積分的設置是根據學生學習成績，該門課程的前驅課選課情況等，可依據本校的實際情況而定，積分的判斷值也可根據各校的不同而定。

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

經驗表明:優秀的學生只占少數，一般情況下能夠全部選中，而且剩下的名額數量還很多，即流程圖中大多執行的是①②③。

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

3 結 語

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

參考文獻

[1]黃海東.網上選課系統的算法分析與改進[J].淮南職業技術學院學報，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]趙波.選課管理系統的設計與開發[J].云南民族學院學報:自然科學版，2002，11(4):245-248.

[4]楊海榮.基于校園網的網上選課系統的設計與實現[J].湖南稅務高等專科學校學報，2003(9):55-57.

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

[6]關慧，由德凱，侯建梅.網上選課系統的設計與實現[J].沈陽化上學院學報，2004，18(4):295-298.

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

[8]王艷，劉雙紅，李玲玲.基于加權關聯規則的選課推薦系統的構建[J].鄭州輕工業學院學報:自然科學版，2009(5):44-47.