规则实例集上警示传播算法的收敛性

来源 :计算机科学 | 被引量 : 0次 | 上传用户：ganglei2008

【摘要】

：

信息传播算法求解随机3-SAT问题时非常有效，能使难解区域变窄。然而，对于因子图带有环的实例，信息传播算法并不总有效，常表现为不收敛。对于这种现象，至今缺少系统的理论解释。警

【作者】

：

王晓峰李强丁红胜

【机构】

：

北方民族大学计算机科学系

【出处】

：

计算机科学

【发表日期】

：

2015年1期

【关键词】

：

警示传播算法收敛性可满足性问题规则结构 Warning propagation algorithm Convergence Satisfiability

下载到本地 , 更方便阅读

下载此文赞助VIP

声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架

论文部分内容阅读

信息传播算法求解随机3-SAT问题时非常有效，能使难解区域变窄。然而，对于因子图带有环的实例，信息传播算法并不总有效，常表现为不收敛。对于这种现象，至今缺少系统的理论解释。警示传播（Warning Propagation，WP）算法是一种基础的信息传播算法，对WP算法的收敛性研究是其它信息传播算法收敛性研究的重要基础。将一个3-SAT问题转换为具有规则结构的（3，4）-SAT问题，（3，4）-SAT问题是NP-完全的。基于（3，4）-SAT问题的规则结构性质，分析WP算法的收敛性。选取了3组不同规模的实例

其他文献

不同形态水分对煤自燃过程微观作用机制研究

制备不同外在水分和原始赋存水分含量的煤体,通过模拟煤自燃升温氧化过程得到不同温度下的氧化煤样;利用原位傅里叶红外变换光谱仪测定不同氧化煤样中活性官能团的含量,研究

期刊

煤自燃形态水分微观结构作用机制coal spontaneous combustionform moisturemicrostructureacti

解析政府部门人力资源激励中双因素理论

在当前情况下,政府部门应该在继续加强对人力资源的管理,使用更加合理和科学的办法来提升人力资源管理的工作质量,在进行人力资源激励时应该加大对双因素理论的应用力度,本文

期刊

政府部门人力资源激励双因素理论

草酸/聚乙二醇低温共熔体催化α-蒎烯水合反应

以天然有机二元羧酸草酸(OA)作为氢键供体,各种聚合度的聚乙二醇(PEG)作为氢键受体,构建出羧酸功能化低温共熔体(DES),将其用于催化α-蒎烯水合制备α-松油醇的反应中。傅里

期刊

Α-蒎烯Α-松油醇水合反应低温共熔体α-pineneα-terpineolhydrationdeep eutectic solvents

在消费类便携设备中实现精确的运动跟踪

以智能手机为主,包括智能腕表、健身追踪器和可听戴设备等在内的各类便携式联网电子设备,彻底改变了我们的生活。这些设备在数据采集中融入了处理功能和无线联网技术。但是,

期刊

运动跟踪数据采集用户体验运动传感器便携式设备便携设备头部运动智能手机

蓝牙5.2的新功能

蓝牙5.2增加低功耗同步通道(LE Isochronous Channels)功能来支持LE Audio,提升这个短距离无线标准。还有众多新功能陆续有来。随着LE Audio近期热闹登场,蓝牙技术联盟(SIG)

期刊

蓝牙技术联盟无线标准AUDIO修订版本SIG低功耗

基于NGN的网络安全技术研究

随着IPv6的部署和5G标准化的推进,下一代网络已成为业界关注的热点。通过分析下一代网络(Next Generation Network,NGN)的4层体系结构以及其关键技术,结合我国的网络特点,提

期刊

下一代网络网络体系结构网络安全

碱改性ZSM-5分子筛及其甲醇芳构化性能

利用乙酸钠和柠檬酸钠对ZSM-5分子筛进行脱硅改性处理,并通过XRD、SEM、NH_(3)-TPD、^(27)Al MAS NMR、吡啶吸附红外光谱和N2吸附-脱附等表征手段对ZSM-5分子筛结构、酸量、

期刊

ZSM-5分子筛碱改性介孔甲醇芳构化ZSM-5 zeolitealkali modifiedmesoporousaromatization of

规则实例集上警示传播算法的收敛性

其他学术论文