Coalition formation is a key topic in multi-agents system, however, finding the optimal coalition structure is NP-complete. Sandholm and Larson et al. Showed that it is necessary and sufficient to search the lowest two levels of the coalition structure graph in order to establish a worst-case bound k. When practical applications can present required real bound in the worst case, how to do a further minimal search to find a coalition structure which value can be guaranteed to be apart from optimal coalition structure value mutually in a given bound. It is a problem that deserves to study and hasn't been solved for a long time. This paper analyzes the different method of grouping influence on the number of cardinality structures, and presents a new grouping method and a new algorithm of coalition structure generation for the given bound in the worse case, decreases greatly the demanded searching the number of cardinality structure or coalition structure.%联盟形成是多Agent系统中的一个关键问题,寻求能极大化联盟值总和的最优联盟结构是NP-完全的.Sandholm等人已经证明,要建立最坏情况下的限界k,搜索联盟结构图的最底两层是必要且是充分的.当实际应用提出最坏情况下的具体限界要求时,如何通过进一步的最小搜索找到一个能保证在最坏情况下其联盟结构值与最优的联盟结构值相距在一个给定的限界内的联盟结构,是个长期以来值得研究而又尚未解决的问题.文中深刻分析了不同的分组方法对需要搜索的势结构数的影响,针对给定限界,在最坏情况下提出一种新的分组方法和一个新的联盟结构生成算法,使需要搜索的势结构数和联盟结构数比已有的算法都大大减少.
展开▼
