基于回溯算法的選課推薦系統的設計與實現

龔熙 于洋

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

關鍵詞： 0-1背包; 回溯算法; 推薦系統; 課程規劃; 選課

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

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

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

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

1 問題提出

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

1.1 學分要求

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

[xij]：決策變量

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

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

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

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

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

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

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

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

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

目標學分：n個學期內選修總學分要達標

[j=1ncj≥ε]? ⑷

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

1.2 選課意向

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

ρ：意向匹配率

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

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

1.3 課業量

1.3.1 單學期課業量

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

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

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

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

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

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

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

1.3.2 課業總量

推薦的選課方案課業總量應盡量少，以減少時間浪費。考慮到天津師范大學軟件學院學生更傾向匹配率高的選課方案，故推薦最高匹配率下課業總量最少的選課方案。

θ：課業總量，取所選課程總學時

[θ=j=1nhj]? ⑻

2 問題求解

2.1 回溯算法

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

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

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

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

2.2 系統測試

現以剛入學小王的選課意向為例，來分析推薦方案。運行系統時取起始學期為1、目標學分為18.5、單學期最高學時上限為400學時。

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

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

3 結束語

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

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

參考文獻（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].中國高教研究，2009.10：85-87

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

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

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

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

[8] 錢淑渠，武慧虹.0/1編碼的克隆選擇算法在選課模型中的應用[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