一种O（2．983^n）时间复杂度的最优联盟结构生成算法

首先,在有限整数集上建立有效拆分关系,在联盟集上建立有效二部分解关系,并设计了一种EOCS(effective optimal coalition structure)算法.该算法采用自底向上方式,只对具有有效二部分解关系的联盟进行二部分解来求联盟的优值,从而降低了二部分解的数量.随后,利用函数的克林闭包特性证明了EOCS算法的正确性,利用积分极限定理证明了EOCS算法时间复杂度的下界是O(2.818n),用时间序列分析方法求出了EOCS算法的上界是O(2.983n).最后,将EOCS算法与其他算法作了对比,指出无论联盟值满足何种概率分布,EOCS算法都能在O(2.983n)时间内找出最优联盟结构.Rothkopf提出的DP(dynamic programming)算法和Rahwan提出的IDP(improved dynamic programming)算法能够在O(3n)时间内求出最优联盟结构.所作的EOCS算法设计、正确性证明、时间复杂度的上下界分析都是对Rothkopf及Rahwan等人相关工作的改进和提高.