随机正则3-可满足性问题的解簇结构分析  

Solution cluster structure analysis of random regular 3-satisfiability problems

作　　者：庞立超 王晓峰[1,2] 谢志新 杨易 赵星宇 杨澜 PANG Lichao;WANG Xiaofeng;XIE Zhixin;YANG Yi;ZHAO Xingyu;YANG Lan(School of Computer Science and Engineering,North Minzu University,Yinchuan Ningxia 750021,China;Key Laboratory of Image and Graphics Intelligent Processing of State Ethnic Affairs Commission(North Minzu University),Yinchuan Ningxia 750021,China)

机构地区：[1]北方民族大学计算机科学与工程学院,银川750021 [2]图像图形智能处理国家民委重点实验室(北方民族大学),银川750021

出　　处：《计算机应用》2024年第7期2137-2143,共7页journal of Computer Applications

基　　金：国家自然科学基金资助项目(62062001);宁夏青年拔尖人才项目(2021)。

摘　　要：正则3-可满足性(3-SAT)问题是一个NP难问题,研究正则3-SAT问题解簇结构变化,旨在深入理解该问题的判定难度和可满足性解的分布情况。然而,现有分析模型只研究了接近簇集相变点的几个离散值,在不同约束密度下,缺乏统一的分析模型来描述解簇的结构演变。为了解决这一问题,提出解簇结构相变分析模型(PMSS)。该模型主要思想是采用WalkSAT算法和信息传播算法求得正则3-SAT问题可满足的初始解,再利用随机游走构造该初始解的解簇,并对解簇进行分析。用模块度和社区度量解簇社区结构,用结构熵度量解簇结构复杂性。实验结果表明,PMSS能够准确分析解簇结构演变过程,并且正则3-SAT问题实例的可满足相变点位于13~14,与使用Zchaff求解器得到的相变点一致,进一步验证了PMSS的有效性。Regular 3-SATisfiability(3-SAT)problem is an NP-hard problem.Studying alterations in the cluster structure of solutions to regular 3-SAT problem is to enhance the comprehension of the difficulty involved in problem determination and distribution of satisfiable solutions.However,existing analysis models only study a few discrete values near the cluster phase transition point.Under different constraint densities,there is lack of unified analysis model to describe the structural evolution of solution clusters.To solve this problem,a Phase transition Model of Solution cluster Structure(PMSS)was proposed.The main idea of this model is to obtain an initial solution of regular 3-SAT problem using WalkSAT algorithm and information propagation algorithm,construct a solution cluster of initial solutions by using random walks,and analyze the solution cluster.Modularity and community were used to measure community structure,and structural entropy was used to measure the complexity of the solution cluster structure.Experimental results show that PMSS can accurately analyze the structural evolution process of solution clusters,and the phase transition point of regular 3-SAT problem instances is between 13 and 14,which is consistent with the phase transition point obtained using Zchaff solver,further verifying the effectiveness of PMSS.

关 键 词：结构熵 正则3-可满足性问题 解簇 模块度 相变 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]