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

doi:10.11896/j.issn.1002-137X.2015.01.062

摘要/Abstract

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

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

Abstract: Message propagation algorithms are very effective in finding satisfying assignments for 3-SAT instances,and they can make hard region become narrower.However,message propagation algorithms do not always converge for graphs with cycles.Unfortunately,rigorous theory proof of this phenomenon is still lacking.Warning propagation algorithm is the most basic message propagation algorithm,and we analysed convergence of the warning propagation algorithm.Lastly,experimental results show that convergence of the warning propagation algorithm is improved for (3,4)-SAT instances.

Key words: Warning propagation algorithm,Convergence,Satisfiability problems,Regular structure

王晓峰,李强,丁红胜. 规则实例集上警示传播算法的收敛性[J]. 计算机科学, 2015, 42(1): 279-284. https://doi.org/10.11896/j.issn.1002-137X.2015.01.062

WANG Xiao-feng, LI Qiang and DING Hong-sheng. Convergence of Warning Propagation Algorithm for Regular Structure Instances[J]. Computer Science, 2015, 42(1): 279-284. https://doi.org/10.11896/j.issn.1002-137X.2015.01.062

参考文献

[1] Martin D,Alan F,Michael M.A probabilistic analysis of randomly generated binary constraint satisfaction[J].Theory Computer Science,2003,290:1815-1828
[2] Creignou N,Eaude H.The SAT-UNSAT transition for random constraint satisfaction problems[J].Discrete Mathematics,2009,309:2085-2099
[3] Martin O C,Monasson R,Zecchina R.Statistical mechanicsmethods and phase transitions in optimization[J].Theory Computer Science,2001,265:3-67
[4] Tsang E.A glimpse of constraint satisfaction[J].Artificial Intelligence Review,1999,13:215-277
[5] Bourgain J.Sharp thresholds of graph properties and the k-SATproblem[J].Journal of The American Mathematical Society,1999,2(4):1017-1054
[6] Kirkpatrick S,Selman B.Critical behavior in the satisfiability of random Boolean Formulae[J].Science,1994,4(5163):1297-1301
[7] Mertens S,Mezard M,Zecchina R.Threshold values of random k-SAT from the cavity method[J].Random Structure Algorithms,2006,28:340-373
[8] Kaporis A,Kirousis L,Lalas E.The probabilistic analysis of agreedy satisfiability algorithm[J].Random structures & Algorithms,2006,8(4):444-480
[9] Dubois O,Boufkhad Y,Mandler J.Typical random 3-sat formulae and the satisfiability threshold[J].Electronic Colloquium on Computational Complexity,2003,10(7):1-2
[10] Moskewicz M W,Madigan C F,Zhao Y.Chaff:Engineering an efficient SAT solver[C]∥Proceedings of the 38th annual Design Automation Conference.New York,ACM,2001:530-535
[11] Aurell E,Gordon U,Kirkkpatrick S.Comparing beliefs,sur-veys,and random walks[J].Advances in Neural Information Processing Systems,2004,7(1):1-8
[12] Mezard M,Parisi G.The cavity method at zero temperature[J].Journal of Statistical Physics,2003,111(1/2):1-34
[13] Mezard M,Zecchina R.Random k-satisifability problem:Froman analytic solution to an efficient algorithm[J].Physical Review E,2002,6(5):56-126
[14] Maneva E,Mossel E,Wainwright M.A new look at surveypropagation and its generalizations[J].Journal of the ACM,2007,4(4):1089-1098
[15] Braunstein A,Mezard M,Zecchina R.Survey propagation:An algorithm for satisfiability[J].Random Structures and Algorithms,2005,7(2):201-226
[16] Montanari A.Message passing algorithms:A success looking for theoreticians[C]∥Proc.of the 42nd ACM Symposium on Theory of Computing (STOC 2010).New York,ACM,2010:37-38
[17] Yedidia J S,Freeman W T,Weiss Y.Understanding belief propa-gation and its generalizations[J].Artificial Intelligence,2003,8(1):239-269
[18] Mezard M,Parisi G,Zecchina R.Analytic and algorithmic solution of random satisfiability problems[J].Science,2002,7(5582):812-815
[19] Cjavas J,Furtlehner C,Mezard M,et al.Survey propagation decimation through distributed local computations[J].Journal of Statistic Mathematics,2005,2005(11):11016
[20] Braunstein A,Zecchina R.Survey and belief propagation on random k-SAT[J].Lecture Notes in Computer Science,2004,9(1):519-528
[21] Xu Ke,Li Wei.Exact phase transitions in random constraint sa-tisfaction problems[J].Journal of Artificial Intelligence Research,2000,12(1):93-103
[22] Xu Ke,Li Wei.Many hard examples in exact phase transitions[J].Theory Computer Science,2006,355(1):291-302
[23] Xu Ke,Boussemart F,Hemery F,et al.Random constraint satisfaction:Easy generation of hard instances[J].Artificial Intelligence,2007,171(1):514-534
[24] 赵春艳,郑志明.一种基于变量熵求解约束满足问题的置信传播算法[J].中国科学F:信息科学,2012,2(9):1170-1180
[25] 殷明浩,周俊萍,孙吉贵,等.求解 QBF 问题的启发式调查传播算法[J].软件学报,2011,2(7):1538-1550
[26] Kschischang F,Frey B,Loeliger H.Factor graph and the sum-product algorithm[J].Information Theory,2001,47(1):498-519
[27] Weiss Y.Correctness of local probability propagation in gra-phical models with loops[J].Neural Computation,2000,2(1):1-41
[28] Weiss Y,Freeman W T.Correctness of belief propagation inGaussian graphical models of arbitrary topology[J].Neural Computation,2001,13(10):2173-2200
[29] Tatikonda S,Jordan M I.Loopy belief propagation and Gibbs measure[C]∥Proceedings of the 18th Annual Conference on Uncertainty in Artificial Intelligence.2002:493-500
[30] Heskes T.On the uniqueness of loopy belief propagation fixed points[J].Neural Computation,2004,16:2379-2413
[31] Ihler A T.Loopy belief propagation:Convergence and effects of message errors[J].Machine Learning Research,2005,6:905-936
[32] Mooij J M,Kappen H J.Sufficient conditions for convergence of the sum-product algorithm[J].IEEE Transactions on Information Theory,2007,3:4422-4437
[33] Shi Xiang-qiong,Schonfeld D,Tuninetti D.Message error analysis of loopy belief propagation for the sum-product algorithm[J].Computer and Information Science,2010,1009:1-30
[34] Gamarnik D,Shah D,Wei Y.Belief propagation for min-costnetwork flow:Convergence and correctness[J].Operations Research,2012,0(2):410-428
[35] Brunsch T,Cornelissen K,Manthey B,et al.Smoothed analysis of BP for minimum cost flow and matching[J].Journal of Graph Algorithms and Applications,2013,7(6):647-670
[36] Norshams N,Wainwright M J.Stochastic belief propagation:A low complexity alternative to the sum product algorithm[J].IEEE Transactions on Information Theory,2013,9(4):1981-2000
[37] Feige U,Mossel E,Vilenchik D.Complete convergence of message passing algorithms for some satisfiability problems[J].Theory of computing,2013,9(19):617-651
[38] 王晓峰,许道云,韦立.随机可满足实例集上警示传播算法的收敛性[J].软件学报,2013,24(1):1-11
[39] 许道云,王晓峰.一个正则NP-完全问题及其不可近似性[J].计算机科学与探索,2013,7(8):691-697

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed