基于回溯算法的选课推荐系统的设计与实现.docx

基于回溯算法的选课推荐系统的设计与实现龚熙于洋摘要：大学生选课是一个既重要又繁琐的过程，如果不提前规划，就有可能出现错失特定学期的中意课程，单学期课业量过重和时间浪费问题，进而影响学习主动性和学业成绩。为解决上述问题，研发选课推荐系统，根据学生所设限定条件推荐多学期的选课方案。文章提出基于0-1背包的回溯算法来处理约束，可以大范围剪枝，加快求解速度。测试结果表明，本系统可以为学生推荐意向匹配率高且课业量少的选课方案。关键词：0-1背包;回溯算法;推荐系统;课程规划;选课中图分类号：TP399文献标识码：A文章编号：1006-8228（2021）10-75-03DesignandimplementationofcourseselectionrecommendationsystemwithbacktrackingalgorithmGongXi，YuYang（CollegeofComputerandInformationEngineering，TianjinNormalUniversity，Tianjin300387，China）Abstract：Courseselectionforcollegestudentsisanessentialandtrivialprocess.Ifstudentsdonotplan，theymayfaceproblemslikemissingthefavoritecoursesinaspecificsemester，overloadingasinglesemesterorwastingtime，whichwillaffecttheirlearninginitiativeandacademicperformance.Acourseselectionrecommendationsystemisdevelopedtosolvetheaboveproblems.Thesystemcanrecommendmulti-semestercourseselectionplansaccordingtothelimitingconditionssetbystudents.Thispaperproposesabacktrackingalgorithmbasedonthe0-1knapsacktodealwithconstraints，pruninginanextensiverangetospeedupthesolving.Testresultsshowthatthesystemcanrecommendplanswithahighmatchingrateofintentionsandalowacademicload.Keywords：0-1knapsack;backtrackingalgorithm;recommendationsystem;courseplanning;courseselection0引言在一些国家，导致学生毕业延期的主要因素是选课不当，因此早在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学期限选学分，对于不限选学分的学期，取δ为该学期所有选修课的