中文摘要：

联盟形成是多agent系统中的一个关键问题，找到最优的联盟结构是NP-完全的．Sandholm和Larson等人已经证明，要建立最坏情况下的限界k，搜索联盟结构图的最底两层是必要且是充分的．在搜索联盟结构图的最底两层之后如何进一步搜索，是个长期以来未能完全解决的问题．在任务分配等实际问题中，不同联盟存在同势同值的特征，或同势的2个联盟的值相差不大．研究了最优势结构生成问题，分析了基于势结构的分组思想，并提出一个以势结构为搜索单位的新的任一时间联盟结构生成算法．算法在最小搜索之后给出进一步降低限界至2的搜索，也讨论了限界从2降到1的过程中由底向上的补充搜索．从搜索的势结构数和联盟结构数以及达到的限界上明显优于由Sandholm和Dang等人给出的算法，是基于势结构的联盟生成问题的一个重要进展．

英文摘要：

Coalition formation is a key topic in multi-agent system. However, finding the optimal coalition structure is NP-complete. Sandholm and Larson et al. showed that it was necessary and sufficient to search the lowest two levels of the coalition structure graph in order to establish a worstcase bound k. How to do further search after the lowest two levels of the coalition structure graph is a problem which hasn＇t been resolved well for a long time. In actual problem such as task assignment, the different coalitions have the characteristics of the same cardinality and same value, or the value of two coalitions with the same cardinality differs a bit. This paper studies the problem about the optimal cardinality structure generation, analyzes the grouping thought of cardinality structures and presents a new anytime algorithm of coalition structure generation. The algorithm gives further search that can decrease bound to 2. After the minimal search, the complement search from the bottom to top in the process is also discussed that declines bound from 2 to 1. It is obviously better than Sandholm et al. and Dang et al. ＇ s in the searching number of cardinality structure and coalition structure, or attaining bound, which is a important progress in the problem of coalition structure generation based on cardinality structure.