一种快速构建最优联盟结构的方法  

A kind of Method for Quick Constructing Optimal Coalition Structure

作　　者：刘惊雷[1] 童向荣[1] 张伟[1] 

机构地区：[1]烟台大学计算机系,烟台264005

出　　处：《计算机工程与应用》2006年第4期35-37,44,共4页Computer Engineering and Applications

基　　金：国家自然科学基金资助项目(编号:60496323);烟台大学青年科学基金项目(编号:JS03Z1)

摘　　要：联盟结构是对Agent集合的一个划分,通过联盟形成联盟结构,可以使Agent之间形成有效的合作,完成单个Agent所不能完成的任务。然而联盟结构的数目和解空间比较大,以至于通过穷举搜索最优联盟结构是很复杂的。动态规划法通常用于求解具有最优子结构性质和重叠子问题性质的问题,文章在给出了Agent联盟的相关概念之后,论证了构造最优联盟结构问题恰恰具有这两类性质,因此利用动态规划法可以求解。最后给出了相应的算法,并得出采用动态规划法实现最优联盟结构的时间复杂度为O(3n)。Coalition structure is a partition of agent set,forming coalition structure by coalition can make agents cooperate effectively and fulfill task that single agent can＇t.but often the number of coalition structure is too large to allow exhaustive search for the optimal one.Dynamlc programming usually is used for the problem that have the superior sub-structure property and overlapped sub-problem property,after giving some concepts of coalition structure, demonstrate that the optimal coalition structure has these property,so that this problem can be solved by dynamic programming.At last,give the relative algorithm and prove that time complexity of search the optimal coalition structure is O（3^n）in theory.

关 键 词：联盟结构 最优联盟结构 动态规划法 时间复杂度 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]