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

doi:10.11772/j.issn.1001-9081.2023070940

《计算机应用》唯一官方网站 ›› 2024, Vol. 44 ›› Issue (7): 2137-2143.DOI: 10.11772/j.issn.1001-9081.2023070940

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

庞立超¹, 王晓峰¹^,²(), 谢志新¹, 杨易¹, 赵星宇¹, 杨澜¹

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

收稿日期:2023-07-14 修回日期:2023-09-15 接受日期:2023-09-20 发布日期:2023-10-26 出版日期:2024-07-10
通讯作者: 王晓峰
作者简介:庞立超（1993—），男，山东临沂人，硕士研究生，CCF会员，主要研究方向：算法分析与设计；
谢志新（1997—），男，陕西渭南人，硕士研究生，CCF会员，主要研究方向：算法分析与设计；
杨易（1995—），男，陕西咸阳人，硕士研究生，CCF会员，主要研究方向：算法分析与设计；
赵星宇（1999—），男，湖北荆州人，硕士研究生，CCF会员，主要研究方向：算法分析与设计；
杨澜（1997—），女，山西忻州人，硕士研究生，CCF会员，主要研究方向：算法分析与设计。
第一联系人：王晓峰（1980—），男，甘肃会宁人，副教授，博士，CCF高级会员，主要研究方向：算法分析与设计、人工智能；
基金资助:
国家自然科学基金资助项目(62062001);宁夏青年拔尖人才项目(2021)

Solution cluster structure analysis of random regular 3-satisfiability problems

Lichao PANG¹, Xiaofeng WANG¹^,²(), Zhixin XIE¹, Yi YANG¹, Xingyu ZHAO¹, Lan YANG¹

^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)

摘要/Abstract

摘要：

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

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

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

中图分类号:

TP301

庞立超, 王晓峰, 谢志新, 杨易, 赵星宇, 杨澜. 随机正则3-可满足性问题的解簇结构分析[J]. 计算机应用, 2024, 44(7): 2137-2143.

Lichao PANG, Xiaofeng WANG, Zhixin XIE, Yi YANG, Xingyu ZHAO, Lan YANG. Solution cluster structure analysis of random regular 3-satisfiability problems[J]. Journal of Computer Applications, 2024, 44(7): 2137-2143.

图/表 11

图1 PMSS结构

Fig. 1 PMSS structure

图2 正则3-SAT问题的一个解簇

Fig. 2 A solution cluster of regular 3-SAT problem

表1 实验环境

Tab. 1 Experimental environment

环境		配置
硬件环境	CPU	Intel Core i5-10200H CPU@2.40 GHz
	内存	16 GB
	硬盘	1 TB
软件环境	操作系统	Windows 10
	开发平台	Anaconda， Eclipse
	编程语言	Java20，Python 3.8.8，Matlab 9.0.0.341360

表2 正则3-SAT实例在不同参数d和n下的平均可满足数

Tab. 2 Average satisfiable numbers for regular 3-SAT instances with different parameters dand n

n	平均可满足数
n	d=8	d=9	d=10	d=11	d=12	d=13	d=14	d=15	d=16	d=17	d=18	d=19	d=20
30	100	100	100	100	91	67	38	22	6	1	0	0	0
60	100	100	100	100	95	63	22	5	1	0	0	0	0
90	100	100	100	100	97	64	17	3	0	0	0	0	0
120	100	100	100	100	98	60	15	4	0	0	0	0	0
150	100	100	100	100	99	67	6	0	0	0	0	0	0
180	100	100	100	100	100	70	5	0	0	0	0	0	0
210	100	100	100	100	100	75	3	0	0	0	0	0	0

表3 正则3-SAT实例在不同参数d和n下的平均求解时间

Tab. 3 Average solution time for regular 3-SAT instances with different d and n

n	平均求解时间/s
n	d=10	d=11	d=12	d=13	d=14	d=15	d=16	d=17
30	0.025 3	0.025 4	0.0269	0.026 1	0.024 1	0.024 5	0.025 8	0.025 5
60	0.026 4	0.034 6	0.029 7	0.039 4	0.0433	0.040 2	0.039 7	0.036 4
90	0.029 0	0.030 5	0.079 3	0.144 5	0.1658	0.127 3	0.088 5	0.075 6
120	0.030 9	0.032 7	0.204 1	1.1766	1.030 7	0.584 2	0.335 5	0.217 8
150	0.033 0	0.035 2	0.178 5	7.342 6	8.0671	3.253 6	1.406 6	0.818 0
180	0.034 8	0.037 3	0.192 1	45.6679	39.270 1	16.146 6	6.576 2	3.102 1
210	0.036 6	0.040 2	10.700 3	467.6260	260.467 5	64.473 7	25.893 0	11.853 5

图3 不同规模下正则3-SAT实例的平均求解时间

Fig. 3 Average solution time for regular 3-SAT instances at different scales

图4 连通分量分布

Fig. 4 Distribution of connected components

图5 解空间和解簇的对比分析

Fig. 5 Comparative analysis of solution space and cluster

图6 正则3-SAT问题的解簇结构熵分布

Fig. 6 Structural entropy distribution of solution cluster for regular 3-SAT problem

图7 随机3-SAT问题的解簇结构熵分布

Fig. 7 Structural entropy distribution of solution cluster for random 3-SAT problem

图8 解簇结构变化

Fig. 8 Change of solution cluster structure

参考文献 24

1	ZHAO C-Y， FU Y-R， ZHAO J-H. A residual-based message passing algorithm for constraint satisfaction problems ［J］. Communications in Theoretical Physics， 2022， 74（3）： 81-90.
2	VIZEL Y， WEISSENBACHER G， MALIK S. Boolean satisfiability solvers and their applications in model checking ［J］. Proceedings of the IEEE， 2015， 103（11）： 2021-2035.
3	NOGUCHI T， FUJIWARA A. An asynchronous P system with a DPLL algorithm for solving SAT ［J］. International Journal of Networking and Computing， 2022， 12（2）： 238-252.
4	FU H， CHEN S， XU Y， et al. Improving WalkSAT for random 3-SAT problems ［J］. Journal of Universal Computer Science， 2020， 26（2）： 220-243.
5	VARMANTCHAONALA C M， FENDJI J L K E， NJAFA J P T， et al. Quantum hybrid algorithm for solving SAT problem ［J］. Engineering Applications of Artificial Intelligence， 2023， 121： 106058.
6	MONTANARI A， RICCI-TERSENGHI F， SEMERJIAN G. Clusters of solutions and replica symmetry breaking in random K-satisfiability ［J］. Journal of Statistical Mechanics： Theory and Experiment， 2008， 2008（4）： P04004.
7	王晓峰，庞立超，莫淳惠，等.可满足性问题的结构特征进展综述［J］.郑州大学学报（工学版）， 2023， 44（6）： 40-47.
	WANG X F， PANG L C， MO C H， et al. A review of structural characteristics of satisfiability problems ［J］. Journal of Zhengzhou University （Engineering Science）， 2023， 44（6）： 40-47.
8	周海军.自旋玻璃与消息传递［M］.北京：科学出版社， 2015： 177-217.
	ZHOU H J. Spin Glass and Message Passing ［M］. Beijing： Science Press， 2015： 177-217.
9	谷文祥，黄平，朱磊，等.人工智能问题中的相变现象研究［J］.计算机科学， 2011， 38（5）： 1-7.
	GU W X， HUANG P， ZHU L， et al. Research of phase transition in artificial intelligence ［J］. Computer Science， 2011， 38（5）： 1-7.
10	MÉZARD M， PALASSINI M， RIVOIRE O. Landscape of solutions in constraint satisfaction problems ［J］. Physical Review Letters， 2005， 95（20）： 200202.
11	MÉZARD M， RICCI-TERSENGHI F， ZECCHINA R. Two solutions to diluted p-spin models and XORSAT problems ［J］. Journal of Statistical Physics， 2003， 111： 505-533.
12	MANEVA E， SINCLAIR A. On the satisfiability threshold and clustering of solutions of random 3-SAT formulas ［J］. Theoretical Computer Science， 2008， 407（1/2/3）： 359-369.
13	ACHLIOPTAS D， COJA-OGHLAN A， RICCI-TERSENGHI F. On the solution space geometry of random constraint satisfaction problems ［J］. Random Structures & Algorithms， 2011， 38（3）： 251-268.
14	KRZAKALA F， MONTANARI A， RICCI-TERSENGHI F， et al. Gibbs states and the set of solutions of random constraint satisfaction problems ［J］. Proceedings of the National Academy of Sciences， 2007， 104（25）： 10318-10323.
15	LI K， MA H， ZHOU H. From one solution of a 3-satisfiability formula to a solution cluster： frozen variables and entropy ［J］. Physical Review E， 2009， 79（3）： 031102.
16	ZHOU H， MA H. Communities of solutions in single solution clusters of a random K-satisfiability formula ［J］. Physical Review E， 2009， 80（6）： 066108.
17	莫孝玲，许道云. CNF公式赋值空间上可满足解的概率性质［J］.计算机科学与探索， 2018， 12（11）： 1852-1861.
	MO X L， XU D Y. Probabilistic properties of satisfiable solutions on space of assignments for CNF formula ［J］. Journal of Frontiers of Computer Science and Technology， 2018， 12（11）： 1852-1861.
18	LI A， PAN Y. Structural information and dynamical complexity of networks ［J］. IEEE Transactions on Information Theory， 2016， 62（6）： 3290-3339.
19	LI A， YIN X， XU B， et al. Decoding topologically associating domains with ultra-low resolution Hi-C data by graph structural entropy ［J］. Nature Communications， 2018， 9： 3265.
20	NEWMAN M E J. Fast algorithm for detecting community structure in networks ［J］. Physical Review E， 2004， 69（6）： 066133.
21	BLONDEL V D， J-L GUILLAUME， LAMBIOTTE R， et al. Fast unfolding of communities in large networks ［J］. Journal of Statistical Mechanics： Theory and Experiment， 2008， 2008（10）： P10008.
22	BRAUNSTEIN A， MÉZARD M， ZECCHINA R. Survey propagation： an algorithm for satisfiability ［J］. Random Structures & Algorithms， 2005， 27（2）： 201-226.
23	GARZA S E， SCHAEFFER S E. Community detection with the label propagation algorithm： a survey ［J］. Physica A： Statistical Mechanics and its Applications， 2019， 534： 122058.
24	KRISHNAMURTHY S， SAHOO S. Balanced K-satisfiability and biased random K-satisfiability on trees ［J］. Physical Review E， 2013， 87（4）： 042130.

[1]	彭庆媛, 王晓峰, 王军霞, 华盈盈, 唐傲, 何飞. 可满足性问题相变研究综述[J]. 《计算机应用》唯一官方网站, 2024, 44(11): 3503-3512.
[2]	李鹏, 王世林, 陈光武, 闫光辉. 基于改进的局部结构熵复杂网络重要节点挖掘[J]. 《计算机应用》唯一官方网站, 2023, 43(4): 1109-1114.
[3]	罗香玉, 闫克, 卢琰, 王甜, 辛刚. 基于社区改变量估计的非均匀时间片划分方法[J]. 《计算机应用》唯一官方网站, 2023, 43(11): 3457-3463.
[4]	李萍, 汪芬, 陈祺东, 孙俊. 求解多目标社区发现问题的离散化随机漂移粒子群优化算法[J]. 计算机应用, 2021, 41(3): 803-811.
[5]	盛俊, 李斌, 陈崚. 基于模块度和标签传递的推荐算法[J]. 计算机应用, 2020, 40(9): 2606-2612.
[6]	付立东, 郝伟, 李丹, 李凡. 基于共邻节点相似度的社区划分算法[J]. 计算机应用, 2019, 39(7): 2024-2029.
[7]	李飞龙, 赵春艳, 范如梦. 基于禁忌搜索算法求解随机约束满足问题[J]. 计算机应用, 2019, 39(12): 3584-3589.
[8]	张震, 付印金, 胡谷雨. 基于布隆过滤器的新型混合内存架构磨损均衡策略[J]. 计算机应用, 2018, 38(8): 2230-2235.
[9]	李雷, 闫光辉, 杨绍文, 张海韬. 基于孤立节点分离策略的改进鲁汶算法[J]. 计算机应用, 2017, 37(4): 970-974.
[10]	王天宏, 武星, 兰旺森. 改进的基于局部模块度的社团划分算法[J]. 计算机应用, 2016, 36(5): 1296-1301.
[11]	夏一丹, 王彬, 董迎朝, 刘辉, 熊新. 加权Fast Newman模块化算法在人脑结构网络中的应用[J]. 计算机应用, 2016, 36(12): 3347-3352.
[12]	张嫱嫱, 黄廷磊, 张银明. 基于聚类分析的二分网络社区挖掘[J]. 计算机应用, 2015, 35(12): 3511-3514.
[13]	水超李慧. 基于“次中心”的社区结构探寻算法[J]. 计算机应用, 2012, 32(08): 2154-2158.
[14]	王艳群李海芳郭浩陈俊杰. 静息态脑功能网络的社团结构研究[J]. 计算机应用, 2012, 32(07): 2044-2048.

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

Solution cluster structure analysis of random regular 3-satisfiability problems

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 11

参考文献 24

相关文章 14

编辑推荐

Metrics