一种生成最优联盟结构的任意时间算法  

Anytime Algorithm for Generating Optimal Coalition Structure

作　　者：张振荣[1] 刘惊雷[1] 张伟[1] 

机构地区：[1]烟台大学计算机学院,山东烟台264005

出　　处：《计算机工程》2011年第2期185-187,共3页Computer Engineering

基　　金：国家自然科学基金资助项目(60496323);山东省教育厅科技计划基金资助项目(J07JY24)

摘　　要：提出一种用于生成最优联盟结构的任意时间算法LVAA。利用分支限界技术和剪枝函数搜索联盟结构图的L1、L2和最顶层后,根据整数拆分对剩余的搜索空间进行横向剪枝,并在横向剪枝剩余的子空间内进行纵向剪枝,从而求得最优联盟结构。实验结果表明,该算法的剪枝效率较高,并能在任意时间点上找到最优值。This paper proposes Lateral and Vertical Anytime Algorithm（LVAA） to generate optimal coalition structure. It uses a branch and bound technique and pruning function to search L1, L2 and top layers of the coalition structure graph. According to the conception of the integer partition, it prunes the space horizontally, and then prunes in the remaining subspace vertically and finds the optimal coalition structure value. Experimental results show that pruning efficiency of the algorithm is high, and it can find the current optimal value at anytime.

关 键 词：LVAA算法 最优联盟结构 任意时间算法 分支限界技术 剪枝函数 

分 类 号：TP301.4[自动化与计算机技术—计算机系统结构]