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

Construction of Steiner tree for multi-source based on CBT

作　　者：马金柱[1] 刘捷[1] 周俊懿[1] 

机构地区：[1]山东大学计算机科学与技术学院,山东济南250100

出　　处：《计算机工程与设计》2006年第17期3172-3174,共3页Computer Engineering and Design

基　　金：山东省中青年科学家奖励基金项目(03BS004)。

摘　　要：构造最小代价树问题可形式化为图论中Steiner树问题。而Steiner树的求解已经被证明是一个NP-complete问题,不可能在多项式时间求得其精确解,所以出现许多启发式算法:在可接受时间内,得到一棵近似的最优多播树。这些算法一般先指定所有链接边的费用,通过一定方法或规则,找出包含源端和所有目的端的一棵近似最优的多播树。很显然,它们并没有考虑由于路径的共享重叠而引起最小生成树链接边费用的变化。现利用CBT算法思想对变化的费用进行建模并对典型启发式算法作了改进,以适应不断变化了的链路费用。Foragraph-theoreticalperspective, the problem of construction multicast distribution paths, modeled as ‘Steiner trees＇, is NP-complete. So many heuristics-based algorithms are available to generate near-optimal trees, Typically, an algorithm first assigns the edge costs for all links, and then examines various candidate paths for interconnecting a given set of nodes. Obviously, this strategy dose not take into account of the variability of link costs because of the overlapping of multiple trees. In other word, as an algorithm runs by examining various paths, the link costs change. A study will embark on heuristics-based algorithms to tackle this modified Steiner tree＇ problem based on CBT.

关 键 词：STEINER树 多播 链路共享 共享路径 启发式算法 核心树 

分 类 号：TP393.02[自动化与计算机技术—计算机应用技术]