互联网 qkzz.net
全刊杂志网:首页 > 女性 > 文章正文
刊社推荐

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


□ 李少芳 胡山立

  摘 要:联盟结构生成是多agent系统中的一个关键问题。Sandholm等人证明了要建立最坏情况下的限界k, 搜索联盟结构图的最底两层是必要且是充分的,如何进一步搜索是一个长期以来未能解决的问题。当实际应用提出最坏情况的具体限界要求时,如何通过部分的搜索达到这个限界?胡山立和石纯一给出了一种以层为单位的最优搜索算法, Dang等人和苏射雄等人给出了以势结构为单位的联盟结构生成算法。新算法MCCS提出在搜索最底两层及顶层后,搜索势结构集合MCCS(n, k)对应的联盟结构,以更少的势结构达到给定限界k。实验表明,在已有的算法中其所搜索的势结构最少,具有一定的理论和实践意义。

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

  中图分类号:TP301.6文献标志码:A

  文章编号:1001-3695(2009)09-3232-03

  doi:10.3969/j.issn.1001-3695.2009.09.008

  Coalition structure generation algorithm based oncardinality structure with given required bound

  LI Shao-fang, HU Shan-li2

  (1.Dept. of Electronic Information Engineering,Putian College,Putian Fujian 351100, China; 2.Dept. of Computer Science & Technology, Fuzhou University, Fuzhou 350108, China)

  Abstract:Coalition structure generation is a key topic in multi-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 present required real bound in the worst case, how to attain this bound via partial search? HU Shan-li and SHI Chun-yi gave an optimal 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.

......
很抱歉,暂无全文,若需要阅读全文或喜欢本刊物请联系《计算机应用研究》杂志社购买。
欢迎作者提供全文,请点击编辑
分享:
 

了解更多资讯,请关注“木兰百花园”
分享:
 
精彩图文


关键字
支持中国杂志产业发展,请购买、订阅纸质杂志,欢迎杂志社提供过刊、样刊及电子版。
关于我们 | 网站声明 | 刊社管理 | 网站地图 | 联系方式 | 中图分类法 | RSS 2.0订阅 | IP查询
全刊杂志赏析网 2017