| 一种O(2.983n)时间复杂度的最优联盟结构生成算法 |
| |
| 引用本文： | 刘惊雷,张伟,童向荣,张振荣. 一种O(2.983n)时间复杂度的最优联盟结构生成算法[J]. 软件学报, 2011, 22(5): 938-950. DOI: 10.3724/SP.J.1001.2011.03817 |
| |
| 作者姓名： | 刘惊雷 张伟 童向荣 张振荣 |
| |
| 作者单位： | 烟台大学,计算机科学与技术学院,山东,烟台,264005 |
| |
| 基金项目： | 国家自然科学基金，山东省教育厅科技计划 |
| |
| 摘 要： | 首先,在有限整数集上建立有效拆分关系,在联盟集上建立有效二部分解关系,并设计了一种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等人相关工作的改进和提高.
|
| 关 键 词： | 最优联盟结构 有效二部分解 克林闭包 时间复杂度的上下界 积分极限定理 时间序列分析 |
| 收稿时间： | 2009-04-05 |
| 修稿时间： | 2010-01-05 |
O(2.983n) Time Complexity Algorithm for Optimal Coalition Structure Generation |
| |
| LIU Jing-Lei,ZHANG Wei,TONG Xiang-Rong and ZHANG Zhen-Rong. O(2.983n) Time Complexity Algorithm for Optimal Coalition Structure Generation[J]. Journal of Software, 2011, 22(5): 938-950. DOI: 10.3724/SP.J.1001.2011.03817 |
| |
| Authors: | LIU Jing-Lei ZHANG Wei TONG Xiang-Rong ZHANG Zhen-Rong |
| |
| Affiliation: | (School of Computer Science and Technology,Yantai University,Yantai 264005,China) |
| |
| Abstract: | |
| |
| Keywords: | optimal coalition structure effective bipartite splitting Kleene closure upper and lower bound of time complexity integration limit theorem time series analysis |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《软件学报》浏览原始摘要信息 |
|
点击此处可从《软件学报》下载全文 |
|
