-
题名随机可满足实例集上警示传播算法的收敛性
被引量：11
- 1
-
-
作者
王晓峰
许道云
韦立
-
机构
贵州大学计算机科学系
-
出处
《软件学报》
EI
CSCD
北大核心
2013年第1期1-11,共11页
-
基金
国家自然科学基金(60863005
61111130186)
贵州大学研究生创新基金(2011033)
-
文摘
信息传播算法在求解随机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为连通分支的大小.
-
关键词
警示传播算法
收敛性分析
相变
可满足性问题
-
Keywords
warning propagation algorithm
convergence analysis
phase transition
satisfiability problem
-
分类号
TP301
[自动化与计算机技术—计算机系统结构]
-
-
题名警示传播算法收敛的充分条件
被引量：10
- 2
-
-
作者
王晓峰
许道云
-
机构
北方民族大学计算机科学系
贵州大学计算机科学系
-
出处
《软件学报》
EI
CSCD
北大核心
2016年第12期3003-3013,共11页
-
基金
国家自然科学基金(61462001
61262006
+4 种基金
61402017)
宁夏自然科学基金(NZ14108)
北方民族大学基金(2014XYZ 03
2014XBZ04)
"计算机应用技术"自治区重点学科项目~~
-
文摘
信息传播算法求解可满足问题时有惊人的效果,难解区域变窄.然而,因子图带有环的实例,信息传播算法不总有效,常表现为不收敛.对于这种现象,至今缺少系统的理论解释.警示传播(warning propagation,简称WP)算法是一种基础的信息传播算法,对WP算法的收敛性研究是其他信息传播算法收敛性研究的重要基础.在WP算法中,将警示信息的取值从{0,1}松弛为[0,1],利用压缩函数的性质,给出了WP算法收敛的一个充分条件.选取了两组不同规模的随机3-SAT实例进行实验模拟,结果表明:当子句与变元的比值?<1.8时,该判定条件有效.
-
关键词
警示传播算法
收敛性
可满足性问题
因子图
-
Keywords
warning propagation algorithm
convergence
satisfiability problem
factor graph
-
分类号
TP301
[自动化与计算机技术—计算机系统结构]
-
-
题名规则实例集上警示传播算法的收敛性
被引量：3
- 3
-
-
作者
王晓峰
李强
丁红胜
-
机构
北方民族大学计算机科学系
-
出处
《计算机科学》
CSCD
北大核心
2015年第1期279-284,共6页
-
基金
国家自然科学基金(61363001
61262006
+6 种基金
60863005
61462001)
宁夏科学基金(NXXT14009
NZ14108
NGY2012096)
北方民族大学基金(2014XYZ03
2014XYS17)资助
-
文摘
信息传播算法求解随机3-SAT问题时非常有效,能使难解区域变窄。然而,对于因子图带有环的实例,信息传播算法并不总有效,常表现为不收敛。对于这种现象,至今缺少系统的理论解释。警示传播(Warning Propagation,WP)算法是一种基础的信息传播算法,对WP算法的收敛性研究是其它信息传播算法收敛性研究的重要基础。将一个3-SAT问题转换为具有规则结构的(3,4)-SAT问题,(3,4)-SAT问题是NP-完全的。基于(3,4)-SAT问题的规则结构性质,分析WP算法的收敛性。选取了3组不同规模的实例进行实验模拟,结果表明:在这种规则结构的可满足性实例集上,WP算法的收敛性有较大提高。
-
关键词
警示传播算法
收敛性
可满足性问题
规则结构
-
Keywords
warning propagation algorithm,convergence,satisfiability problems, regular structure
-
分类号
TP301
[自动化与计算机技术—计算机系统结构]
-
-
题名基于结构熵的警示传播算法收敛性分析
被引量：3
- 4
-
-
作者
牛进
王晓峰
林青文
-
机构
北方民族大学计算机科学与工程学院
-
出处
《计算机应用研究》
CSCD
北大核心
2021年第3期760-763,776,共5页
-
基金
国家自然科学基金资助项目(61462001,61762019,61862051,61962002)
北方民族大学重大专项资助项目(ZDZX201901)
+1 种基金
宁夏自然科学基金资助项目(NZ17111,2019AAC03120,2019AAC03119)
北方民族大学校级科研一般项目(2019XYZJK05)。
-
文摘
收敛性是评价信息传播算法性能的重要指标,信息传播算法求解可满足性问题时,命题公式的结构特征影响算法的收敛性,具有复杂结构的命题公式,信息传播算法不总收敛。为了系统地对此现象给予理论解释,借助于结构熵的方法和技术,提出命题公式的结构熵模型及其度量方法,计算随机可满足性实例的结构熵。警示传播算法(WP)作为信息传播算法的基本模型,分析WP算法的收敛性对于研究其他信息传播算法的收敛性具有重要意义,分析了WP算法收敛性与结构熵之间的关系,给出WP算法收敛的判定条件。通过实验分析,该方法有效可行。
-
关键词
可满足性问题
命题公式
结构熵
警示传播算法
收敛性
-
Keywords
satisfiability problem
propositional formula
structural entropy
warning propagation algorithm
convergence
-
分类号
TP393.04
[自动化与计算机技术—计算机应用技术]
-
-
题名基于树宽的警示传播算法收敛性分析
被引量：2
- 5
-
-
作者
谢志新
王晓峰
于卓
曹泽轩
吴宇翔
莫淳惠
-
机构
北方民族大学计算机科学与工程学院
北方民族大学图像图形智能处理国家民委重点实验室
-
出处
《计算机应用研究》
CSCD
北大核心
2022年第10期3061-3064,3077,共5页
-
基金
国家自然科学基金资助项目(62062001,61762019,61862051,61962002)
宁夏自然科学基金资助项目(2020AAC03214,2020AAC03219,2019AAC03120,2019AAC03119)
+1 种基金
北方民族大学重大专项资助项目(ZDZX201901)
北方民族大学研究生创新项目(YCX22197)。
-
文摘
警示传播算法作为一种基本的信息传播算法,其收敛时求解可满足性问题十分有效,但因子图结构较为复杂时,算法往往不收敛导致求解失败。为了对这种现象给予理论解释,同时对警示传播算法收敛性进行有效分析,利用树分解方法构造了命题公式对应因子图的树宽度量模型,计算可满足随机实例的树宽。建立树宽与警示传播算法收敛性之间的关系,给出了基于树宽的警示传播算法收敛性判定条件。通过实验分析,结果表明该方法有效,对于分析其他信息传播算法收敛性分析研究具有十分重要的意义。
-
关键词
警示传播算法
收敛性
树宽
命题公式
可满足性问题
-
Keywords
warning propagation(WP)algorithm
convergence
tree width
propositional formula
satisfiability problem
-
分类号
TP301
[自动化与计算机技术—计算机系统结构]
-
-
题名基于K维结构熵的调查传播算法收敛性分析
被引量：2
- 6
-
-
作者
梁晨
王晓峰
刘子琳
芦磊
牛鹏飞
-
机构
北方民族大学计算机科学与工程学院
北方民族大学图像图形智能处理国家民委重点实验室
-
出处
《计算机应用研究》
CSCD
北大核心
2022年第5期1432-1436,共5页
-
基金
国家自然科学基金资助项目(62062001,61762019,61862051,61962002)
北方民族大学重大专项资助项目(ZDZX201901)
宁夏自然科学基金资助项目(2020AAC03214,2020AAC03219,2019AAC03120,2019AAC03119)。
-
文摘
信息传播算法在可满足性(SAT)问题上性能表现优越,其收敛性却依赖于因子图的结构复杂程度,至今缺少系统的理论解释。调查传播算法(SP)是解决SAT问题效果最好的信息传播算法。为有效分析SP算法的收敛性,借助因子图转换技术和鲁汶算法划分因子图社区,基于K维结构熵理论,提出了SAT实例的K维结构熵度量模型,得出了随机SAT实例的K维结构熵。分析了SP算法收敛性与K维结构熵之间的关系,给出了SP算法收敛性的K维结构熵阈值。实验证明该方法有效。
-
关键词
可满足性问题
K维结构熵
调查传播算法
收敛性
-
Keywords
satisfiability problem
K-dimensional structural entropy
survey propagation algorithm
convergence
-
分类号
TP301.6
[自动化与计算机技术—计算机系统结构]
-
