最大约束满足问题是在给定的多个约束当中,寻找一个问题的解决方法,使得被满足的约束数量最多。最大约束满足问题作为人工智能领域最基本的NPC问题之一,在人工智能领域有着重要的研究价值和研究地位。在以前的研究工作当中,国内外的学者主要使用完备求解算法和不完备求解算法对最大约束满足问题进行求解,在不同的应用领域,都取得了很好的求解效果。置信传播算法是一种经典的消息传播算法,置信传播算法在神经网络算法中,占有重要的地位。置信传播算法是在因子图中进行迭代得到一种求解结果的不完备算法,该算法在求解多种NPC问题中,得到了很好的求解效果。本文首先在深入研究置信消息传播算法的基础上,根据最大约束满足问题的问题特点,建立了因子图。然后将最小熵的物理方法应用于置信消息传播算法,用于求解最大约束满足问题的RB模型,并在置信传播方程中加入惩罚值,从而使得该算法更加适合于求解最大约束满足问题。最后,利用该算法对最大约束满足问题RB模型进行实际求解,本文还分析了最大约束满足问题RB模型的相变现象。本文通过对置信传播算法进行改进,并将其应用于最大约束满足问题,在求解效果上面,得到了很好的改进,并且使用实验分析的方法,证明了求解效果的改进。利用该算法对最大约束满足问题RB模型优良的求解效果,本文还分析了最大约束满足问题RB模型的相变现象,使用实验分析的方法证明了以前使用理论研究得到的相变点的存在性,为以后进一步研究效果更好的最大约束满足问题RB模型求解算法提供了可借鉴的参考。