一种基于置信传播的算法求解随机约束满足问题

为了求解具有增长域的随机约束满足问题(CSP),提出一种基于置信传播的算法即NBP* (new-selected belief propagation*, NBP*)。在置信传播算法中,当BP方程不收敛时,算法就会终止。然而算法在经过多次迭代之后,虽然约束发送给变量的信息没有达到收敛条件,但是仍有部分信息是准确的,所以当算法的BP方程不收敛时,提出利用最后一次迭代得到的约束发送给变量的信息来计算变量的边际概率,当赋值不满足约束时,根据边际概率确定的变量顺序挑选下一个变量进行赋值,得到NBP*算法。数值实验表明:这种算法可以在可满足性相变区域找到解,并且有效提高了置信传播算法的求解效率。