蚁群算法求解直径约束最小生成树问题

2012-12-27 12:04:30冯祖针杨建强
红河学院学报 2012年4期
关键词:规则信息

石 磊,冯祖针,杨建强

(红河学院 数学学院,云南 蒙自661100)

蚁群算法求解直径约束最小生成树问题

石 磊,冯祖针,杨建强

(红河学院 数学学院,云南 蒙自661100)

给定无向赋权图G和直径约束值D,直径约束最小生成树问题是查找一个直径不超过D最小权重的生成树.当时,其是NP-hard问题.用蚁群算法对其进行求解,设计了一种新的当前节点选择规则.分析和实验表明,基于新的节点选择规则的蚁群算法对直径约束最小生成树问题有较好的求解效果.

蚁群算法;直径约束最小生成树;直径约束

0 引言

直径约束最小生成(Bounded Diameter Minimum Spanning Tree,简记BDMST)问题是一个经典网络优化问题,在现实生活中有着广泛的应用,如路由优化、数据分发、分布式系统等[1,2].

BDMST问题描述为[3]:给定无向网络,任意节点,且;任意边且;任意边对应一个非负权值,称为长度或代价,.给定正整数D.设是一棵树,中节点的离心率定义为从到树中其它节点的最大距离.这里的距离是两个节点间边的数目.树的直径定义为节点的最大离心率.因此BDMST模型为:

文献[3]证明了直径约束值时的BDMST问题为NP-完全问题,因此BDMST问题不存在多项式时间算法,只能用启发式算法或人工智能算法求解.文献[4]提出一次性构造生成树算法(OTTC),OTTC算法是基于Prim算法基础上的贪婪启发式算法,在不违背直径约束的条件每次选择距离最近的节点加入当前树中,直到当前树含有网络的所有节点,但其性能较差.Raidl和Julstrom[5-6]提出了随机贪婪启发算法(RGH)和基于边集编码的遗……

登录APP查看全文

猜你喜欢
规则信息
撑竿跳规则的制定
数独的规则和演变
规则的正确打开方式
幸福(2018年33期)2018-12-05 05:22:42
让规则不规则
Coco薇(2017年11期)2018-01-03 20:59:57
订阅信息
中华手工(2017年2期)2017-06-06 23:00:31
TPP反腐败规则对我国的启示
搜索新规则
展会信息
中外会展(2014年4期)2014-11-27 07:46:46
信息
建筑创作(2001年3期)2001-08-22 18:48:14
健康信息
祝您健康(1987年3期)1987-12-30 09:52:32