随机可满足实例集上警示传播算法的收敛性 被引量：11

1

作者 王晓峰 许道云 韦立 《软件学报》 EI CSCD 北大核心 2013年第1期1-11,共11页

信息传播算法在求解随机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为连通分支的大小. 展开更多

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

在线阅读 下载PDF 职称材料

警示传播算法收敛的充分条件 被引量：10

2

作者 王晓峰 许道云 《软件学报》 EI CSCD 北大核心 2016年第12期3003-3013,共11页

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

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

在线阅读 下载PDF 职称材料

规则实例集上警示传播算法的收敛性 被引量：3

3

作者 王晓峰 李强 丁红胜 《计算机科学》 CSCD 北大核心 2015年第1期279-284,共6页

信息传播算法求解随机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算法的收敛性有较大提高。 展开更多

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

在线阅读 下载PDF 职称材料

一种求解最小割的警示传播算法 被引量：4

4

作者 王辛 王晓峰 李卫民 《电子学报》 EI CAS CSCD 北大核心 2019年第11期2386-2391,共6页

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

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

在线阅读 下载PDF 职称材料

一种改进的警示传播算法求解Max-SAT问题 被引量：2

5

作者 吴宇翔 王晓峰 +1 位作者 丁红胜 于卓 《计算机应用研究》 CSCD 北大核心 2022年第8期2290-2294,共5页

Max-SAT问题是SAT问题的优化版本,目标是在给定的子句集中找到一组变元赋值,使得满足子句数最多,该问题是典型的NP-hard问题。随着大数据和人工智能的深度发展,过去原有的算法已不再适用,设计新的求解算法或对已有的求解算法进行优化是... Max-SAT问题是SAT问题的优化版本,目标是在给定的子句集中找到一组变元赋值,使得满足子句数最多,该问题是典型的NP-hard问题。随着大数据和人工智能的深度发展,过去原有的算法已不再适用,设计新的求解算法或对已有的求解算法进行优化是目前研究的热点。针对警示传播算法求解随机Max-3-SAT问题的局限性,提出了一种基于变元权值计算的警示传播算法,结合随机游走算法,给出一种新型算法WWP+WalkSAT,通过改进求解的局限性,更好地得到一组有效的初始解,从而提高算法的局部搜索能力。利用2016年Max-SAT国际竞赛部分基准实例,将WWP+WalkSAT算法与八种局部搜索算法进行精度方面的对比实验。实验结果表明,WWP+WalkSAT算法有较好的性能。 展开更多

关键词 可满足性问题 最大可满足性问题 警示传播算法 局部搜索算法

在线阅读 下载PDF 职称材料

WP可解公式上警示传播算法收敛的有效条件 被引量：2

6

作者 崔立 王晓峰 牛进 《计算机应用研究》 CSCD 北大核心 2020年第5期1406-1410,共5页

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

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

在线阅读 下载PDF 职称材料

基于结构熵的警示传播算法收敛性分析 被引量：2

7

作者 牛进 王晓峰 林青文 《计算机应用研究》 CSCD 北大核心 2021年第3期760-763,776,共5页

收敛性是评价信息传播算法性能的重要指标,信息传播算法求解可满足性问题时,命题公式的结构特征影响算法的收敛性,具有复杂结构的命题公式,信息传播算法不总收敛。为了系统地对此现象给予理论解释,借助于结构熵的方法和技术,提出命题公... 收敛性是评价信息传播算法性能的重要指标,信息传播算法求解可满足性问题时,命题公式的结构特征影响算法的收敛性,具有复杂结构的命题公式,信息传播算法不总收敛。为了系统地对此现象给予理论解释,借助于结构熵的方法和技术,提出命题公式的结构熵模型及其度量方法,计算随机可满足性实例的结构熵。警示传播算法(WP)作为信息传播算法的基本模型,分析WP算法的收敛性对于研究其他信息传播算法的收敛性具有重要意义,分析了WP算法收敛性与结构熵之间的关系,给出WP算法收敛的判定条件。通过实验分析,该方法有效可行。 展开更多

关键词 可满足性问题 命题公式 结构熵 警示传播算法 收敛性

在线阅读 下载PDF 职称材料

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

8

作者 佘光伟 许道云 《计算机科学》 CSCD 北大核心 2018年第11期312-317,共6页

利用极小不可满足公式的临界特性,可以将任意的一个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问题 警示传播算法

在线阅读 下载PDF 职称材料

基于树宽的警示传播算法收敛性分析 被引量：1

9

作者 谢志新 王晓峰 +3 位作者 于卓 曹泽轩 吴宇翔 莫淳惠 《计算机应用研究》 CSCD 北大核心 2022年第10期3061-3064,3077,共5页

警示传播算法作为一种基本的信息传播算法,其收敛时求解可满足性问题十分有效,但因子图结构较为复杂时,算法往往不收敛导致求解失败。为了对这种现象给予理论解释,同时对警示传播算法收敛性进行有效分析,利用树分解方法构造了命题公式... 警示传播算法作为一种基本的信息传播算法,其收敛时求解可满足性问题十分有效,但因子图结构较为复杂时,算法往往不收敛导致求解失败。为了对这种现象给予理论解释,同时对警示传播算法收敛性进行有效分析,利用树分解方法构造了命题公式对应因子图的树宽度量模型,计算可满足随机实例的树宽。建立树宽与警示传播算法收敛性之间的关系,给出了基于树宽的警示传播算法收敛性判定条件。通过实验分析,结果表明该方法有效,对于分析其他信息传播算法收敛性分析研究具有十分重要的意义。 展开更多

关键词 警示传播算法 收敛性 树宽 命题公式 可满足性问题

在线阅读 下载PDF 职称材料

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

10

作者 王帅 王晓峰 +1 位作者 梁田 李志 《计算机工程与科学》 CSCD 北大核心 2021年第11期2056-2061,共6页

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

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

在线阅读 下载PDF 职称材料

基于警示传播与DPLL算法的启发式极性决策算法 被引量：3

11

作者 秦永彬 许道云 王晓峰 《计算机科学》 CSCD 北大核心 2010年第12期178-181,185,共5页

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

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

在线阅读 下载PDF 职称材料

一种求解双目标最小生成树的警示传播算法 被引量：6

12

作者 王辛 王晓峰 +1 位作者 许道云 杨德仁 《中国科学：信息科学》 CSCD 北大核心 2020年第10期1501-1510,共10页

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

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

原文传递

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

13

作者 王晓峰 许道云 秦永彬 《西南交通大学学报》 EI CSCD 北大核心 2012年第1期32-38,62,共8页

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

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

在线阅读 下载PDF 职称材料

求解公式关键文字集的信息传播算法 被引量：3

14

作者 王晓峰 许道云 秦永彬 《山东大学学报（工学版）》 CAS 北大核心 2011年第3期1-6,共6页

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

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

原文传递