作　　者： ; ; ;

机构地区： 烟台大学计算机学院计算机科学与技术系

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

摘　　要： 联盟结构是对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.

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

领　　域： [自动化与计算机技术] [自动化与计算机技术]