摘要
回溯法是解决多约束条件下合理分配问题的重要方法之一,经过认真分析研究,提出了解决这类问题的一种新的有效算法——基于矩阵存储的回溯算法,并以学生宿舍合理分配问题为背景,给出了算法的具体实现过程,最后讨论了该算法的时间复杂度,得出了该算法较同类问题的回溯法具有更好的时间效率,实际应用的结果验证了该算法在多约束分配问题中更具合理性和有效性.
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.
出处
《江西师范大学学报（自然科学版）》
CAS
北大核心
2008年第6期729-732,共4页
Journal of Jiangxi Normal University(Natural Science Edition)
基金
国家自然科学基金(60573052)
延安大学预研项目(YJS07-10)资助
关键词
回溯算法
约束条件
多约束分配
时间复杂度
流程图
backtracking algorithm
matrix storage
multi - constraint assignment
flow chart
complexity
