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

Application of Backtracking Algorithm Based on Matrix Storage in Multi-constraint Assignment Problem

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

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

出　　处：《江西科学》2008年第5期697-699,706,共4页Jiangxi Science

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

摘　　要：学生宿舍的合理分配涉及学生高考入学成绩、生源地等诸多约束条件,在充分分析现行学生宿舍分配问题的基础上,对学生宿舍的合理分配问题进行了研究,提出了解决这类问题的一种新方法——基于矩阵存储的回溯算法。在对该算法的时间复杂度进行分析的基础上,得出了该算法较同类问题的回溯法具有更好的时间效率,在多约束分配问题中更具合理性和有效性。For reasonable assignment of college dormitories, multi - constraints such as student scores ,local customs, student habit and so on should be considered. Based on analyzing the student dormitory assignment problem adequately, a new assignment algorithm, a backtracking algorithm based on matrix storage, was proposed, and the time complexity of the p lyzed, which indicates the p algorithm is more efficient and effective compared to the existing methods for multi -constraint assignment problems.

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

分 类 号：O223[理学—运筹学与控制论]