| 给定限界要求的联盟结构生成 |
| |
| 引用本文： | 胡山立,石纯一. 给定限界要求的联盟结构生成[J]. 计算机学报, 2001, 24(11): 1185-1190 |
| |
| 作者姓名： | 胡山立 石纯一 |
| |
| 作者单位： | 1. 中国科学院软件研究所;福州大学计算机科学与技术系
2. 清华大学计算机科学与技术系, |
| |
| 基金项目： | 国家自然科学基金 ( 699730 2 3，697330 2 0 )，福建省自然科学基金( F0 0 0 12 )资助 |
| |
| 摘 要： | 联盟形成是多Agent系统中的一个关键问题，目的是通过寻找使联盟值的总和最大的联盟结构来使系统得到最大的效益。但通常可能的联盟结构的数目太大，不允许穷尽搜索来找出最优解。当实际问题提出最坏情况的具体限界要求时，如何以最小的搜索达到这个要求是需要解决的。文中给出的算法对给定的限界要求K*≥2以最少的搜索层数解决了这个问题。Sandholm等人已经证明，要建立最坏情况下的限界K（n)，搜索联盟结构图的最底两层是必要且是充分的，此时限界是n(系统的Agent 数）。以此为基础，文中给出了算法，在搜索最底两层之后，只要搜索一层就能保证K(n)≤3；而在搜索最底两层之后，最多搜索两层就能保证K(n)≤2。与Samdholm等人给出的算法相比，文中给出的算法达到指定限界的搜索量显著减少。
|
| 关 键 词： | 联盟结构 多Agent系统 联盟形式 人工智能 |
| 修稿时间： | 2000-03-20 |
Coalition Structure Generation with Given Required Bound |
| |
| HU Shan-Li ),) SHI Chun-Yi ) ). Coalition Structure Generation with Given Required Bound[J]. Chinese Journal of Computers, 2001, 24(11): 1185-1190 |
| |
| Authors: | HU Shan-Li ) ) SHI Chun-Yi ) ) |
| |
| Affiliation: | HU Shan-Li 1),3) SHI Chun-Yi 2) 1) |
| |
| Abstract: | |
| |
| Keywords: | coalition coalition structure algorithm multi-agent system |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
