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

摘要：

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

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

所属期刊栏目：26

分类号：TP301.6(计算技术、计算机技术)

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

在线出版日期：2009-11-03（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：3232-3234,3238