基于回溯算法的多约束宿舍分配方法  

Multi-constraint dormitory allocation method based on backtracking algorithm

作　　者：王晓薇[1] 马佳宁 龚雪莹 任恩良 孙航 WANG Xiaowei;MA Jianing;GONG Xueying;REN Enliang;SUN Hang(Software College, Shenyang Normal University, Shenyang 110034, China;Party and Government Office, Shenyang Institute of Engineering, Shenyang 110136,China)

机构地区：[1]沈阳师范大学软件学院,沈阳110034 [2]沈阳工程学院党政办公室,沈阳110136

出　　处：《沈阳师范大学学报（自然科学版）》2021年第2期164-168,共5页Journal of Shenyang Normal University:Natural Science Edition

基　　金：教育部高等学校重点实验室访问学者基金项目(20200701)。

摘　　要：高校招生规模不断扩大,在校大学生的人数在不断增加,对学生主管部门而言,学生数量的增长会给其各项学生管理工作带来一定的压力。基于此,提出基于回溯算法的多约束宿舍分配方法,回溯算法是解决多约束条件下合理分配问题的重要方法之一。首先分析宿舍分配的约束条件,同时对宿舍资源及学生进行统计分析,形成宿舍集与学生集,结合回溯算法,基于约束条件,按照深度优先的搜索策略,从宿舍集的根结点出发,搜索解空间树,得到最优解,实现宿舍智能分配。最后通过计算算法的时间复杂度,得出了该算法较同类问题的回溯法具有更好的时间效率,同时验证了该算法在多约束分配问题中更具合理性和有效性。通过文章提出的算法进行宿舍分配,有效地节约了人力、时间等成本,同时提高了宿舍分配的质量。As the enrollment scale of colleges and universities continues to expand,the number of college students continues to increase.For the student authorities,the increase in the number of students will bring some pressure to their various student management works.Based on this,a multi-constraint dormitory allocation method based on backtracking algorithm is proposed.Backtracking algorithm is one of the important methods to solve the reasonable allocation problem under multi-constraint conditions.Firstly,the constraint conditions of dormitory allocation are analyzed,and the dormitory resources and students are statistically analyzed to form the dormitory set and student set.Combined with the backtracking algorithm,based on the constraint conditions,according to the depth-first search strategy,starting from the root node of the dormitory set,the solution space tree is searched to obtain the optimal solution,and the intelligent dormitory allocation is realized.Finally,by calculating the time complexity of the algorithm,it is concluded that the algorithm has better time efficiency than the backtracking method of similar problems.At the same time,it is proved that this algorithm is more reasonable and effective in multi-constraint assignment problem.The algorithm proposed in this paper can effectively save the cost of manpower and time,and improve the quality of dormitory allocation.

关 键 词：回溯算法 多约束 宿舍分配 

分 类 号：TP391.9[自动化与计算机技术—计算机应用技术]