文献类型：期刊文章

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

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

出　　处：《中国科学：信息科学》

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

年　　份：2012

卷　　号：42

期　　号：9

起止页码：1170-1180

语　　种：中文

收录情况：CSCD、CSCD2011_2012、JST、RCCSE、ZGKJHX、普通刊

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

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

分 类 号：TP18]