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

联盟结构是对Agent集合的一个划分,通过联盟形成联盟结构,可以使Agent之间形成有效的合作,完成单个Agent所不能完成的任务。然而联盟结构的数目和解空间比较大,以至于通过穷举搜索最优联盟结构是很复杂的。动态规划法通常用于求解具有最优子结构性质和重叠子问题性质的问题,文章在给出了Agent联盟的相关概念之后,论证了构造最优联盟结构问题恰恰具有这两类性质,因此利用动态规划法可以求解。最后给出了相应的算法,并得出采用动态规划法实现最优联盟结构的时间复杂度为O(3n)。

A kind of Method for Quick Constructing Optimal Coalition Structure

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.Dynamic 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(3n)in theory.