分布式约束优化问题(DCOP)是多智能体系统(MAS)中建模多智能体协调的基本框架,现已应用于传感器网络、任务分配、电力系统和智能家居等领域,具有重要的学术研究意义和实用价值。基于信念传播的非完备推理算法能直接用于求解多元DCOP问题,目前已成功应用在多种实际工程中,是进行DCOP求解的一种重要方法。其中,Max-Sum是其典型代表。然而,可扩展性是非完备信念传播算法所面临的一个巨大挑战。针对该问题,有学者已提出一些解决方法,但这些方法缺乏一般化或者在预处理阶段所需计算量很大。此外,非完备信念传播算法还存在效用重复问题以致求解质量不佳。针对上述问题,本文致力于研究如何以较低成本来加速非完备信念传播,以及在加速的同时,缓解效用重复问题以提高解质量。研究的具体工作如下:(1)深入分析最大化操作对可扩展性的影响及现有加速方法存在局限性,提出一个函数分解和状态剪枝加速方法(FDSP)。该方法基于分支定界的思想利用已探索到的下界对搜索空间进行动态剪枝,并具有通用、快速、易于部署的特性。其中,基于动态规划和目标变量取值已知这一先验知识提出函数分解技术来计算每个部分解的函数上界,并采用基于深度优先的状态剪枝技术对搜索空间进行剪枝。同时,本文从理论上证明FDSP提供单调非增的上界且不影响非完备信念传播算法的性质。最后,实验验证FDSP具有通用性和强大的加速性能,甚至在不利条件下仍然可以进行有效剪枝。(2)深入研究放弃本地函数最优性对非完备信念传播算法解质量的影响,提出一系列基于局部搜索策略的加速优化方法,包括基于随机搜索(SA-MS),基于最大增益(MGM-MS)和基于坐标上升的方法(CA-MS)。这类方法首次在加速信念传播的同时兼顾求解质量的提高,并创新性地将局部搜索和推理相结合,利用局部搜索策略对解空间进行非完备遍历。其先为变量随机赋予初始值,然后根据搜索策略求取变量最佳取值并进行赋值替换,最后得到一个具有最大效用的解。本文还在理论上对其Anytime性质进行证明。最后,实验验证SA-MS、MGM-MS和CA-MS在加速信念传播的同时能够大幅度提高算法的求解质量。