分布式约束优化问题（DCOP）是多智能体系统（Multi-agent System,MAS）的基本框架,在该框架中各个智能体（Agent）通过相互合作的方式来求解目标优化的任务。它是多智能体协作问题的重要建模技术并且被成功应用于任务调度,传感器网络和智能电网等领域。基于伪树的完备求解算法作为求解DCOP的重要手段,具有很高的学术研究和实际应用价值。然而,现有的基于伪树的完备算法普遍存在着通信消耗较大,解决问题规模较小,运行时间较长等问题。固本文致力于提升此类算法的效率、可扩展性和求解速度,以推进其在实际场景中的应用。具体地,本文针对基于伪树的完备算法进行了如下研究:（1）本文提出了一种不依赖界的剪枝技术BIP（Bound-Independent Pruning）。具体来说,本文首先提出了最优主支持POS（Primary Optimal Support）的概念,其具有以下两个属性:1)利用POS可确定一个包含最优解的解空间的子集;2)仅利用效用表的部分信息可求得POS。基于POS的上述两个属性,本文提出了BIP,其仅利用本地约束信息和部分邻居节点的赋值信息就可实现对解空间的剪枝,从而极大地提升了完备算法的效率,并且降低了完备算法的求解时间。本文从理论上证明了BIP的正确性。（2）本文将BIP剪枝技术应用于基于伪树的同步和异步完备搜索算法,分析并解决了执行BIP所带来的潜在问题。具体来说,基于BIP所确定的子集,每个智能体不仅可以为本地变量剪枝还可以为其孩子节点提供建议剪枝,然而为孩子节点提供建议剪枝可能会扩大每个智能体搜索结果所依赖的上文,使得搜索算法中现有的上下文兼容性检查机制没有足够的上下文信息来确定基于BIP的搜索结果的有效性。为此,本文提出了可接受性检查机制（Acceptability Testing Mechanism,ATM）。ATM在现有的上下文兼容性检查机制的基础上,通过检查值域的变化过滤掉不可接受的搜索结果,从而保证了基于BIP的搜索算法的完备性。本文从理论上证明了在基于伪树的搜索算法中实施BIP和ATM的正确性。实验结果表明,BIP可极大地降低基于伪树的完备搜索算法的通信量,显著的提高它们的可扩展性和求解速度。（3）本文将BIP剪枝技术应用于基于伪树的内存有界完备推理算法。具体来说,给定一个Cycle-cut（CC）节点的赋值组合实例,BIP可以仅利用该实例和本地约束确定一个包含最优解的解空间的子集。每个CC节点可以利用该子集为本地变量剪枝以降低迭代推理的次数和缩短求解时间。本文从理论上证明了在基于伪树的内存有界完备推理算法中实施BIP的正确性。实验结果表明,BIP可显著的提高推理算法的效率和速度。