分布式约束优化问题（DCOP）是多智能体协调优化问题的基本模型，在该模型中，各个智能体合作以优化一个共同的目标。DCOP可以对信息与控制分布于多个智能体间的协作问题进行有效建模，被广泛应用于分布式调度、智能电网和认知无线电等领域。推理算法作为求解DCOP的重要手段，具有较高的学术研究意义和实际应用价值。然而，现有推理算法均在不同程度上存在内存占用过多和运行时间较长等问题。故本文致力于提升此类算法的可扩展性，以推进其在实际场景中的应用。具体地，本文针对完备算法——内存有界的分布式伪树优化过程算法（MB-DPOP）的和非完备算法——最大和（Max-sum）算法进行了如下研究：
　　①系统性地研究了MB-DPOP的可扩展性，提出了RMB-DPOP算法。具体地，本文深入分析了限制MB-DPOP可扩展性的主要原因，指出其产生大量冗余推理的原因在于智能体选择的CC节点（Cycle-cut node）过多，且由簇头节点盲目枚举所有赋值组合的行为导致了大量的非并发实例。为此，本文提出了分布式枚举机制、迭代选择机制和缓存机制。其中，分布式枚举机制解决了非并发实例枚举问题，迭代选择机制解决了CC节点选择标准单一问题，缓存机制解决了无法对历史推理结果进行重复利用的问题。此外，本文从理论上证明了RMB-DPOP所需迭代推理次数不多于MB-DPOP，且实验结果表明RMB-DPOP可以显著提高MB-DPOP的可扩展性。
　　②深入分析了基于分支定界的加速Max-sum算法的函数分解和状态剪枝方法（FDSP），提出了一系列基于多解的信念传播加速方法以解决基于分支定界算法下界质量不高、枚举较为盲目等问题。具体地，本文指出在效用函数矩阵高度结构化的情况下，基于深度优先的状态剪枝算法无法完成对解空间的有效压缩，限制了基于FDSP的最大和类方法的可扩展性。因此，本文提出了基于并发搜索的CONC_FDSP和基于最佳优先搜索的BFS_FDSP。其中，前者通过并发执行多个深度优先搜索进程以缩短获得高质量下界的时间；后者利用部分解上界实现对解空间的排序，并通过不断展开上界最佳的部分解以快速获得最佳效用。此外，本文从理论上分析了CONC_FDSP的复杂度，并证明了BFS_FDSP的剪枝率优于所有基于FDSP的加速算法。实验结果表明，CONC_FDSP和BFS_FDSP能够显著提升基于信念传播的非完备推理算法的可扩展性。