论文部分内容阅读
摘要： 大学生选课是一个既重要又繁琐的过程，如果不提前规划，就有可能出现错失特定学期的中意课程，单学期课业量过重和时间浪费问题，进而影响学习主动性和学业成绩。为解决上述问题，研发选课推荐系统，根据学生所设限定条件推荐多学期的选课方案。文章提出基于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
关键词： 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