Abstract:
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.
Key words:
Lateral and Vertical Anytime Algorithm(LVAA),
optimal coalition structure,
anytime algorithm,
branch and bound technique,
prune function
摘要： 提出一种用于生成最优联盟结构的任意时间算法LVAA。利用分支限界技术和剪枝函数搜索联盟结构图的L1、L2和最顶层后，根据整数拆分对剩余的搜索空间进行横向剪枝，并在横向剪枝剩余的子空间内进行纵向剪枝，从而求得最优联盟结构。实验结果表明，该算法的剪枝效率较高，并能在任意时间点上找到最优值。
关键词:
LVAA算法,
最优联盟结构,
任意时间算法,
分支限界技术,
剪枝函数
CLC Number:
ZHANG Zhen-Rong, LIU Jing-Lei, ZHANG Wei. Anytime Algorithm for Generating Optimal Coalition Structure[J]. Computer Engineering, 2011, 37(2): 185-187.
张振荣, 刘惊雷, 张伟. 一种生成最优联盟结构的任意时间算法[J]. 计算机工程, 2011, 37(2): 185-187.