给定限界的势结构分组与联盟结构生成

• 作者: 李少芳 石纯一 胡山立
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 多Agent系统 联盟结构 势结构 给定限界 分组
• 年，卷（期）: 2012,（12）
• 所属期刊栏目: 研究论文
• 页码范围: 2618-2624
• 页数: 7页
• 分类号: TP18
• 字数: 6455字
• 语种: 中文
• DOI: 10.3724/SP.J.1016.2012.02618

摘要

联盟形成是多Agent系统中的一个关键问题,寻求能极大化联盟值总和的最优联盟结构是NP-完全的.Sandholm等人已经证明,要建立最坏情况下的限界k,搜索联盟结构图的最底两层是必要且是充分的.当实际应用提出最坏情况下的具体限界要求时,如何通过进一步的最小搜索找到一个能保证在最坏情况下其联盟结构值与最优的联盟结构值相距在一个给定的限界内的联盟结构,是个长期以来值得研究而又尚未解决的问题.文中深刻分析了不同的分组方法对需要搜索的势结构数的影响,针对给定限界,在最坏情况下提出一种新的分组方法和一个新的联盟结构生成算法,使需要搜索的势结构数和联盟结构数比已有的算法都大大减少.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	石纯一	清华大学计算机科学与技术系	85	3189	30.0	55.0
2	李少芳	莆田学院电子信息工程学系	25	162	7.0	12.0
3	胡山立	福州大学计算机科学与技术系	41	542	13.0	22.0