首页 | 本学科首页   官方微博 | 高级检索  
     

基于整数二部拆分的最优联盟结构求解
引用本文:刘惊雷,张振荣,张伟.基于整数二部拆分的最优联盟结构求解[J].计算机工程与科学,2010,32(5):64-66.
作者姓名:刘惊雷  张振荣  张伟
作者单位:烟台大学计算机学院,山东,烟台,264005
基金项目:国家自然科学基金资助项目(60496323);;山东省教育厅科技计划资助项目(J07JYJ24)
摘    要:联盟结构是对Agent集合的一个划分,通过联盟形成联盟结构,可以使Agent之间形成有效合作,完成单个Agent所不能完成的任务。本文提出了BIDP来求最优联盟结构,该算法利用整数二部拆分来生成二部划分,并利用二部拆分的界来对搜索空间进行限界。随后把该算法与DP算法做了理论和实验分析,理论上得出BIDP所需要的空间比DP减少33.3%。实验表明,当联盟值满足均匀分布和正态分布,BIDP在21个Agent的情况下,搜索空间比DP减少35%和92%。最后对求最优联盟结构的确定式算法作了总结,即时间复杂度的上界是O(3n),下界是Ω(2n),空间复杂度是Θ(2n)。

关 键 词:最优联盟结构  BIDP算法  整数二部拆分  二部划分  时间和空间复杂度
收稿时间:2009-11-15
修稿时间:2010-02-09

Optimal Coalition Structure Solving Based on the Bipartite of Integer
LIU Jing-lei,ZHANG Zhen-rong,ZHANG Wei.Optimal Coalition Structure Solving Based on the Bipartite of Integer[J].Computer Engineering & Science,2010,32(5):64-66.
Authors:LIU Jing-lei  ZHANG Zhen-rong  ZHANG Wei
Affiliation:School of Computer Science and Technology/a>;Yantai University/a>;Yantai 264005/a>;China
Abstract:Coalition structure is a partition of the agent set,forming a coalition structure by coalition can make agents cooperate effectively and fulfill the tasks that a single agent can not.In this paper,we propose a BIDP(Bipartite of Integer Dynamic Programming)algorithm to solve the optimal coalition structure generation,which adopts the bipartite of integer to generate bipartite partitions,and takes the bound of integer bipartite as the bound of the search space.And a theoretical analysis proves that BIDP can s...
Keywords:optimal coalition structure  BIDP algorithm  bipartite of integer  bipartite partition  time and space complexity  
本文献已被 CNKI 万方数据 等数据库收录!
点击此处可从《计算机工程与科学》浏览原始摘要信息
点击此处可从《计算机工程与科学》下载全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号