关键词: 约束满足问题，符号算法，桶消元，有序二叉决策图(0BDD)

Abstract: Bucket elimination algorithm is a typical reasoning method for the constraint satisfaction problem(CSP). Aiming at the state explosion problem of bucket elimination algorithm, ordered binary decision diagram(OBDD) technique was combined with bucket-elimination algorithm, and a symbolic 013DI}based algorithm for CSP was proposed. By encoding each variable and each value in the domain as binary variables,CSP was encoded as a propositional satisfiability (SAID) problem,and then CSP was formulated symbolically by OBDD. Based on the ideas of bucket elimination algorithm and the symbolic OBDD representation of CSP, the CSP was solved implicitly by the ANl)operator and the EXIST operator of OBDD，so that the explicit enumeration of states in traditional algorithms was avoided. The simulation results show that the symbolic algorithm is more efficient than both the bucket elimination algorithm and the direct algorithm based on OBDD.

Key words: Constraint satisfaction problem, Symbolic algorithm, Bucket elimination, Ordered binary decision diagram(OBDD)