首页 | 官方网站   微博 | 高级检索  
     

一种O(2.983n)时间复杂度的最优联盟结构生成算法
引用本文:刘惊雷,张伟,童向荣,张振荣.一种O(2.983n)时间复杂度的最优联盟结构生成算法[J].软件学报,2011,22(5):938-950.
作者姓名:刘惊雷  张伟  童向荣  张振荣
作者单位:烟台大学,计算机科学与技术学院,山东,烟台,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等人相关工作的改进和提高.

关 键 词:最优联盟结构  有效二部分解  克林闭包  时间复杂度的上下界  积分极限定理  时间序列分析
收稿时间:4/5/2009 12:00:00 AM
修稿时间:1/5/2010 12:00:00 AM

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.
Authors:LIU Jing-Lei  ZHANG Wei  TONG Xiang-Rong and 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 万方数据 等数据库收录!
点击此处可从《软件学报》浏览原始摘要信息
点击此处可从《软件学报》下载全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司    京ICP备09084417号-23

京公网安备 11010802026262号