现实生活中会存在很多约束,需要在所有约束被满足或尽量满足的情况下制定出一种最优解决方案,这一类问题被称为约束满足问题(Constraint Satisfaction Problem,CSP)。本文的研究重点最大可满足性问题(Maximum Satisfiability Problem,MaxSAT)是一类特殊的约束满足问题,其目标是对给定的子句集,找到关于其变元集合的一组完备赋值使得该子句集被满足的子句个数最多。MaxSAT是典型的NP难问题,具有很重要的理论和工业价值。MaxSAT的算法有两大类:完备算法以及启发式算法。本文研究的重点是MaxSAT的完备算法,完备算法的最大特点是需要考虑每一种可能解,所以在基于分支限界的MaxSAT算法中,为了更早更多的排除非最优解,在下界预估阶段使用单子句传播规则、推理规则、失败文字探测等技术来提高下界,从而提高算法的求解效率。本文结合了基于分支限界的MaxSAT算法maxsatz,提出了新算法Iter_maxsatz。新算法Iter_maxsatz将子句集划分为多个子句分组,通过对各子句分组调用maxsatz迭代求解,会得到各子句分组的局部最优解,这个局部最优解的值会被用到maxsatz搜索过程的剪枝中:可以在线性时间复杂度内根据局部最优解的值计算出搜索树中各个结点上可满足子句个数的上界值,将该值与当前可满足子句个数的下界比较,判断对以该结点为根结点的子树进行搜索的必要性,从而提高算法的求解效率。对MaxSAT竞赛网站上的公开的随机算例进行了测试,实验结果的深入分析表明算法Iter_maxsatz是一个可行且具潜力的算法。