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
Lichao PANG1, Xiaofeng WANG1,2(), Zhixin XIE1, Yi YANG1, Xingyu ZHAO1, Lan YANG1
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.Supported by:
庞立超1, 王晓峰1,2(), 谢志新1, 杨易1, 赵星宇1, 杨澜1
通讯作者:
王晓峰
作者简介:
庞立超(1993—),男,山东临沂人,硕士研究生,CCF会员,主要研究方向:算法分析与设计;基金资助:
CLC Number:
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.
庞立超, 王晓峰, 谢志新, 杨易, 赵星宇, 杨澜. 随机正则3-可满足性问题的解簇结构分析[J]. 《计算机应用》唯一官方网站, 2024, 44(7): 2137-2143.
Add to citation manager EndNote|Ris|BibTeX
URL: https://www.joca.cn/EN/10.11772/j.issn.1001-9081.2023070940
环境 | 配置 | |
---|---|---|
硬件环境 | 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 |
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 |
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 |
Tab. 2 Average satisfiable numbers for regular 3-SAT instances with different parameters dand 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 |
n | 平均求解时间/s | |||||||
---|---|---|---|---|---|---|---|---|
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 |
Tab. 3 Average solution time for regular 3-SAT instances with different d and n
n | 平均求解时间/s | |||||||
---|---|---|---|---|---|---|---|---|
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 |
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] | Peng LI, Shilin WANG, Guangwu CHEN, Guanghui YAN. Key node mining in complex network based on improved local structural entropy [J]. Journal of Computer Applications, 2023, 43(4): 1109-1114. |
[2] | Xiangyu LUO, Ke YAN, Yan LU, Tian WANG, Gang XIN. Nonuniform time slicing method based on prediction of community variance [J]. Journal of Computer Applications, 2023, 43(11): 3457-3463. |
[3] | LI Ping, WANG Fen, CHEN Qidong, SUN Jun. Discrete random drift particle swarm optimization algorithm for solving multi-objective community detection problem [J]. Journal of Computer Applications, 2021, 41(3): 803-811. |
[4] | SHENG Jun, LI Bin, CHEN Ling. Recommendation algorithm based on modularity and label propagation [J]. Journal of Computer Applications, 2020, 40(9): 2606-2612. |
[5] | YUAN Peiyan, CAI Yunyun. Content offloading scheme of greedy strategy in mobile edge computing system [J]. Journal of Computer Applications, 2019, 39(9): 2664-2668. |
[6] | FU Lidong, HAO Wei, LI Dan, LI Fan. Community dividing algorithm based on similarity of common neighbor nodes [J]. Journal of Computer Applications, 2019, 39(7): 2024-2029. |
[7] | LI Feilong, ZHAO Chunyan, FAN Rumeng. Solving random constraint satisfaction problems based on tabu search algorithm [J]. Journal of Computer Applications, 2019, 39(12): 3584-3589. |
[8] | LI Lei, YAN Guanghui, YANG Shaowen, ZHANG Haitao. Improved Louvain method with strategy of separating isolated nodes [J]. Journal of Computer Applications, 2017, 37(4): 970-974. |
[9] | WANG Tianhong, WU Xing, LAN Wangsen. Improved community detection algorithm based on local modularity [J]. Journal of Computer Applications, 2016, 36(5): 1296-1301. |
[10] | XIA Yidan, WANG Bin, DONG Yingzhao, LIU Hui, XIONG Xin. Application of weighted Fast Newman modularization algorithm in human brain structural network [J]. Journal of Computer Applications, 2016, 36(12): 3347-3352. |
[11] | ZHANG Qiangqiang, HUANG Tinglei, ZHANG Yinming. Detecting community in bipartite network based on cluster analysis [J]. Journal of Computer Applications, 2015, 35(12): 3511-3514. |
[12] | GUO Yujing JI Donghong. Summary extraction of news comments based on weighed textual matrix factorization and information entropy model [J]. Journal of Computer Applications, 2014, 34(10): 2859-2864. |
[13] | SHUI Chao LI Hui. Community structure identification algorithm based on subcenter [J]. Journal of Computer Applications, 2012, 32(08): 2154-2158. |
[14] | WANG Yan-qun LI Hai-fang GUO Hao CHEN Jun-jie. Research into community structure of resting-state brain functional network [J]. Journal of Computer Applications, 2012, 32(07): 2044-2048. |
[15] | . Epistemic Cord logic: verifying anonymous routing protocols in Ad Hoc network [J]. Journal of Computer Applications, 2009, 29(09): 2432-2434. |
Viewed | ||||||
Full text |
|
|||||
Abstract |
|
|||||