给定限界势结构生成算法的改进  

Improvement of Cardinality Structure Generation Algorithm with Given Required Bound

作　　者：李少芳[1] 车艳[1] LI Shao fang CHE Yan(College of Information Engineering, Putian University, Putian 351100, China)

机构地区：[1]莆田学院信息工程学院,福建莆田351100

出　　处：《贵州大学学报（自然科学版）》2016年第4期69-73,共5页Journal of Guizhou University:Natural Sciences

基　　金：福建省教育厅资助项目(JA15440)

摘　　要：寻求最优联盟结构是NP-完全的,建立限界k=n/2的最小搜索是搜索联盟结构图的最底二层及顶层,在最小搜索之后,不同算法采用不同的搜索单位和路径进行有选择地部分搜索,以尽快达到给定限界值。在实际应用中,充分利用同势的两个联盟同值或值相差不大的特征,研究最优势结构生改进算法效率。文中通过分析势结构间的关系,指出了给定限界的势结构生成算法中一些可以去除的冗余搜索集合,从两个方面改进了算法,并进行了相关结果的证明。Finding the optimal coalition structure is NP-complete. The minimal search that can establish a bound k = n/2 is searching the lowest two levels and the top level of the coalition structure graph. After minimal search,different algorithms adopt the different search units and path to make selectively part search,as soon as possible to achieve a given bound value. In practice,making full use of the characters of the same or similar value in two coalitions with the same cardinality to study the most optimal cardinality structure generation to improve algorithm efficiency. The paper analyzes the relations between cardinality structures,and points out some redundancy search set than can be removed in cardinality structure generation algorithm with given required bound,improves the algorithm from two aspects and proves the related result.

关 键 词：势结构(CCS) 给定限界 多AGENT系统 算法改进 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]