一种基于松弛算法改进的最小组播树生成方法

摘要

最小组播树是一个经典的网络传输问题。组播树生成问题可泛化为斯坦纳树问题,但后者通常情况下是一个NP完全问题。目前已经存在很多包括松弛算法在内的近似算法用于组播树的生成,但没有一种能达到最优。分析松弛算法执行过程中的所形成的环路,发现其中有些环路是可优化的,优化之后即可降低整棵树的传播低价,于是提出一种通过破除可优化环来生成最小组播树的方法。该方法首先分析可优化环的条件,分析环路中的中转节点的特点,设计寻找环的分支节点的子算法和破环的子算法,最终得出寻找最小代价组播树的方法,数据模拟结果表明,在不增加时间复杂度的前提下该方法能够获得目前为止最小的组播树代价。