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

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