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

摘要：

约束满足问题(CSP)是人工智能中一个重要的研究课题.通过讨论CSP的有序二叉决策图(OBDD)描述,给出了CSP的符号OBDD求解算法.其算法是在CSP的符号表示的基础上,首先对CSP中的所有变量根据其在约束图中的度的大小进行递增排序,然后按照此变量序将CSP分成n个子问题分别进行求解,其中n为CSP中变量数,最后利用OBDD的"与"操作合并所有子问题,所得的OBDD即为满足所有约束的CSP的所有解.通过与桶消元算法和符号OBDD直接求解算法的实验对比,证明本算法具有明显的优越性.

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

所属期刊栏目：30

分类号：TP301.6(计算技术、计算机技术)

资助基金：广西自然科学基金0832006Z

在线出版日期：2011-04-15（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：570-572