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

摘要

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