给定限界要求的联盟结构生成

被引：18

作者：

胡山立

石纯一

机构：

[1] 福州大学计算机科学与技术系

[2] 清华大学计算机科学与技术系

来源：

计算机学报 | 2001年 / 11期

关键词：

联盟; 联盟结构; 算法; 多Agent系统;

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

联盟形成是多 Agent系统中的一个关键问题 ,目的是通过寻找使联盟值的总和最大的联盟结构来使系统得到最大的效益 .但通常可能的联盟结构的数目太大 ,不允许穷尽搜索来找出最优解 .当实际问题提出最坏情况的具体限界要求时 ,如何以最小的搜索达到这个要求是需要解决的 .文中给出的算法对给定的限界要求 K* 2以最少的搜索层数解决了这个问题 . Sandholm等人已经证明 ,要建立最坏情况下的限界 K ( n) ,搜索联盟结构图的最底两层是必要且是充分的 ,此时限界是 n(系统的 Agent数 ) .以此为基础 ,文中给出了算法 ,在搜索最底两层之后 ,只要搜索一层就能保证 K( n) 3 ;而在搜索最底两层之后 ,最多搜索两层就能保证 K( n) 2 .与 Samdholm等人给出的算法相比 ,文中给出的算法达到指定限界的搜索量显著减少 .

引用

页码：1285 / 1290

页数：6