一种基于变量熵求解约束满足问题的置信传播算法

摘要：

在置信传播(belief propagation,BP)算法中,提出一种基于变量熵来挑选变量从而固定变量赋值的策略,用于求解一类具有增长定义域的随机约束满足问题.RB模型是一个具有增长定义域的随机约束满足问题的典型代表,已经严格证明它不仅存在精确的可满足性相变现象,而且可以生成难解实例.在RB模型上选取两组不同的参数进行数值实验.结果表明:在接近可满足性相变点时,BP引导的消去算法仍然可以非常有效地找到随机实例的解;不断增加问题的规模,算法的运行时间呈指数级增长;并且当控制参数(约束紧度)增加时,变量的平均自由度逐渐降低.

关键词：约束满足问题、RB模型、相变、置信传播、算法、熵

所属期刊栏目：42

分类号：TP18;O236(自动化基础理论)

资助基金：国家自然科学基金;国家国际科技合作专项基金

在线出版日期：2012-12-20（万方平台首次上网日期，不代表论文的发表时间）

页码：1170-1180