一种最小代价组播树的快速算法

A FAST HEURISTIC ALGORITHM OF MINIMUM COST MULTICAST TREE

本文对KMB算法进行了改进,提出了一种快速的最小代价组播树算法,它只需使用一次PR IM算法,也不需要判断叶结点,从而快速地获得了最小代价组播树,减少了算法的运行时间。随机网络模型的仿真实验表明:该算法的计算时间远小于KMB算法,是一种快速、稳定、高效的算法。

In this paper,we has improved the KMB algorithm and propose a fast algorithm of minimum cost muhicast tree. The algorithm uses PRIM algorithm only once and needn＇t judge if the leaf of the tree is the member of a group or not. Thus the running time was decreased in our algoritbm. And tbe minimum cost tree was obtained very fast. The simulated experience result sbows that the computed time of this algoritbm is far less tban the KMB algorithm,and it is a fast,stable and efficient heuristic.