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

A belief-propagation algorithm based on variable entropy for constraint satisfaction problems

作　　者：赵春艳[1] 郑志明[1] 

机构地区：[1]北京航空航天大学数学与系统科学学院,数学,信息与行为教育部重点实验室,北京100191

出　　处：《中国科学：信息科学》2012年第9期1170-1180,共11页Scientia Sinica(Informationis)

基　　金：国家自然科学基金(批准号:60973033);国家国际科技合作专项(批准号:2010DFR00700)资助项目

摘　　要：在置信传播(belief propagation,BP)算法中,提出一种基于变量熵来挑选变量从而固定变量赋值的策略,用于求解一类具有增长定义域的随机约束满足问题.RB模型是一个具有增长定义域的随机约束满足问题的典型代表,已经严格证明它不仅存在精确的可满足性相变现象,而且可以生成难解实例.在RB模型上选取两组不同的参数进行数值实验.结果表明:在接近可满足性相变点时,BP引导的消去算法仍然可以非常有效地找到随机实例的解;不断增加问题的规模,算法的运行时间呈指数级增长;并且当控制参数(约束紧度)增加时,变量的平均自由度逐渐降低.Belief propagation （BP） is a powerful technique that has been applied to solve constraint satisfaction problems （CSPs）. In this paper, for solving random CSPs with growing domains, we propose a new strategy based on the variable entropy to fix variables in the procedure of BP decimation. It has been proved that model RB, a representative random CSP with growing domains, exhibits an exact satisfiability phase transition phenomenon, and all instances of model RB are hard at the threshold. We perform the algorithm on the instances of model RB with two different groups of parameters. Numerical results show that the algorithm guided by BP can find solutions efficiently for instances in the regime that is close to the threshold. The running time of the algorithm grows exponentially with the problem size. Besides, the average freedom of the variables decreases as the control parameter （constraint tightness） increases.

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

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]