【摘要】 基于树分解的回溯搜索算法,结合separator分解算子提出一种新的搜索算法BTD+-MAC.该算法在搜索时,优先选择separator中的变量进行相容性检查和实例化,由于树宽度的减小能提高约束传播的效率,进而提高问题求解效率.对几组benchmark问题进行测试,测试结果表明,该算法在问题求解效率上超过了MAC3rm算法和BTD-MAC算法.更多还原

【Abstract】 Based on the tree decomposition backtracking search algorithm,combined with the separator decomposition operator,we proposed a new search algorithm BTD+-MAC. The algorithm first selected the variables in separator to carry on the consistency checks and instantiation during search,so the efficiency of constraint propagation could be improved by reducing the width of the tree and further improved the efficiency of solving problems. We tested several sets of benchmark problems. The results show that the algorithm is more efficient than the MAC3 rm and BTD-MAC algorithm in solving the problem.更多还原