龔熙 于洋

摘要： 大學生選課是一個既重要又繁瑣的過程，如果不提前規(guī)劃，就有可能出現(xiàn)錯失特定學期的中意課程，單學期課業(yè)量過重和時間浪費問題，進而影響學習主動性和學業(yè)成績。為解決上述問題，研發(fā)選課推薦系統(tǒng)，根據(jù)學生所設(shè)限定條件推薦多學期的選課方案。文章提出基于0-1背包的回溯算法來處理約束，可以大范圍剪枝，加快求解速度。測試結(jié)果表明，本系統(tǒng)可以為學生推薦意向匹配率高且課業(yè)量少的選課方案。

關(guān)鍵詞： 0-1背包; 回溯算法; 推薦系統(tǒng); 課程規(guī)劃; 選課

中圖分類號：TP399? ? ? ? ? 文獻標識碼：A? ? ?文章編號：1006-8228（2021）10-75-03

Design and implementation of course selection recommendation system

with backtracking algorithm

Gong Xi， Yu Yang

（College of Computer and Information Engineering， Tianjin Normal University， Tianjin 300387， China）

Abstract： Course selection for college students is an essential and trivial process. If students do not plan， they may face problems like missing the favorite courses in a specific semester， overloading a single semester or wasting time， which will affect their learning initiative and academic performance. A course selection recommendation system is developed to solve the above problems. The system can recommend multi-semester course selection plans according to the limiting conditions set by students. This paper proposes a backtracking algorithm based on the 0-1 knapsack to deal with constraints， pruning in an extensive range to speed up the solving. Test results show that the system can recommend plans with a high matching rate of intentions and a low academic load.

Key words： 0-1 knapsack; backtracking algorithm; recommendation system; course planning; course selection

0 引言

在一些國家，導(dǎo)致學生畢業(yè)延期的主要因素是選課不當，因此早在21世紀初就開始研究選課[1]，有不少高校都根據(jù)自身實際開發(fā)了選課推薦系統(tǒng)，助力學業(yè)規(guī)劃[2]。由于國外高校選修課在總體課程中所占比例與國內(nèi)大學相比普遍偏高[3]，因此其推薦系統(tǒng)還不能很好地在國內(nèi)推廣。

我國高校在選課方面的研究也有一些，如文獻[4-7]使用MATLAB等數(shù)學軟件求解選課問題，但很難呈現(xiàn)出優(yōu)越性;雖然有文獻[8]對此改進，設(shè)計克隆選擇算法，使用VC++求解選課問題，但是沒有搭建系統(tǒng)，不便于推廣。另外，選課意向是否滿足和課業(yè)量是否合理作為影響學習主動性和學業(yè)成績的重要因素，還沒有被文獻[4-8]全部考慮在內(nèi)。

針對這些不足，本文做出如下改進。首先將課業(yè)量和選課意向納入考慮范圍，然后圍繞學分要求、課業(yè)量和選課意向設(shè)計回溯算法，未來開發(fā)適用于國內(nèi)高校的選課推薦系統(tǒng)，幫助學生聰明的選課。

1 問題提出

天津師范大學軟件學院6個學期共開設(shè)16門選修課，31門必修課，選修課如表1所示，必修課不列出。為解決錯失中意課程，課業(yè)量過重和時間浪費問題，需要綜合考慮學分要求、選課意向和課業(yè)量等因素。

1.1 學分要求

推薦的選課方案必須滿足學分要求，即不超過各學期限選學分并達到目標學分。在本問題中，第五學期限選7分，第六學期限選6分，其他學期不限選學分，要求至少修讀18.5學分。

[xij]：決策變量

[xij=1 選修第 j 學期開設(shè)的第 i 門課程;0 不選修]

[?i=1，…，m，?j=1，…，n] ⑴

其中，m為選修課程數(shù);n為總學期數(shù)。

[cj]：第j學期選修的總學分

[cj=i=1mαi×xij，?j=1，…，n] ⑵

其中，[αi]為第i門課程學分。

限選學分：第j學期選修總學分不能超過指定學分

[cj ≤δj，?j=1，…，n] ⑶

其中，[δj]為第j學期限選學分，對于不限選學分的學期，取δ為該學期所有選修課的總學分。

目標學分：n個學期內(nèi)選修總學分要達標

[j=1ncj≥ε]? ⑷

其中，[ε]為目標學分。

1.2 選課意向

學生對某門課程的意向一般可分為必選（想選）、不選（不想選）和任選（選修與否都可以）。推薦的選課方案應(yīng)包含盡量多的必選課，不包含不選課，以激發(fā)學習主動性。定義意向匹配率作為衡量標準，匹配率最高的選課方案將被推薦。

ρ：意向匹配率

[ρ=yz? ? ?不含不選課0? ? ? ? ? 含不選課]? ⑸

其中，y為某方案在選課意向中匹配的必選課程數(shù);z為選課意向中必選課程總數(shù)。

1.3 課業(yè)量

1.3.1 單學期課業(yè)量

推薦的選課方案單學期課業(yè)量不應(yīng)過重，以免影響學業(yè)成績。

[hj]：第j學期所選課程的總學時

[hj=i=1m（βi×xij），?j=1，…，n]? ⑹

其中，[βi]為第i門課程學時。

課業(yè)量限制：單學期最高學時不能超過上限

[max1≤j≤n（hj+rj）≤τ]? ⑺

其中，[rj]為第j學期必修課總學時;[ τ]為單學期允許的最大課業(yè)量。

1.3.2 課業(yè)總量

推薦的選課方案課業(yè)總量應(yīng)盡量少，以減少時間浪費?？紤]到天津師范大學軟件學院學生更傾向匹配率高的選課方案，故推薦最高匹配率下課業(yè)總量最少的選課方案。

θ：課業(yè)總量，取所選課程總學時

[θ=j=1nhj]? ⑻

2 問題求解

2.1 回溯算法

在算法實現(xiàn)中，發(fā)現(xiàn)選課問題本質(zhì)上是0-1背包問題，可采用回溯法求解。由于回溯法的非遞歸實現(xiàn)在時間方面較遞歸有較好表現(xiàn)，故采用非遞歸實現(xiàn)，如程序清單1所示。

程序清單1中將課程集合看作一個線性表，依次隱式枚舉各個選修課，為避免多選課程，已預(yù)先按照學分降序排序。枚舉開始前，先加入一個未選課程的新方案，隨后將會從第一門課程開始枚舉。

在枚舉第i門課程時，會嘗試將課程添加到方案中，以檢查方案是否滿足給定公式。如果滿足，就要分別考慮選修第i門課程與不選修兩種情況。

先檢驗選修后是否達到目標學分，如果達標且是當前最好的選課方案，則保留，不再枚舉后續(xù)課程。最終保留的方案將是最高匹配率下課業(yè)總量最少的選課方案。而不選修的方案將暫存于棧中，后續(xù)還會取出并從中斷處繼續(xù)規(guī)劃。

2.2 系統(tǒng)測試

現(xiàn)以剛?cè)雽W小王的選課意向為例，來分析推薦方案。運行系統(tǒng)時取起始學期為1、目標學分為18.5、單學期最高學時上限為400學時。

使用本系統(tǒng)前，小王自行規(guī)劃出滿足學分要求的選課方案，如表2所示，其中選修了兩門必選課和一門不選課，意向匹配率為0%;使用后小王按照推薦方案選修課程，意向匹配率達到80%，沒有選修不選課，并且選修了四門必選課，在選課意向方面有很大改進。

另外在課業(yè)量方面的改進如圖1所示。使用本系統(tǒng)后，小王課業(yè)總量減少了117學時，并將單學期最高學時維持在400學時內(nèi)，因此，本系統(tǒng)可以幫助學生聰明地選課。

3 結(jié)束語

本文在借鑒國外經(jīng)典的選課問題GBACP[9]（Generalized Balanced Academic Curriculum Problem）的基礎(chǔ)上，對選課問題抽象建模，并以天津師范大學軟件學院為實例進行研究。通過實現(xiàn)回溯求解算法，并搭建選課推薦系統(tǒng)，有效地解決了選課常見問題，讓選課過程變得簡單、輕松。

在未來的研究中，可以對以下兩點進行改進：①由于某些學校選課中存在課程間相互依存和排斥的問題，因此未來可以根據(jù)需要將相應(yīng)約束添加到程序清單1的判斷條件中，以適應(yīng)更多場景。②考慮部分學生在修讀培養(yǎng)方案的課程外會安排其他活動，因此可以允許學生增刪課程，達到個性化推薦的目的。

參考文獻（References）：

[1] Castro C， Manzano S. Variable and value ordering when solving balanced academic curriculum problems[J].arXiv preprint cs/0110007，2001.

[2] Laghari M S. Automated course advising system[J]. International Journal of Machine Learning and Computing，2014.4（1）：47

[3] 顧海兵，薛珊珊.我國高校選修課比重亟待提高——基于本科經(jīng)濟學專業(yè)的國際比較[J].中國高教研究，2009.10：85-87

[4] 李梟，欒天.數(shù)學規(guī)劃模型在大學生選課問題中的應(yīng)用[J].白城師范學院學報，2018.32（Z1）：69-74

[5] 于樂源，廖華博.關(guān)于大學生選課問題的優(yōu)化方案[J].濟寧學院學報，2016.3：40-43

[6] 張玉蘭，曹亞萍.基于0-1規(guī)劃的高校選課策略[J].高師理科學刊，2014.34（6）：14-18

[7] 劉國璧，孫群.基于0-1規(guī)劃的高校選課模型[J].長春大學學報，2012.22（8）：966-968

[8] 錢淑渠，武慧虹.0/1編碼的克隆選擇算法在選課模型中的應(yīng)用[J].安順學院學報，2008.4：89-92

[9] Chiarandini M， Di Gaspero L， Gualandi S， et al. Thebalanced academic curriculum problem revisited[J].Journal of Heuristics，2012.18（1）：119-148