计算机科学 ›› 2015, Vol. 42 ›› Issue (1): 279-284.doi: 10.11896/j.issn.1002-137X.2015.01.062
王晓峰,李强,丁红胜
WANG Xiao-feng, LI Qiang and DING Hong-sheng
摘要: 信息传播算法求解随机3-SAT问题时非常有效,能使难解区域变窄。然而,对于因子图带有环的实例,信息传播算法并不总有效,常表现为不收敛。对于这种现象,至今缺少系统的理论解释。警示传播(Warning Propagation,WP)算法是一种基础的信息传播算法,对WP算法的收敛性研究是其它信息传播算法收敛性研究的重要基础。将一个3-SAT问题转换为具有规则结构的(3,4)-SAT问题,(3,4)-SAT问题是NP-完全的。基于(3,4)-SAT问题的规则结构性质,分析 WP算法的收敛性。选取了3组不同规模的实例进行实验模拟,结果表明:在这种规则结构的可满足性实例集上,WP算法的收敛性有较大提高。
[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 |
No related articles found! |
|