-
题名约束满足问题求解的符号OBDD桶消元算法
被引量:4
- 1
-
-
作者
徐周波
古天龙
常亮
李凤英
-
机构
西安电子科技大学电子工程学院
桂林电子科技大学计算机科学与工程学院
-
出处
《计算机科学》
CSCD
北大核心
2011年第7期200-202,219,共4页
-
基金
国家自然科学基金(60963010
60903079
+1 种基金
61063002)
广西自然科学基金重点项目(0832006Z)资助
-
文摘
桶消元算法是求解约束满足问题的一种典型推理方法。针对桶消元算法面临的状态空间爆炸问题,将有序二叉决策图(OBDD)技术与该算法结合起来,给出了约束满足问题的一种求解算法。通过对约束满足问题中变量和域值的编码,将CSP问题转化为命题可满足性问题,给出了约束满足问题的OBDD表示方法;基于桶消元的算法思想,在约束满足问题的OBDD表示的基础上,利用OBDD的"与"操作和"量化"操作等,避免了传统算法中状态的显式枚举,隐式地实现了对CSP的求解。对大量随机生成的测试用例进行了实验分析,结果表明提出的符号算法明显优于桶消元法和符号直接求解法。
-
关键词
约束满足问题
符号算法
桶消元
有序二叉决策图(OBDD)
-
Keywords
Constraint satisfaction problem
Symbolic algorithm
Bucket elimination
Ordered binary decision diagram(OBDD)
-
分类号
TP301.6
[自动化与计算机技术—计算机系统结构]
-
-
题名基于桶消元的贝叶斯网络推理平台的设计与实现
被引量:2
- 2
-
-
作者
朱永利
胡卫华
-
机构
华北电力大学计算机学院
-
出处
《计算机工程》
CAS
CSCD
北大核心
2004年第15期178-180,共3页
-
文摘
结合新一代开发工具.net和XML技术实现了贝叶斯网络推理实验平台的构建,新构建的实验平台还很好地克服了国际市场上已有的此类平台的不足,为贝叶斯网络的进一步研究打下了坚实的基础。
-
关键词
桶消元算法
贝叶斯网络
NET技术
XML
实验平台
-
Keywords
Bucket elimination
Bayesian networks
.Net technology
XML
Experimental platform
-
分类号
TP393.02
[自动化与计算机技术—计算机应用技术]
-
-
题名基于桶消元的联合树算法
被引量:1
- 3
-
-
作者
邢永康
沈一栋
-
机构
重庆大学计算机科学与工程学院
-
出处
《计算机科学》
CSCD
北大核心
2001年第6期101-105,共5页
-
基金
国家自然科学基金
教育部跨世纪优秀人才基金
-
文摘
一、引言
联合树算法[1]是一种应用广泛的信度网推理算法.根据不同的消息传递方案,可以将联合树算法分为两种:一种基于Hugin消息传递方案,称为Hugin联合算法;另和中采用Shafer-Shenoy消息传递方案[2],称为Shafer-Shenoy联合树算法.下文除特别申明外,提到的联合树算法都是指Hugin联合树算法.
-
关键词
人工智能
桶消元
聚合树算法
消息传递
-
Keywords
Belief networks, Bucket elimination, Junction tree algorithm
-
分类号
TP18
[自动化与计算机技术—控制理论与控制工程]
-
-
题名基于桶消元的数控机床故障模糊贝叶斯网络推理方法
- 4
-
-
作者
高新勤
杜景霏
张艳平
-
机构
西安理工大学机械与精密仪器工程学院
-
出处
《航空精密制造技术》
2016年第5期14-18,共5页
-
基金
国家自然科学基金项目(51575443)
陕西省教育厅重点实验室科学研究计划项目(16JS075)
-
文摘
用模糊数描述节点的多种故障状态,用模糊子集描述根节点的故障概率,用贝叶斯网络的条件概率表描述节点间的不确定关系,构建数控机床故障的模糊贝叶斯网络;采用桶消元算法,对数控机床故障的模糊贝叶斯网络进行推理和计算,获得根节点的后验概率,为数控机床故障诊断与分析提供依据;最后,以数控机床刀架系统故障的贝叶斯网络推理过程为例,验证所提理论和方法的有效性。
-
关键词
桶消元算法
模糊贝叶斯网络
数控机床
故障推理
刀架系统
-
Keywords
Bucket elimination algorithm
fuzzy Bayesian network
numerical control machine tool
fault reasoning
tool carrier system
-
分类号
TH166
[机械工程—机械制造及自动化]
TP391
[自动化与计算机技术—计算机应用技术]
-
-
题名一种基于桶树的自动推理问题求解算法
- 5
-
-
作者
袁暋
胡春玲
胡学钢
姚宏亮
-
机构
合肥学院网络与智能信息处理重点实验室
合肥工业大学计算机与信息学院
-
出处
《计算机科学》
CSCD
北大核心
2013年第1期211-217,共7页
-
基金
国家自然科学基金(60975034)
安徽省教育厅自然科学一般项目(KJ2010B177)
合肥学院人才科研基金(13RC01)资助
-
文摘
桶消元和连接树推理算法是处理自动推理问题的两种常用的推理算法。针对连接树推理算法中消息传播效率问题,提出了一种能有效进行消息传播的连接树推理算法JTR。针对桶消元推理算法BE处理多任务的自动推理问题效率低下的问题,采用连接树结构和连接树推理算法JTR的消息传播方式对桶消元算法BE进行改进和扩展,提出了一种桶树推理算法BJTR。通过对算法BE、BTE和BJTR的时空性能分析发现:与同类算法BTE相比,算法BJTR在空间略有下降的情况下提高了时间性能;针对多任务的自动推理问题,与桶消元推理算法BE相比,BJTR算法的空间略有下降,时间性能得到明显提高;并通过实例和实验进一步验证了算法BJTR针对多任务的自动推理任务具有良好的时间性能。
-
关键词
自动推理
多任务
桶消元
连接树
桶-树
-
Keywords
Automated reasoning
Multi-task
Bucket elimination
Join-tree
Bucket-tree
-
分类号
TP181
[自动化与计算机技术—控制理论与控制工程]
-
-
题名Credal网络推理的一种不完全枚举法
被引量:1
- 6
-
-
作者
熊文涛
齐欢
余胜平
-
机构
华中科技大学系统工程研究所
孝感学院数学系
-
出处
《计算机工程与应用》
CSCD
北大核心
2009年第31期27-29,33,共4页
-
基金
国家自然科学基金No.60774036
孝感学院青年基金资助No.Z200803~~
-
文摘
Credal网络是研究不确定环境下知识表示和因果推理的一种图模型,其条件概率值可以用不精确的区间或不等式定性地表示,使得表达方式更加灵活有效。Credal网络的推理是计算一定证据下的后验概率最大值和最小值,给出了一种Credal网络推理的新方法,该方法是在桶消元框架下通过枚举计算部分因子函数值,使计算量大大减小,并且可以得到精确的结果。最后用一个实例说明了该方法的可行性。
-
关键词
Credal网络
贝叶斯网络
桶消元
枚举
-
Keywords
Credal networks
bayesian networks
bucket elimination
enumeration
-
分类号
TP181
[自动化与计算机技术—控制理论与控制工程]
-
-
题名加权约束满足问题的符号ADD求解算法
被引量:5
- 7
-
-
作者
徐周波
古天龙
常亮
-
机构
西安电子科技大学电子工程学院
桂林电子科技大学计算机科学与工程学院
-
出处
《模式识别与人工智能》
EI
CSCD
北大核心
2011年第1期14-21,共8页
-
基金
国家自然科学基金(No.60963010
60903079)
广西自然科学基金(No.0832006Z)资助项目
-
文摘
加权约束满足问题(WCSP)是一类软约束满足问题.给出WCSP的代数决策图(ADD)描述,以及基于ADD的两种符号求解算法.首先,通过对变量和变量域值的二进制编码,给出软约束图的ADD表示.其次,将分支定界搜索算法与桶消元算法及符号ADD技术相结合,在静态变量序下,利用结点一致性预处理技术,对WCSP问题进行符号ADD求解.通过引入有向弧一致性计数技术提高符号ADD算法的搜索下界,对符号ADD求解算法作了改进.最后,对大量随机生成的测试用例进行实验分析.结果表明,文中算法在性能上明显优于带有存在有向弧一致性或结点一致性预处理技术的具有前向检查功能的深度优先分支定界搜索算法.
-
关键词
加权约束满足问题(WCSP)
分支定界
桶消元
符号算法
代数决策图(ADD)
-
Keywords
Weighted Constraint Satisfaction Problem (WCSP), Branch and Bound, BucketElimination, Symbolic Algorithm, Algebraic Decision Diagram (ADD)
-
分类号
TP301.6
[自动化与计算机技术—计算机系统结构]
-