基于CBT的多源Steiner树构造算法

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

Construction of Steiner tree for multi-source based on CBT

For a graph-theoretical perspective, the problem of construction multicast distribution paths, modeled as 'Steiner trees', isNP-complete. So many heuristics-based algorithms are available to generate near-optimal trees. Typically, an algorithm first assignsthe edge costs for all links, and then examines various candidate paths for interconnecting a given set of nodes. Obviously, this strategydose not take into account of the variability of link costs because of the overlapping of multiple trees. In other word, as an algorithmruns by examining various paths, the link costs change. A study will embark on heuristics-based algorithms to tackle this 'modifiedSteiner tree' problem based on CBT.