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 MAC3rm and BTD-MAC algorithm in solving the problem.

Key words: artificial intelligence, constraint satisfaction problem, tree decomposition, backtracking search, heuristic method