|
|||||
|
|
| 最坏情况具有限界的联盟结构生成 | |
| 引用本文： | 胡山立,李少芳,石纯一.最坏情况具有限界的联盟结构生成[J].计算机研究与发展,2009,46(8). |
| 作者姓名： | 胡山立 李少芳 石纯一 |
| 作者单位： | 1. 福州大学计算机科学与技术系,福州,350108 2. 莆田学院电子信息工程学系,福建莆田,351100 3. 清华大学计算机科学与技术系,北京,100084 |
| 基金项目： | 国家自然科学基金项目 |
| 摘 要： | 联盟形成是多Agent系统中的一个关键问题. 寻求能极大化联盟值总和的最优联盟结构是NP-完全的. Sandholm等人已经证明要建立最坏情况下的限界k,搜索联盟结构图的最底两层是必要且是充分的,在搜索联盟结构图的最底两层之后如何进一步搜索,是个长期以来未能解决的问题. Dang等人给出的算法,对于奇数限界k≥3,在搜索最底两层及顶层后,进一步搜索最大联盟的势不小于- n(k-1)/(k+1) - 的所有联盟结构,是迄今所知的第1个不以层为搜索单位的算法,对于较小的限界明显地优于Sandholm等人给出的算法. 文中深刻分析了联盟结构间的关系,提出的算法在搜索最底两层后,只需进一步搜索最大联盟的势等于- n(k-1)/(k+1) - 的所有联盟结构,从而使需要搜索的联盟结构数大大减少,并进一步将搜索某些层最大联盟的势等于- n(k-1)/(k+1) - 的联盟结构巧妙地改为搜索联盟结构数更少的相应层,使需要搜索的联盟结构数进一步减少,较大地改进了Sandholm等人和Dang等人的工作. |
| 关 键 词： | 联盟 联盟结构 任一时间算法 多Agent系统 |
Coalition Structure Generation with Worst-Case Finite Bound from the Optimal Guarantees |
|
| Hu Shanli,Li Shaofang,Shi Chunyi.Coalition Structure Generation with Worst-Case Finite Bound from the Optimal Guarantees[J].Journal of Computer Research and Development,2009,46(8). | |
| Authors: | Hu Shanli Li Shaofang Shi Chunyi |
| Affiliation: | Department of Computer Science and Technology;Fuzhou University;Fuzhou 350108;Department of Electronic Information Engineering;Putian College;Putian;Fujian 351100;Department of Computer Science and Technology;Tsinghua University;Beijing 100084 |
| Abstract: | |
| Keywords: | coalition coalition structure anytime algorithm multi-agent system |
| 本文献已被 CNKI 万方数据 等数据库收录！ | |