基于MAC的动态回溯算法优化.pdfVIP

第 53卷 第 2期 吉 林 大 学 学 报 (理 学 版 ) Vo1．53 NO．2 2015年 3月 JournalofJilinUniversity(ScienceEdition) M ar 2O15 doi：10．13413／j．cnki．jdxblxb．2015．02．25 基于MAC的动态回溯算法优化 许苍竹 ，郝 爽 。，李博宇 ，刘明慧 (1．吉林大学 符号计算与知识工程教育部重点实验室，长春 130012； 2．吉林大学 计算机科学与技术学院，长春 130012；3．吉林大学 软件学院，长春 130012) 摘要：针对基于MAC的动态回溯算法在求解约束满足 问题时，不仅需要大量空间存储删 解释，而且回溯机制过于复杂，对经典的删除解释及动态 回溯算法的回溯机制进行优化， 化后的动态回溯算法减少 了存储删除解释 的空间，并可仅使用一次回溯操作返 回到可能导 冲突的关键变量．在最差情况下，存储删 除解释 的空间复杂度 由O(n。)改进为0( +n。 通过结合 restart技术使优化后的动态回溯算法成为完备算法．实验结果表明，优化后的完 动态回溯算法在大部分 问题求解 中，整体效率明显优于标准 回溯算法． 关键词 ：人工智能；约束满足问题；动态回溯算法；删除解释 中图分类号 ：TP18 文献标志码 ：A 文章编号：1671-5489(2015)02—0285—06 OptimizingtheDynamicBacktrackingBasedonMAC XU Cangzhu ，HAO Shuang ，LIBoyu ，LIU M inghui， (1·KeyLaboratoryofSymbolicComputationandKnowledgeEngineeringforMinistryofEd“c口tio”。JiliUniveity． Changchun 130012，China；2 ． CollegeofComputerScienceandTechnolog ，JiliUniversit ， Changchun 130012，China；3 ． CollegeofSoftware，JilinUniversity，Changchu 130012，( 口) Abstract：Oncopingwithconstraintsatisfactionproblemsbymeansofclassicaldynamicbacktracking 除 优 致 备 basedonMAC,itcostsmuchspacetostoreeliminatingexplanation，andthebacktrackingmechanism IS tOO complex． Thus we optimized the classic eliminating explanation and the backtracking mechanism ofthedynamicbacktrackingalgorithm． Theoptimized dynamicbacktrackingalgorithm compressesthespaceO{recordingeliminating explanation．andreturnstothekeyvariablethatmay leadtoconflictionviaonlyonebackt