| 随机约束满足问题相变研究综述 |
| |
| 引用本文： | 牛鹏飞,王晓峰,芦磊,张九龙.随机约束满足问题相变研究综述[J].计算机工程与科学,2022,44(7):1321-1330. |
| |
| 作者姓名： | 牛鹏飞 王晓峰 芦磊 张九龙 |
| |
| 作者单位： | (1.北方民族大学计算机科学与工程学院，宁夏 银川 750021；
2.北方民族大学图像图形智能处理国家民委重点实验室，宁夏 银川 750021) |
| |
| 基金项目： | 国家自然科学基金(62062001,61762019,61862051,61962002)；宁夏自然科学基金(2020AAC03214,2020AAC03219,2019AAC03120,2019AAC03119);北方民族大学重大专项(ZDZX201901) |
| |
| 摘 要： | 随机约束满足问题是经典的NP完全问题，在理论研究和现实生活中有着广泛应用。研究人员发现随机约束满足问题存在相变现象，近几十年来关于此问题相变的研究成果不断涌现。从随机图着色问题和随机可满足问题2个最经典的随机约束满足问题入手，从算法研究、理论物理和数学证明3个方面综述了随机图着色问题和随机可满足问题的相变研究成果。最后对随机约束满足问题相变的研究趋势进行了展望。
|
| 关 键 词： | 随机约束满足问题 随机可满足问题 随机图着色问题 相变 |
| 收稿时间： | 2021-10-18 |
| 修稿时间： | 2021-12-26 |
Review of phase transition ofrandom constraint satisfaction problems |
| |
| NIU Peng-fei,WANG Xiao-feng,LU Lei,ZHANG Jiu-long.Review of phase transition ofrandom constraint satisfaction problems[J].Computer Engineering & Science,2022,44(7):1321-1330. |
| |
| Authors: | NIU Peng-fei WANG Xiao-feng LU Lei ZHANG Jiu-long |
| |
| Affiliation: | (1.School of Computer Science and Engineering,North Minzu University,Yinchuan 750021;
2.The Key Laboratory of Images and Graphics Intelligent Processing of
State Ethnic Affairs Commission,North Minzu University,Yinchuan 750021,China) |
| |
| Abstract: | 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. |
| |
| Keywords: | random constraint satisfaction problem random satisfiability problem random graph coloring problem phase transition |
|
| 点击此处可从《计算机工程与科学》浏览原始摘要信息 |
|
点击此处可从《计算机工程与科学》下载全文 |
|
