Journal of Computer Applications ›› 2024, Vol. 44 ›› Issue (7): 2137-2143.DOI: 10.11772/j.issn.1001-9081.2023070940

• Advanced computing • Previous Articles     Next Articles

Solution cluster structure analysis of random regular 3-satisfiability problems

Lichao PANG1, Xiaofeng WANG1,2(), Zhixin XIE1, Yi YANG1, Xingyu ZHAO1, Lan YANG1   

  1. 1.School of Computer Science and Engineering,North Minzu University,Yinchuan Ningxia 750021,China
    2.Key Laboratory of Image and Graphics Intelligent Processing of State Ethnic Affairs Commission (North Minzu University),Yinchuan Ningxia 750021,China
  • Received:2023-07-14 Revised:2023-09-15 Accepted:2023-09-20 Online:2023-10-26 Published:2024-07-10
  • Contact: Xiaofeng WANG
  • About author:PANG Lichao, born in 1993, M. S. candidate. His research interests include algorithm analysis and design.
    XIE Zhixin, born in 1997, M. S. candidate. His research interests include algorithm analysis and design.
    YANG Yi, born in 1995, M. S. candidate. His research interests include algorithm analysis and design.
    ZHAO Xingyu, born in 1999, M. S. candidate. His research interests include algorithm analysis and design.
    YANG Lan, born in 1997, M. S. candidate. Her research interests include algorithm analysis and design.
    First author contact:WANG Xiaofeng, born in 1980, Ph. D., associate professor. His research interests include algorithm analysis and design, artificial intelligence.
  • Supported by:
    National Natural Science Foundation of China(62062001);Ningxia Youth Top Talent Project(2021)

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

庞立超1, 王晓峰1,2(), 谢志新1, 杨易1, 赵星宇1, 杨澜1   

  1. 1.北方民族大学 计算机科学与工程学院, 银川 750021
    2.图像图形智能处理国家民委重点实验室(北方民族大学), 银川 750021
  • 通讯作者: 王晓峰
  • 作者简介:庞立超(1993—),男,山东临沂人,硕士研究生,CCF会员,主要研究方向:算法分析与设计;
    谢志新(1997—),男,陕西渭南人,硕士研究生,CCF会员,主要研究方向:算法分析与设计;
    杨易(1995—),男,陕西咸阳人,硕士研究生,CCF会员,主要研究方向:算法分析与设计;
    赵星宇(1999—),男,湖北荆州人,硕士研究生,CCF会员,主要研究方向:算法分析与设计;
    杨澜(1997—),女,山西忻州人,硕士研究生,CCF会员,主要研究方向:算法分析与设计。
    第一联系人:王晓峰(1980—),男,甘肃会宁人,副教授,博士,CCF高级会员,主要研究方向:算法分析与设计、人工智能;
  • 基金资助:
    国家自然科学基金资助项目(62062001);宁夏青年拔尖人才项目(2021)

Abstract:

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.

Key words: structural entropy, regular 3-satisfiability problem, solution cluster, modularity, phase transition

摘要:

正则3-可满足性(3-SAT)问题是一个NP难问题,研究正则3-SAT问题解簇结构变化,旨在深入理解该问题的判定难度和可满足性解的分布情况。然而,现有分析模型只研究了接近簇集相变点的几个离散值,在不同约束密度下,缺乏统一的分析模型来描述解簇的结构演变。为了解决这一问题,提出解簇结构相变分析模型(PMSS)。该模型主要思想是采用WalkSAT算法和信息传播算法求得正则3-SAT问题可满足的初始解,再利用随机游走构造该初始解的解簇,并对解簇进行分析。用模块度和社区度量解簇社区结构,用结构熵度量解簇结构复杂性。实验结果表明,PMSS能够准确分析解簇结构演变过程,并且正则3-SAT问题实例的可满足相变点位于13~14,与使用Zchaff求解器得到的相变点一致,进一步验证了PMSS的有效性。

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

CLC Number: