一种O(2.983n)时间复杂度的最优联盟结构生成算法

摘要

First, this paper establishes an effective partition relationship in the finite integer set and an effective splitting relationship in the coalition set, and devises an EOCS (effective optimal coalition structure) algorithm,which only evaluates bipartite effective splittings of coalition to find the optimal value from bottom to top, so it decreases the number of bipartite splitting.Secondly, the correctness of the EOCS algorithm is proved based on the Kleene closure function.Moreover, this paper proves that the EOCS lower bound is Ω(2.818n) by the integration limit theorem, and discovers that the EOCS upper bound is O(2.983n) by the time serial analysis technique.Finally,this paper compares the EOCS algorithm with other algorithms to point out that the EOCS algorithm can find optimal coalition structure in O(2.983n) time whether the coalition values meet which probability distributions or not.The DP (dynamic programming) algorithm and the IDP (improved dynamic programming) algorithm proposed by Rothkopf and Rahwan can find an optimal solution in 0(3n).The EOCS algorithm's design, correctness proof,and time complexity analysis are all improvements of Rothkopf and Rahwan's related work.%首先,在有限整数集上建立有效拆分关系,在联盟集上建立有效二部分解关系,并设计了一种EOCS(effective optimal coalition structure)算法.该算法采用自底向上方式,只对具有有效二部分解关系的联盟进行二部分解来求联盟的优值,从而降低了二部分解的数量.随后,利用函数的克林闭包特性证明了EOCS算法的正确性,利用积分极限定理证明了EOCS算法时间复杂度的下界是Ω(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等人相关工作的改进和提高.