基于势结构的给定限界的联盟结构生成算法  

Coalition structure generation algorithm based on cardinality structure with given required bound

作　　者：李少芳[1] 胡山立[2] 

机构地区：[1]莆田学院电子信息工程学系,福建莆田351100 [2]福州大学计算机科学与技术系,福州350108

出　　处：《计算机应用研究》2009年第9期3232-3234,3238,共4页Application Research of Computers

基　　金：国家自然科学基金资助项目(60573076)

摘　　要：联盟结构生成是多agent系统中的一个关键问题。Sandholm等人证明了要建立最坏情况下的限界k,搜索联盟结构图的最底两层是必要且是充分的,如何进一步搜索是一个长期以来未能解决的问题。当实际应用提出最坏情况的具体限界要求时,如何通过部分的搜索达到这个限界?胡山立和石纯一给出了一种以层为单位的最优搜索算法,Dang等人和苏射雄等人给出了以势结构为单位的联盟结构生成算法。新算法MCCS提出在搜索最底两层及顶层后,搜索势结构集合MCCS(n,k)对应的联盟结构,以更少的势结构达到给定限界k。实验表明,在已有的算法中其所搜索的势结构最少,具有一定的理论和实践意义。Coalition structure generation is a key topic in muhi-agent system. Sandholm et al. proved that it was necessary and sufficient to search the lowest two levels of the coalition structure graph in order to establish a worst-case bound k. How to do a further search after？ That is a problem which hasn＇t been resoled for a long time. When practical applications could pres- ent required real bound in the worst case, how to attain this bound via partial search？ HU Shan-li and SI-II Chun-yi gave an op- timal searching algorithm whose searching unit was level. Dang et al. and SU She-xiong et al. gave their coalition structure generation algorithms whose searching unit was cardinality structure. New algorithm MCCS proposed that searching all coalition structures corresponding to the set of cardinality structure MCCS（ n, k） could attain the given required bound k with more less cardinality structures after searching the lowest two levels and the top level in the coalition structure graph. Finally, comparing to the existing algorithms, it obviously searches less cardinality structures and has some theoretical and practical meaning.

关 键 词：联盟结构 势结构 给定限界 算法MCCS 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]