OBDD-based Bucket Elimination Algorithm for Constraint Satisfaction Problem
Fengying Li · 2011
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 OBDD-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(SAT) 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 AND 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.