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

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

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

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

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

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

来源：评论

学校读者我要写书评

暂无评论

一种求解最小割的警示传播算法

引用

电子学报 2019年第11期47卷 2386-2391页

作者：王辛王晓峰李卫民北方民族大学计算机科学与工程学院宁夏银川750021 上海大学计算机工程与科学学院上海200444

最小割问题(minimum cut problem)是NP(Non-deterministic Polynomial)难问题,警示传播算法(warning propagation)是一种基于因子图的消息传递算法,可用于求解组合优化问题.首先,本文借助隐马尔可夫模型将无向图转换为因子图,将求解最... 详细信息

最小割问题(minimum cut problem)是NP(Non-deterministic Polynomial)难问题,警示传播算法(warning propagation)是一种基于因子图的消息传递算法,可用于求解组合优化问题.首先,本文借助隐马尔可夫模型将无向图转换为因子图,将求解最小割映射为求解因子图的相应问题.进而设计一种求解最小割的警示传播算法.最后,选取了几组随机无向图实例进行数值实验,实验结果表明,该算法在求解速度上优于同类算法.

关键词：组合优化最小割警示传播算法隐马尔可夫模型概率算法马尔科夫化

来源：评论

学校读者我要写书评

暂无评论

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

引用

软件学报 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为连通分支的大小.

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

来源：评论

学校读者我要写书评

暂无评论

一种求解双目标最小生成树的警示传播算法

引用

中国科学：信息科学 2020年第10期50卷 1501-1510页

作者：王辛王晓峰许道云杨德仁北方民族大学计算机科学与工程学院银川750021 贵州大学计算机系贵阳550025 宁夏医科大学理学院银川750004

双目标最小生成树问题是一个NP-难问题,在光缆通信、智能控制等领域有其重要的应用价值.警示传播(warning propagation,WP)算法是一种基于因子图的消息传递算法,可用于求解组合优化问题.借助于Boltzmann机模型使一个无向图转换为因子图... 详细信息

双目标最小生成树问题是一个NP-难问题,在光缆通信、智能控制等领域有其重要的应用价值.警示传播(warning propagation,WP)算法是一种基于因子图的消息传递算法,可用于求解组合优化问题.借助于Boltzmann机模型使一个无向图转换为因子图,将求解无向图上的双目标最小生成树问题映射为求解因子图上的对应问题,进而设计一种求解双目标最小生成树问题的警示传播算法.选取由随机数种子产生的若干随机数构造邻接矩阵,生成对应的无向图实例,数值实验结果表明,该算法优于同类算法.

关键词：双目标优化组合优化警示传播算法最小生成树因子图

来源：评论

学校读者我要写书评

暂无评论

警示传播算法在求解命题公式骨干集中的应用研究

警示传播算法在求解命题公式骨干集中的应用研究

引用

作者：王帅北方民族大学

学位级别：硕士

近年来随着互联网技术的迅速发展,在人工智能、调度计划、交通运输等方面涌现出许多新的复杂问题,通常可将这些问题转化为命题公式的可满足性判定问题。在求解命题公式的可满足性判定问题时,算法往往都具有一定的局限性,精确算法求解时... 详细信息

近年来随着互联网技术的迅速发展,在人工智能、调度计划、交通运输等方面涌现出许多新的复杂问题,通常可将这些问题转化为命题公式的可满足性判定问题。在求解命题公式的可满足性判定问题时,算法往往都具有一定的局限性,精确算法求解时间往往较长,近似算法容易陷入局部最优。骨干变元集是命题公式中的一种特殊隐藏结构,给该变元赋值后,使得化简后的公式容易求解。然而,往往求解骨干集比较困难。警示传播算法是一种基于因子图的信息迭代算法,能够有效给出变量的边缘概率分布。对于一个命题公式可满足性判定问题的实例,其骨干变元的取值是固定的,这就佐证了使用警示传播算法计算骨干变元边缘概率的可行性,进而确定骨干变元集。本文探索利用警示传播算法求解命题公式中的骨干集,具体地讲,有如下创新点:1)深入分析了警示传播算法的数学原理,在算法收敛时找出其固定变元与骨干变元之间的关系。基于这样的特征修改警示传播算法的迭代方程、变元赋值条件,设计一种求解命题公式骨干集的警示传播算法。结果表明:该方法求解命题公式骨干集时非常有效。2)在实际应用上,本文将求解命题公式骨干集的警示传播算法应用于多目标路线规划系统中。通过将路线模型转换为因子图模型进行求解,利用求解结果为用户提供相应路线,具有很好的时间效率。

关键词：警示传播算法 SAT问题因子图骨干集

来源：评论

学校读者我要写书评

暂无评论

警示传播算法求解正则(3,4)-SAT问题

警示传播算法求解正则(3,4)-SAT问题

引用

作者：佘光伟贵州大学

学位级别：硕士

利用极小不可满足公式的临界特性,可以将任意一个3-CNF公式多项式时间归约转换为一个正则（3,4）-CNF公式,从而得到一个保留NP完全性的正则（3,4）-SAT问题。对于归约转换后的正则（3,4）-SAT实例集而言,警示传播算法（Warning Propagat... 详细信息

利用极小不可满足公式的临界特性,可以将任意一个3-CNF公式多项式时间归约转换为一个正则（3,4）-CNF公式,从而得到一个保留NP完全性的正则（3,4）-SAT问题。对于归约转换后的正则（3,4）-SAT实例集而言,警示传播算法（Warning Propagation,WP）在其上高概率收敛,然而难以有效地返回关于变元的一组真值指派（如果该实例可满足）。因此,在归约转换下的正则（3,4）-SAT问题上,WP算法求解失效。本文围绕该问题,基于归约转换下正则（3,4）-CNF公式的结构特征,提出了WP算法的一种修正策略来专门用于求解归约转换下的正则（3,4）-SAT实例。同时基于WP算法的信息传播机制,引出了WP-可解公式的结构定义,探索了WP算法的收敛性特征条件。主要的研究成果如下:（1）从三个方面比较了归约转换后的正则（3,4）-CNF公式与原3-CNF公式在公式的结构特征上所发生的变化:一是归约转换后的正则（3,4）-CNF公式中变元正负出现次数之差趋于稳定;二是归约转换后的正则（3,4）-CNF公式中每个变元至少被包含在两个圈中;三是一个归约转换后且可满足的正则（3,4）-CNF公式中至少含有规模大小为9m的脊梁（m为原3-CNF公式子句数）。（2）在WP算法求解随机3-SAT实例集的实验中,发现随着子句约束密度的增大,WP算法会高概率地收敛于平凡稳定点,这意味着算法在初始迭代求解时只能以随机的方式来给变元赋值,从而对算法求解SAT问题的性能造成了影响。因此提出了一种基于最大极性变元的策略来改进WP算法。实验结果表明:改进的WP算法比原算法求解效果更好。（3）针对WP算法在归约转换下且可满足的正则（3,4）-SAT实例集上求解失效的问题,基于归约转换下正则（3,4）-CNF公式中变元正负出现次数趋于稳定的结构特征,提出了WP算法的一种修正策略。实验结果表明:修正的WP算法可以重新有效求解归约转换下的正则（3,4）-SAT实例集。（4）证明了树公式是WP-可解公式。进一步,基于植入分布模型Pn,pplant,证明了以WP-可解的3-CNF公式作为输入,WP算法高概率收敛。

关键词：极小不可满足公式正则(3,4)-SAT问题警示传播算法 WP-可解公式

来源：评论

学校读者我要写书评

暂无评论

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

引用

计算机科学 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算法的收敛性有较大提高。

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

来源：评论

学校读者我要写书评

暂无评论

一种求解命题公式骨干集的警示传播算法

引用

计算机工程与科学 2021年第11期43卷 2056-2061页

作者：王帅王晓峰梁田李志北方民族大学计算机科学与工程学院宁夏银川750021

警示传播WP算法是一类重要的信息传播算法,在命题公式的可满足性判定中非常有效。通过对WP算法的数学原理分析发现,当算法收敛时以高概率固定部分变元的赋值,可以对公式进行化简。基于这样的特征修改WP算法的迭代方程和变元赋值条件,设... 详细信息

警示传播WP算法是一类重要的信息传播算法,在命题公式的可满足性判定中非常有效。通过对WP算法的数学原理分析发现,当算法收敛时以高概率固定部分变元的赋值,可以对公式进行化简。基于这样的特征修改WP算法的迭代方程和变元赋值条件,设计了一种求解命题公式骨干集的信息传播算法。当变元数目超过400时,与经典骨干集求解算法对比,效率提高了40%,与目前常用算法对比也有10%的提高。结果表明,所提算法求解命题公式骨干集时非常有效。

关键词：警示传播算法 SAT问题因子图骨干集

来源：评论

学校读者我要写书评

暂无评论

用于求解正则(3,4)-SAT实例集的修正警示传播算法

引用

计算机科学 2018年第11期45卷 312-317页

作者：佘光伟许道云贵州大学计算机科学与技术学院贵阳550025

利用极小不可满足公式的临界特性,可以将任意的一个3-CNF公式多项式时间归约转换为一个正则(3,4)-CNF公式,从而得到一个保留NP完全性的正则(3,4)-SAT问题。警示传播算法(Warning Propagation,WP)在归约转换后的正则(3,4)-SAT实例集上高... 详细信息

利用极小不可满足公式的临界特性,可以将任意的一个3-CNF公式多项式时间归约转换为一个正则(3,4)-CNF公式,从而得到一个保留NP完全性的正则(3,4)-SAT问题。警示传播算法(Warning Propagation,WP)在归约转换后的正则(3,4)-SAT实例集上高概率收敛,但在任意一个实例上都无法判断公式的可满足性,因此算法求解失效。对于一个归约转换后的正则(3,4)-CNF公式,每一变元出现的正负次数之差具有趋于稳定的结构特征,基于该特征,提出基于变元正负出现次数规则的WP算法来求解归约转换后的正则(3,4)-SAT实例。实验结果表明,修正的WP算法对正则公式的可满足性判定有效,从而可以利用公式的正则性特征进一步研究WP算法的收敛性特征条件。

关键词：极小不可满足公式正则(3,4)-SAT问题警示传播算法

来源：评论

学校读者我要写书评

暂无评论

WP可解公式上警示传播算法收敛的有效条件

引用

计算机应用研究 2020年第5期37卷 1406-1410页

作者：崔立王晓峰牛进北方民族大学计算机科学与工程学院银川750021

通过对警示传播(warning propagation,WP)算法的数学原理分析,高概率确定的部分变元与公式的骨干集和后门集有密切关系。针对WP算法收敛性的研究,基于骨干集和后门集定义WP-可解公式,利用在G(n,3,m)模型和植入指派模型下证明WP算法的收... 详细信息

通过对警示传播(warning propagation,WP)算法的数学原理分析,高概率确定的部分变元与公式的骨干集和后门集有密切关系。针对WP算法收敛性的研究,基于骨干集和后门集定义WP-可解公式,利用在G(n,3,m)模型和植入指派模型下证明WP算法的收敛性,给出算法收敛的充要条件。最后,通过在植入指派的公式产生模型上进行数值实验验证,结果表明:如果一个可满足性公式WP-可解公式,当且仅当WP算法高概率收敛。

关键词：警示传播算法骨干集后门集 WP-可解公式实例产生模型

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：