计算机应用

作者：梁永濠, 李金龙

单位：中国科学技术大学 计算机科学与技术学院，合肥 230026

关键词：布尔可满足性问题,消息传递神经网络,图神经网络,机器学习,人工智能

为优化端到端神经布尔可满足性问题（SAT）求解器的消息传递神经网络（MPNN）结构、减少求解过程中的迭代次数并提升求解器性能，提出一种更多更深的消息传递网络（MDMPN）。该网络通过引入整体消息传递模块，在每次消息传递迭代中实现从文字节点到子句节点的额外的整体消息传递，从而传递更多的消息。同时，引入消息跳跃模块，实现从文字节点到它的二阶邻居的消息传递，从而传递更深的消息。为了评估MDMPN的性能与泛化能力，将它应用于目前先进的神经SAT求解器QuerySAT和基础神经SAT求解器NeuroSAT。实验结果表明，在困难随机的3-SAT数据集上，应用MDMPN的QuerySAT的求解性能优于标准的QuerySAT，在求解包含600个变量迭代次数上限为212的困难3-SAT问题上的准确率提高了46.12个百分点；应用MDMPN的NeuroSAT的求解性能也优于标准的NeuroSAT，在求解包含600个变量迭代次数上限为212的困难3-SAT问题上的准确率提高了35.69个百分点。

来源：2025年第9期

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

查看计算机应用杂志2025年第9期