检索结果-内蒙古大学图书馆

软件学报 2016年第12期27卷 3003-3013页

作者：王晓峰许道云北方民族大学计算机科学系宁夏银川750021 贵州大学计算机科学系贵州贵阳550025

信息传播算法求解可满足问题时有惊人的效果,难解区域变窄.然而,因子图带有环的实例,信息传播算法不总有效,常表现为不收敛.对于这种现象,至今缺少系统的理论解释.警示传播(warning propagation,简称WP)算法是一种基础的信息传播算法,... 详细信息

信息传播算法求解可满足问题时有惊人的效果,难解区域变窄.然而,因子图带有环的实例,信息传播算法不总有效,常表现为不收敛.对于这种现象,至今缺少系统的理论解释.警示传播(warning propagation,简称WP)算法是一种基础的信息传播算法,对WP算法的收敛性研究是其他信息传播算法收敛性研究的重要基础.在WP算法中,将警示信息的取值从{0,1}松弛为[0,1],利用压缩函数的性质,给出了WP算法收敛的一个充分条件.选取了两组不同规模的随机3-SAT实例进行实验模拟,结果表明:当子句与变元的比值?<1.8时,该判定条件有效.

关键词：警示传播算法收敛性可满足性问题因子图

来源：评论

学校读者我要写书评

暂无评论

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

引用

计算机科学 2015年第1期42卷 279-284页

作者：王晓峰李强丁红胜北方民族大学计算机科学系银川750021

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

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

关键词：警示传播算法收敛性可满足性问题规则结构

来源：评论

学校读者我要写书评

暂无评论

随机可满足实例集上警示传播算法的收敛性

引用

软件学报 2013年第1期24卷 1-11页

作者：王晓峰许道云韦立贵州大学计算机科学系贵州贵阳550025

信息传播算法在求解随机kSAT问题时有惊人的效果,难解区域变窄.对于这种现象,至今缺少系统的理论解释.警示传播(warning propagation,简称WP)算法是一种基础的信息传播算法,为有效分析WP算法在随机kCNF公式上的收敛性,给出了随机kCNF公... 详细信息

信息传播算法在求解随机kSAT问题时有惊人的效果,难解区域变窄.对于这种现象,至今缺少系统的理论解释.警示传播(warning propagation,简称WP)算法是一种基础的信息传播算法,为有效分析WP算法在随机kCNF公式上的收敛性,给出了随机kCNF公式因子图上圈存在的相变点.在随机kCNF公式产生模型G(n,k,p)中,取k=3,p=d/n2,因子图中圈存在的相变点为p=1/8n2.当d<1/8时,因子图中开始出现圈,且每个连通分支至多有一个圈,因子图中含圈的连通分支的数目以及圈的长度均与n无关.因此,因子图是由森林和一些含有唯一圈的连通分支构成.证明了WP算法在这些实例集上高概率收敛,并且给出了算法的迭代步数为O(logn+s),其中,s为连通分支的大小.

关键词：警示传播算法收敛性分析相变可满足性问题

来源：评论

学校读者我要写书评

暂无评论

最大可满足性问题的算法优化及应用研究

最大可满足性问题的算法优化及应用研究

引用

作者：吴宇翔北方民族大学

学位级别：硕士

随着信息科学和网络技术的快速发展,组合优化问题(Combinatorial Optimization Problem)如今已是运筹学、离散数学和计算机科学中一个重要的研究方向。最大可满足性问题(Maximum Satisfiability,Max-SAT)属于典型的组合优化问题,现实生... 详细信息

随着信息科学和网络技术的快速发展,组合优化问题(Combinatorial Optimization Problem)如今已是运筹学、离散数学和计算机科学中一个重要的研究方向。最大可满足性问题(Maximum Satisfiability,Max-SAT)属于典型的组合优化问题,现实生活中的许多组合优化问题都可以转为最大可满足性问题,如机器人路径规划、车辆调度、资源配置和神经网络优化等问题。因此,关于Max-SAT问题求解算法的研究有着重要的理论意义和应用价值。Max-SAT是经典的NP难问题,随着人工智能和大数据技术的深度发展,数据量快速增加,Max-SAT的问题规模也逐渐扩大,求解Max-SAT问题原有的算法已不再适用。因此,研究人员开始设计新的求解算法或对原有的求解算法进行优化。基于此,本文设计了两种求解Max-SAT问题的非完备性算法,分别对警示传播算法和模拟退火算法进行优化,从而提高了求解Max-SAT问题的性能。具体地讲,本文的主要研究内容如下:(1)在警示传播算法的基础上,通过局部警示传播获取警示值,利用警示值对部分变元进行赋值,并对未赋值变元,引入变元权值计算,从而得到一组有效的变元赋值,最后对赋值结果采用随机游走的局部搜索算法。改进后的算法提高了警示传播算法在求解Max-SAT问题的全局搜索能力,可用于求解任何区域的实例,同时,在求解精度上也有所提高。结果证明:该算法性能优于传统警示传播算法。(2)提出了改进的快速模拟退火算法求解Max-SAT问题,采用变元权值计算初始解,结合基于概率的随机扰动和选择扰动两种方式,并在Metropolis接受准则中添加记忆功能,用于搜索当前局部最优解,其次引入高低温两种降温模式,较大程度地提高算法的全局搜索能力,进而加快算法的收敛速度,有效减少求解时间。最后,在公开数据集和随机生成的数据集上进行仿真实验,证明了本文改进算法的有效性。(3)设计开发了一个Max-SAT求解器,用于随机SAT实例生成和求解Max-SAT问题。

关键词：组合优化问题最大可满足性问题启发式算法警示传播算法模拟退火算法

来源：评论

学校读者我要写书评

暂无评论

求解若干图论问题的信息传播算法

求解若干图论问题的信息传播算法

引用

作者：王辛北方民族大学

学位级别：硕士

信息传播算法(Information Propagation Algorithm)是一种基于因子图(Factor Graph)的消息传播算法,在求解组合优化问题时有良好的效果。该算法在因子图上表现出的良好收敛特性可用于图论问题的建模。警示传播(Warning Propagation Algo... 详细信息

信息传播算法(Information Propagation Algorithm)是一种基于因子图(Factor Graph)的消息传播算法,在求解组合优化问题时有良好的效果。该算法在因子图上表现出的良好收敛特性可用于图论问题的建模。警示传播(Warning Propagation Algorithm,WP)算法和置信传播(Belief Propagation Algorithm,BP)算法是两种相对较为基础的信息传播算法,本文通过对警示传播算法和置信传播算法原理进行分析,设计了求解图论问题(最小割问题、双目标最小生成树问题和最小顶点覆盖集问题)的信息传播算法,取得良好效果,具体地讲,研究内容如下:(1)求解最小点覆盖集的置信传播算法利用随机图的马尔可夫性原理,将随机图各个节点的度映射为置信传播算法的不协调赋值集中的元素。选取度最大的节点,使用信息迭代方程,调整参数p的值,使算法收敛。最后,取收敛的节点作为最小顶点覆盖集中的点.实验证明,此方法有效。(2)求解双目标最小生成树的警示传播算法借助于受限Boltzmann机模型,将一个随机无向图转换为因子图,把求解无向图上的双目标最小生成树问题映射为求解因子图上的对应问题,进而设计一种求解双目标最小生成树问题的警示传播算法。选取由随机数种子产生的若干随机数构造邻接矩阵,生成对应的无向图实例,数值实验结果表明,该算法优于同类算法。(3)求解最小割的警示传播算法借助隐马尔可夫模型将无向图转换为因子图,把最小割问题映射为求解因子图上的相应问题,进而设计一种求解最小割的警示传播算法。选取了几组随机无向图实例进行数值实验,实验结果表明,该算法在求解速度上优于同类算法。

关键词：警示传播算法置信传播算法最小割双目标最小生成树最小顶点覆盖

来源：评论

学校读者我要写书评

暂无评论

基于警示传播与DPLL算法的启发式极性决策算法

引用

计算机科学 2010年第12期37卷 178-181,185页

作者：秦永彬许道云王晓峰贵州大学计算机科学与信息学院贵阳550025

警示传播(WP)算法是信息传播算法的重要基础,WP算法的本质是因子图上警示信息的迭代过程,在算法收敛时得到一组稳定的警示信息,并利用局部腔域得到公式变元的部分赋值。分析了警示传播算法的基本原理,给出了算法的改进。RB实例集上的实... 详细信息

警示传播(WP)算法是信息传播算法的重要基础,WP算法的本质是因子图上警示信息的迭代过程,在算法收敛时得到一组稳定的警示信息,并利用局部腔域得到公式变元的部分赋值。分析了警示传播算法的基本原理,给出了算法的改进。RB实例集上的实验证明,改进后的算法比原算法具有迭代次数和运行时间,提高了收敛速度。然而,在RB模型产生的大部分实例集上,警示传播算法不收敛,因而不能有效求解公式。警示传播算法与DPLL算法的组合使用使回溯计算次数大大降低,从而有效地弥补了WP算法的不足。通过在RB实例集上的测试实验表明,该方法是有效的。

关键词：信息传递警示传播算法收敛性 DPLL算法

来源：评论

学校读者我要写书评

暂无评论

信息传播算法收敛的后门集

引用

西南交通大学学报 2012年第1期47卷 32-38,62页

作者：王晓峰许道云秦永彬贵州大学计算机科学系贵州贵阳550025

为了探讨WP(警示传播)算法的收敛性,给出了WP算法收敛的后门集.通过对此后门集中的变元赋值,可将布尔公式简化成其因子图为树型结构的子公式,WP算法在子公式上收敛.最后,设计了一个求解该后门集的随机算法,并分析了该算法的可行性.结果... 详细信息

为了探讨WP(警示传播)算法的收敛性,给出了WP算法收敛的后门集.通过对此后门集中的变元赋值,可将布尔公式简化成其因子图为树型结构的子公式,WP算法在子公式上收敛.最后,设计了一个求解该后门集的随机算法,并分析了该算法的可行性.结果表明,所提出的求解该后门集的随机算法是有效的.

关键词：信息传递算法警示传播算法原理分析后门集算法收敛性

来源：评论

学校读者我要写书评

暂无评论

求解公式关键文字集的信息传播算法

引用

山东大学学报（工学版） 2011年第3期41卷 1-6页

作者：王晓峰许道云秦永彬贵州大学计算机科学系贵州贵阳550025

关键文字集影响判定布尔公式可满足性的判定难度。如果能找到公式的关键文字集或关键文字集的子集,就可使公式的可满足性判定变得容易。通过对警示传播算法的原理分析,发现高概率决定的部分变元对公式的求解难度有一定的影响。当某个子... 详细信息

关键文字集影响判定布尔公式可满足性的判定难度。如果能找到公式的关键文字集或关键文字集的子集,就可使公式的可满足性判定变得容易。通过对警示传播算法的原理分析,发现高概率决定的部分变元对公式的求解难度有一定的影响。当某个子句与变元之间的警示信息具有一致性时,表明该子句的可满足性完全由该变元的取值决定,其它变元的取值都不能使得该子句可满足。进一步研究发现,当该算法收敛时,具有一致性的警示信息对应的变元集合是关键文字集的子集,这就佐证了警示传播算法可用于求解公式的关键文字集。基于该算法的特征,给出了一个寻找公式关键文字集的信息传播算法。

关键词：信息传递警示传播算法原理分析关键文字

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：