摘要：联盟结构是对kent集合的一个划分，通过联盟形成联盟结构，可以使Agent之间形成有效合作，完成单个kent所不能完成的任务。本文提出了BDP来求最优联盟结构，该算法利用整数二部拆分来生成二部划分，并利用二部拆分的界来对搜索空间进行限界。随后把该算法与DP算法做了理论和实验分析，理论上得出BIDP所需要的空间比DP减少33．3％。实验表明，当联盟值满足均匀分布和正态分布，BIDP在21个Agent的情况下，搜索空间比DP减少35％和92％。最后对求最优联盟结构的确定式算法作了总结，即时间复杂度的上界是O（3n），下界是Ω（2n），空间复杂度是θ（2n）。

关键词：最优联盟结构 bidp算法 整数二部拆分 二部划分 时间和空间复杂度 

单位：烟台大学计算机学院 山东烟台264005