基于矩阵存储的回溯算法在多约束分配问题中的应用探讨  

Application and research of backtracking algorithm based on matrix storage in multi-constraint assignment problem

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

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

出　　处：《西南民族大学学报（自然科学版）》2008年第5期935-939,共5页Journal of Southwest Minzu University(Natural Science Edition)

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

摘　　要：学生宿舍的合理分配涉及学生高考入学成绩、生源地等诸多约束条件,在充分分析现行学生宿舍分配问题的基础上,对学生宿舍的合理分配问题进行了研究,提出了解决这类问题的一种新方法——基于矩阵存储的回溯算法.在对该算法的时间复杂度进行分析的基础上,得出了该算法较同类问题的回溯法具有更好的时间效率,在多约束分配问题中更具合理性和有效性.College dormitory can be assigned reasonably according to multi-constraint, scores, sources, and so on. By analyzing the dormitory assignment problem of current college students adequately, the problem of how to assign dormitory reasonably is researched, a new algorithm is proposed, that is, a backtracking algorithm based on matrix storage, and the complexity of the algorithm is analyzed. The result shows the algorithm is more efficient comparing the similar method, and more reasonable and effective in multi-constraint assignment problem.

关 键 词：回溯算法 约束条件 矩阵 复杂度 流程图 

分 类 号：P642[天文地球—工程地质学]