Computer Science ›› 2011, Vol. 38 ›› Issue (7): 200-202.
Previous Articles Next Articles
XU Zhou-bo,GU Tian-long,CHANG Liang,LI Feng-ying
Online:
Published:
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)
XU Zhou-bo,GU Tian-long,CHANG Liang,LI Feng-ying. OBDD-based Bucket Elimination Algorithm for Constraint Satisfaction Problem[J].Computer Science, 2011, 38(7): 200-202.
0 / / Recommend
Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks
URL: https://www.jsjkx.com/EN/
https://www.jsjkx.com/EN/Y2011/V38/I7/200
Cited