论文部分内容阅读
构造最小代价树问题可形式化为图论中Steiner树问题。而Steiner树的求解已经被证明是一个NP-complete问题，不可能在多项式时间求得其精确解，所以出现许多启发式算法：在可接受时间内，得到一棵近似的最优多播树。这些算法一般先指定所有链接边的费用，通过一定方法或规则，找出包含源端和所有目的端的一棵近似最优的多播树。很显然，它们并没有考虑由于路径的共享重叠而引起最小生成树链接边费用的变化。现利用CBT算法思想对变化的费用进行建模并对典型启发式算法作了改进，以适应不断变化了的链路费用。