信息传播算法在可满足性(SAT)问题上性能表现优越，其收敛性却依赖于因子图的结构复杂程度，至今缺少系统的理论解释。调查传播算法(SP)是解决SAT问题效果最好的信息传播算法。为有效分析SP算法的收敛性，借助因子图转换技术和鲁汶算法划分因子图社区，基于K维结构熵理论，提出了SAT实例的K维结构熵度量模型，得出了随机SAT实例的K维结构熵。分析了SP算法收敛性与K维结构熵之间的关系，给出了SP算法收敛性的K维结构熵阈值。实验证明该方法有效。
科研之友
微信
新浪微博
Facebook
分享链接
