论文部分内容阅读
联盟形成是多Agent系统中的一个关键问题．寻求能极大化联盟值总和的最优联盟结构是NP一完全的．Sandholm等人已经证明要建立最坏情况下的限界k，搜索联盟结构图的最底两层是必要且是充分的，在搜索联盟结构图的最底两层之后如何进一步搜索，是个长期以来未能解决的问题．Dang等人给出的算法，对于奇数限界k≥3，在搜索最底两层及顶层后，进一步搜索最大联盟的势不小于[ n（k- 1）/（k＋1）]的所有联盟结构，是迄今所知的第1个不以层为搜索单位的算法，对于较小的限界明显地优于Sandholm等人给出的算法．文