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

摘要：

针对基于 MAC 的动态回溯算法在求解约束满足问题时，不仅需要大量空间存储删除解释，而且回溯机制过于复杂，对经典的删除解释及动态回溯算法的回溯机制进行优化，优化后的动态回溯算法减少了存储删除解释的空间，并可仅使用一次回溯操作返回到可能导致冲突的关键变量。在最差情况下，存储删除解释的空间复杂度由 O(n 2 d )改进为O(nd +n 2)。通过结合 restart 技术使优化后的动态回溯算法成为完备算法。实验结果表明，优化后的完备动态回溯算法在大部分问题求解中，整体效率明显优于标准回溯算法。

关键词：人工智能、约束满足问题、动态回溯算法、删除解释

分类号：TP18(自动化基础理论)

资助基金：国家自然科学基金61173014,61272208;吉林省自然科学基金20140101200JC

在线出版日期：2015-04-10（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：285-290