约束满足问题求解的符号OBDD技术  

An OBDD-based technique for the constraint satisfaction problem

作　　者：徐周波[1] 古天龙[1] 

机构地区：[1]桂林电子科技大学计算机科学与工程学院,广西桂林541004

出　　处：《桂林电子科技大学学报》2010年第6期570-572,共3页Journal of Guilin University of Electronic Technology

基　　金：广西自然科学基金(0832006Z)

摘　　要：约束满足问题(CSP)是人工智能中一个重要的研究课题。通过讨论CSP的有序二叉决策图(OBDD)描述,给出了CSP的符号OBDD求解算法。其算法是在CSP的符号表示的基础上,首先对CSP中的所有变量根据其在约束图中的度的大小进行递增排序,然后按照此变量序将CSP分成n个子问题分别进行求解,其中n为CSP中变量数,最后利用OBDD的"与"操作合并所有子问题,所得的OBDD即为满足所有约束的CSP的所有解。通过与桶消元算法和符号OBDD直接求解算法的实验对比,证明本算法具有明显的优越性。Constraint satisfaction problem（CSP） is an important research branch in artificial intelligence.In the paper,CSP is formulated by ordered binary decision diagram（OBDD）,and the symbolic OBDD algorithm for CSP is proposed.Based on the symbolic OBDD formulation of CSP,all the variables in the CSP are ordered in increasing order by its degree in the constraint graph.With this variable order,the CSP is decomposed into n sub-problems,where n is the number of variables in the CSP.Then the ＂AND＂ operation of OBDD is used to conjoin all sub-problems,and all solutions of CSP is found which are represented by OBDD.The simulation results show that the symbolic algorithm is more efficient than bucket elimination algorithm and direct algorithm based on OBDD.

关 键 词：约束满足问题 符号算法 有序二叉决策图(OBDD) 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]