回溯法求解多约束分配问题  

Application and Research of Backtracking Algorithm Based on Matrix Storage in Multi-Constraint Assignment Problem

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

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

出　　处：《江西师范大学学报（自然科学版）》2008年第6期729-732,共4页Journal of Jiangxi Normal University(Natural Science Edition)

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

摘　　要：回溯法是解决多约束条件下合理分配问题的重要方法之一,经过认真分析研究,提出了解决这类问题的一种新的有效算法——基于矩阵存储的回溯算法,并以学生宿舍合理分配问题为背景,给出了算法的具体实现过程,最后讨论了该算法的时间复杂度,得出了该算法较同类问题的回溯法具有更好的时间效率,实际应用的结果验证了该算法在多约束分配问题中更具合理性和有效性.Backtracking algorihm is one of important metheds to solving the multiconstraint assignment problem. By analyzing and studying enough, a new backtracking algorithm based on matrix storage was proposed. Based on the background of reasonable assignment for college dormitory, detailed algorithm realization process was given, and the complexity of the algorithm was analyzed. The analysis result show the algorithm is more efficient comparing the similar method, and the application result show it is effective and reasonable in practice.

关 键 词：回溯算法 约束条件 多约束分配 时间复杂度 流程图 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]