回溯算法在多约束分配问题中的应用  

The Application of Backtracking Algorithm in Multi-constraint Assignment Problem

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

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

出　　处：《微计算机应用》2008年第11期87-90,共4页Microcomputer Applications

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

摘　　要：以学生宿舍合理分配问题为背景,对分配中所涉及的学生高考入学成绩、生源地、宿舍类别等诸多约束条件进行充分分析和探讨,给出了解决这类问题的一种新的有效算法——基于矩阵存储的回溯算法,并给出了算法的实现细节。在此基础上,讨论了该算法的时间复杂度,得出了该算法较同类问题的回溯法具有更好的时间效率,说明了该算法在多约束分配问题中更具合理性和有效性。The multi-constraint conditions,including the entrance examination for college,the source and the dormitory classification and so on,were analyzed and studied enough by assigning dormitory reasonably.A new backtracking algorithm based on matrix storage was proposed to resolve such problem,and the realization detailed of the algorithm was discussed.Further,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.

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

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