摘要
随机约束满足问题是经典的NP完全问题,在理论研究和现实生活中有着广泛应用。研究人员发现随机约束满足问题存在相变现象,近几十年来关于此问题相变的研究成果不断涌现。从随机图着色问题和随机可满足问题2个最经典的随机约束满足问题入手,从算法研究、理论物理和数学证明3个方面综述了随机图着色问题和随机可满足问题的相变研究成果。最后对随机约束满足问题相变的研究趋势进行了展望。
Random constraint satisfaction problem is a classical NP complete problem,which is widely used in theoretical research and real life.The random constraint satisfaction problem has phase transition phenomenon.In recent decades,the research results of phase transitions on this issue have continuously emerged.In this paper,random graph coloring problem and random satisfiability problem are selected,which are classical constraint satisfaction problems.Based on the method from algorithm research,statistical physic,mathematical proof,this paper summarizes and reviews the research results on phase transition of random graph coloring problem and random satisfiability problem.Finally,we provided a suggestion for the direction of future development.
作者
牛鹏飞
王晓峰
芦磊
张九龙
NIU Peng-fei;WANG Xiao-feng;LU Lei;ZHANG Jiu-long(School of Computer Science and Engineering,North Minzu University,Yinchuan 750021;The Key Laboratory of Images and Graphics Intelligent Processing of State Ethnic Affairs Commission,North Minzu University,Yinchuan 750021,China)
出处
《计算机工程与科学》
CSCD
北大核心
2022年第7期1321-1330,共10页
Computer Engineering & Science
基金
国家自然科学基金(62062001,61762019,61862051,61962002)
宁夏自然科学基金(2020AAC03214,2020AAC03219,2019AAC03120,2019AAC03119)
北方民族大学重大专项(ZDZX201901)。
关键词
随机约束满足问题
随机可满足问题
随机图着色问题
相变
random constraint satisfaction problem
random satisfiability problem
random graph coloring problem
phase transition
