中文摘要：

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

英文摘要：

On coping with constraint satisfaction problems by means of classical dynamic backtracking based on MAC,it costs much space to store eliminating explanation,and the backtracking mechanism is too complex.Thus we optimized the classic eliminating explanation and the backtracking mechanism of the dynamic backtracking algorithm.The optimized dynamic backtracking algorithm compresses the space of recording eliminating explanation,and returns to the key variable that may lead to confliction via only one backtrack operation.In the worst case,the space complexity of storing eliminating explanation declines from O（n2 d）to O（nd＋n2）.The optimized dynamic backtracking algorithm combines with restart technology for further improvement to become a complete algorithm.Experimental results show that the efficiency of the complete optimized dynamic backtracking algorithm is prior to that of standard backtracking in solving most problems.