计算机应用

作者：庞立超, 王晓峰, 谢志新, 杨易, 赵星宇, 杨澜

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

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

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

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

来源：2024年第7期

《计算机应用》期刊编辑部

查看计算机应用杂志2024年第7期