分布式约束优化是解决分布式推理任务的一个基本框架,是目前多Agent领域的研究热点。近几年来提出了许多优秀的分布式约束优化算法,这些算法大体上分为完备算法和非完备算法。非完备算法通过局部搜索,旨在找到最好的解,适用于求解大规模问题,但这类算法容易陷入局部最优解。而完备算法通过遍历搜索空间,旨在找到全局最优解,适用于中小规模问题。本论文针对如何提高完备算法的性能展开研究。完备算法的性能不仅依靠算法自身的求解策略,还依靠预处理阶段形成的Agent通信结构。目前针对完备算法的求解策略已提出了许多优化方法,但对Agent通信结构的优化研究较少。因此,研究分布式约束优化完备算法的Agent通信结构具有重要的学术意义和实际应用价值。本文从结点自身的属性特征和结点之间的约束关系特征这两方面对基于树型的通信结构进行研究。具体研究工作如下:①介绍了分布式约束的研究现状,并对分布式约束优化相关定义、完备算法的通信结构做了进一步阐述。另外,分别介绍了链式结构和树型结构的形成过程以及相应的典型完备算法。②提出了一种基于结点贡献的通信结构构建方法。该方法采用了约束一致性(Arc Consistency,AC)的思想,以结点对全局最优代价的贡献来对结点进行排序以构建Agent树型通信结构;将贡献值较高的结点优先排序,使得在求解过程中可以迅速地接近全局最优解。通过对不同的Agent树型通信结构对算法性能影晌的实验对比,表明该方法减少了算法的搜索空间,提高了算法的求解效率。③提出了一种基于图割点的通信结构构建方法。该方法利用问题建模后的约束图特征,以约束图的割点作为构建树型通信结构的依据,并在没有割点的情况下结合结点贡献的策略,在一定程度上提高了算法的并行性。实验结果表明,该方法提高了并行性,并减少搜索空间从而提高了算法的性能。最后,将本文提出的两种构建方法通过对比,分析这两种构建方法适合的问题类型。④为了验证所提的通信结构构造方法的可行性,本文将采用图割点通信结构的完备算法用于解决会议安排问题。与采用基于结点连接边的通信结构的完备算法对比,实验表明,采用基于图割点通信结构的完备算法具有更好优化性能,从而验证了本文提出的构建方法在实际应用中的可行性。