论文研究 置信传播和模拟退火相结合求解约束满足问题.pdf

约束满足问题是人工智能领域的一个重要问题。针对一个具有精确相变现象和能产生大量难解实例的随机约束满足问题，提出了置信传播和模拟退火相结合的求解算法。这种算法先通过置信传播方程收敛后得到变量取值的边际概率分布，分别采用最大概率和最小分量熵的策略产生一组启发式的初始赋值，再用模拟退火对这组赋值进行修正。实验结果表明，该算法大大提高了初始赋值向最优解收敛的速度，表现出了显著优越于模拟退火算法的求解性能。