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

• 作者: 古天龙 徐周波
• 来源期刊: 桂林电子科技大学学报
• 学科: 工学
• 关键词: 约束满足问题 符号算法 有序二叉决策图(OBDD)
• 年，卷（期）: 2010,（6）
• 页码范围: 570-572
• 分类号: TP301.6
• 字数: 1745字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-808X.2010.06.010

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	古天龙	桂林电子科技大学计算机科学与工程学院	207	1546	18.0	30.0
2	徐周波	桂林电子科技大学计算机科学与工程学院	53	284	8.0	15.0