| 摘要: |
| 首先,在有限整数集上建立有效拆分关系,在联盟集上建立有效二部分解关系,并设计了一种EOCS (effective optimal coalition structure)算法.该算法采用自底向上方式,只对具有有效二部分解关系的联盟进行二部分解来求联盟的优值,从而降低了二部分解的数量.随后,利用函数的克林闭包特性证明了EOCS算法的正确性,利用积分极限定理证明了EOCS 算法时间复杂度的下界是Ω(2.818n),用时间序列分析方法求出了EOCS 算法的上界是 |
| 关键词: 最优联盟结构 有效二部分解 克林闭包 时间复杂度的上下界 积分极限定理 时间序列分析 |
| DOI：10.3724/SP.J.1001.2011.03817 |
| 分类号: |
| 基金项目:国家自然科学基金(60496323); 山东省教育厅科技计划(J07JYJ24) |
|
| O(2.983n) Time Complexity Algorithm for Optimal Coalition Structure Generation |
|
LIU Jing-Lei, ZHANG Wei, TONG Xiang-Rong, ZHANG Zhen-Rong
|
|
School of Computer Science and Technology, Yantai University, Yantai 264005, China
|
| Abstract: |
| 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 O(3n). The EOCS algorithm’s design, correctness proof, and time complexity analysis are all improvements of Rothkopf and Rahwan’s related work. |
| Key words: optimal coalition structure effective bipartite splitting Kleene closure upper and lower bound of time complexity integration limit theorem time series analysis |
