基于整数二部拆分的最优联盟结构求解
【出 处】:《
计算机工程与科学
》
CSCD
2010年第32卷第5期 64-66页,共4页
【作 者】:
刘惊雷
;
张振荣
;
张伟
【摘 要】
联盟结构是对kent集合的一个划分,通过联盟形成联盟结构,可以使Agent之间形成有效合作,完成单个kent所不能完成的任务。本文提出了BDP来求最优联盟结构,该算法利用整数二部拆分来生成二部划分,并利用二部拆分的界来对搜索空间进行限界。随后把该算法与DP算法做了理论和实验分析,理论上得出BIDP所需要的空间比DP减少33.3%。实验表明,当联盟值满足均匀分布和正态分布,BIDP在21个Agent的情况下,搜索空间比DP减少35%和92%。最后对求最优联盟结构的确定式算法作了总结,即时间复杂度的上界是O(3n),下界是Ω(2n),空间复杂度是θ(2n)。
相关热词搜索:
上一篇:一种面向主体的服务规则模拟验证方法
下一篇:一种基于时态的扩展值辩论框架