| 一种基于势结构分组思想的任一时间联盟结构生成 |
| 李少芳[1] 胡山立[2] 石纯[3] |
| 关键词：多agent系统 联盟结构 势结构 任一时间 分组 |
| 主要内容：联盟形成是多agent系统中的一个关键问题，找到最优的联盟结构是NP-完全的．Sandholm和Larson等人已经证明，要建立最坏情况下的限界k，搜索联盟结构图的最底两层是必要且是充分的．在搜索联盟结构图的最底两层之后如何进一步搜索，是个长期以来未能完全解决的问题．在任务分配等实际问题中，不同联盟存在同势同值的特征，或同势的2个联盟的值相差不大．研究了最优势结构生成问题，分析了基于势结构的分组思想，并提出一个以势结构为搜索单位的新的任一时间联盟结构生成算法．算法在最小搜索之后给出进一步降低限界至2的搜索，也讨论了限界从2降到1的过程中由底向上的补充搜索．从搜索的势结构数和联盟结构数以及达到的限界上明显优于由Sandholm和Dang等人给出的算法，是基于势结构的联盟生成问题的一个重要进展． |
| 《计算机研究与发展》 2011,48(11).-2047-2054 |
| 全文下载请进入http://hightech.stlib.cn/tpi_1/sysasp/include/index.asp |
微信公众号