基于矩阵存储的学生分班问题的回溯算法  

Backtracking algorithm for assigning dormitory problem based on matrix storage

作　　者：马燕[1,2] 王文发[1,2] 李宏达[3] 

机构地区：[1]延安大学计算机学院,陕西延安716000 [2]延安大学软件研究与开发中心,陕西延安716000 [3]中国科学院软件研究所信息安全国家重点实验室,北京100080

出　　处：《计算机工程与设计》2009年第12期3022-3025,共4页Computer Engineering and Design

基　　金：国家自然科学基金项目(60573052);延安大学预研基金项目(YJS07-10)

摘　　要：结合项目开发,提出了多约束条件下合理分配问题的一种解法——基于矩阵存储的回溯算法。以学生合理分班问题为例,以学生成绩和男女生比例等诸多条件作为约束,给出了算法的具体实现过程,分析了算法的时间复杂度。该算法较同类问题的回溯法,效率有很大提高,实际应用的结果表明了算法的合理性和有效性。Combining with the actual project, an effective solution, backtracking algorithm based on matrix storage, for assignment problem is proposed under multi-constraint conditions. Taking class-division of college students as example, the entrance examination scores and the proportion of male and female students as multi-constraints, the implementation procedure of this algorithm is given, and the complexity is analyzed. The analysis result show the algorithm is more efficient comparing the similar method, and the application result show it is effective and reasonable.

关 键 词：回溯算法 矩阵存储 多约束分配 流程图 时间复杂度 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]