值域增长约束满足问题的无回溯与随机行走策略的算法复杂性分析

摘要/Abstract

摘要： 值域增长的约束满足问题模型是计算复杂性理论中一类重要的实际问题模型,针对解决这类问题的算法研究仍然很少。通过研究RB模型这一典型的值域增长约束满足问题,发现当问题规模很大时,无回溯策略比随机行走策略更加有效。这与典型的值域确定的约束满足问题如SAT问题不同,是值域增长的约束满足问题所特有的性质。通过实验研究了两种策略的表现,并进一步对两种策略的表现进行了分析。

关键词: 无回溯,随机行走,算法复杂性,RB模型,约束满足问题

Abstract: Constraint satisfaction problems (CSP) with growing domains are a kind of important practical models in complexity theory,but the algorithm performance research is still rare．By the study on a typical CSP with growing domains,RB model,it is discovered that the backtrack-free strategy works better than the random-walk strategy when the size of problems is huge．Different from CSP with fixed domains such as SAT,this is a special property to CSP with growing domain．Moreover,the performances in experiments and theoretic analysis for these two strategies were also given.

Key words: Backtrack-free,Random-walk,Algorithmic complexity,RB model,CSP

徐伟,巩馥洲. 值域增长约束满足问题的无回溯与随机行走策略的算法复杂性分析[J]. 计算机科学, 2014, 41(4): 205-210. https://doi.org/

XU Wei and GONG Fu-zhou. Computational Complexity Analysis of Backtrack-free and Random-walk Strategies on Constraint Satisfaction Problems with Growing Domains[J]. Computer Science, 2014, 41(4): 205-210. https://doi.org/

参考文献

[1] Rossi F,Van Beek P,Walsh T．Handbook of constraint pro-gramming[M]．New York:Elsevier Science Inc,2006
[2] Nishimori H．statistical physics of spin glasses and information processing:an introduction[M]．Oxford:Clarendon Press,2001
[3] Mezard M,Montanari A．Information,physics and computation[M]．New York:Oxford University Press,2009
[4] Creignou N,Daude H．The SAT-UNSAT transition for random constraint satisfaction problems[J]．Discrete Math,2009,9:2085-2099
[5] Martin O C,Monasson R,Zecchina R．Statistical mechanicsmethods and phase transitions in optimization problems[J]．Theor Comput Sci,2001,265:3-67
[6] 王芙,周育人,叶立．调查传播算法和蚁群算法相结合求解可满足性问题[J]．计算机科学,2012,39(4):227-231
[7] Xu K,Li W．Exact phase transitions in random constraint satisfaction problems[J]．J Artif Intell Res,2000,12:93-103
[8] Lecoutre C．Constraint networks:techniques and algorithms[M]．London:ISTE Ltd,Hoboken:John Wiley & Sons Inc,2009
[9] Xu K,Li W．Many hard examples in exact phase transitions[J]．Theor Comput Sci,2006,355:291-302
[10] Xu K,Boussemart F,Hemery F,et al．Random constraint satisfaction:easy generation of hard (satisfiable) instances[J]．Artif Intell,2007,171:514-534
[11] Saitta L,Giordana A,Cornuejols A．Phase transitions in machine learning[M]．Cambridge:Cambridge University Press,2011
[12] Zhao C Y,Zhang P,Zheng Z M,et al．Analytical and belief-propagation studies of random constraint satisfaction problems with growing domains[J]．Phys Rev E,2012,85:016106
[13] 赵春燕,郑志明．一种基于变量熵求解约束满足问题的置信传播算法[J]．中国科学:信息科学,2012,42(9):1170-1180
[14] Jiang W,Liu T,Ren T,et al．Two hardness results on feedback vertex sets[C]∥FAW-AAIM 2011,LNCS 6681．Springer,2011:233-243
[15] Liu T,Lin X,Wang C,et al．Large hinge width on sparse random hypergraphs[C]∥IJCAI 2011,AAAI．2011:611-616
[16] Wang C,Liu T,Cui P,et al．A note on treewidth in random graphs[C]∥COCOA 2011,LNCS 6831．Springer,2011:491-499
[17] Richter S,Helmert M,Gretton C．A stochastic local search approach to vertex cover[C]∥Proceedings of the 30th German Conference on Artificial Intelligence (KI)．2007
[18] Guturu P,Dantu R．An impatient evolutionary algorithm withprobabilistic tabu search for unified solution of some NP hard problems in graph and set theory via clique finding[J]．IEEE Transactions on Systems,Man and Cybernetics,2008,28:645-666
[19] Pullan W．Approximating the maximum vertex/edge weighted clique using local search[J]．Journal of Heuristics,2008,14:117-134
[20] Alphonse E,Osmani A．A model to study phase transition and plateaus in relational learning [C]∥18th International Confe-rence on Inductive Logic Programming．2008:6-23
[21] Heras F,Baneres D．The impact of Max-SAT resolution-based preprocessors on local search solvers．Journal on Satisability[J]．Boolean Modeling and Computation (JSAT),2010,7(2/3):89-126
[22] Zhao C,Zheng Z．Threshold behaviors of a random constraint satisfaction problem with exact phase transitions[J]．Information Processing Letters,2011,111(20):985-988
[23] Cai S,Su K,Sattar A．Local search with edge weighting and configuration checking heuristics for minimum vertex cover[J]．Artificial Intelligence,2011,175(9/10):1672-1696
[24] Cai S,Su K,Luo C,et al．NuMVC:an efficient local search algorithm for minimum vertex cover[J]．Journal of Artificial Intelligence Research,2013,46:687-716
[25] Biere A,Heule M,Maaren H,et al．Handbook of satisfiability[M]．Amsterdam:IOS press,2009
[26] Papadimitriou C H．On selecting a satisfying truth assignment[C]∥Proceedings of the 32nd Annual IEEE Symposium on Foundations of Computer Science．1991:163-169
[27] Selman B,Kautz H．Local search strategies for satisfiability testing[C]∥AMS-DIMACS Series on Discr Math Theor Comp Sci．1996,26:521-531
[28] Iwama K,Tamaki S．Improved bounds for 3-SAT[C]∥Procee-dings of the Fifteenth AnnualACM-SIAM Symposium on Discrete Algorithms．2004:321-322
[29] Alekhnovich M,Ben-Sasson E．Linear upper bounds for random walk on small density random 3-cnfs[J]．SIAM J Comput,2006,36(5):1248-1263
[30] Coja-Oghlan A,Feige U,Frieze A,et al．On smoothed k-CNFformulas and the walksat algorithm[C]∥Proc 20th SODA．2009:451-460
[31] Coja-Oghlan A,Frieze A．Analyzing walksat on random formulas[C]∥Proc 9th ANALCO．2012:48-55
[32] Kamath A,Motwani R,Palem K,et al．Tail bounds for occupancy and the satisfiability threshold conjecture[J]．Random Struct Alg,1995,7:59-80

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed