改进的基于拓扑分析的Steiner树近似算法

摘要

针对Berman近似算法k为3情况下的求解思想进行了改进.在使用Fibonacci堆求解出相应点对间最短距离的基础上,通过构建Voronoi域求出元组子树的耗费,并分析了Steiner树的网络拓扑结构以去除无用元组,从而简化拓扑,降低总体时间复杂度.在实验结果中,每个实例的过滤因子均大于0.9,有的甚至高达0.999,这表明大量无用的元组在进入评估阶段和构造阶段之前已被过滤掉,同时运行时间的减少也显示出改进算法在多播应用的路由寻径中更有效.