求解欧氏距离斯坦纳最小树的逐步调优法

摘要：

　　对于有n个正则点的欧几里得距离斯坦纳树最小树问题, 设计了一种启发式算法，称为逐步调优法。先依次按辅助点数k 从1 取到n-2，求出这n+k个点的最小生成树，然后利用这些树的树长产生一个离散型的概率分布，接着按计算机模拟的方法，抽取一棵树作优化调整，这样多次迭代后，最后再按一定的算法作进一步的优化调整，获得一个近似最优解。算法较简单实用，经编程实现验证，效果良好。

关键词： 斯坦纳最小树 计算机模拟 概率分布 欧氏距离

作者: 林健良 施美珍 朱晓清 何明芳

作者单位: 华南理工大学理学院,广州,中国,510640

会议类型: 国内会议

会议名称: 2011年青年通信国际会议(ICYC2011)

会议地点: 澳门

会议语种:中文

页码: 284-288

在线出版日期: 2011-07-22（万方平台首次上网日期，不代表论文的发表时间）