求解满瓶颈Steiner树

首先对Steiner树,瓶颈Steiner树研究现状加以介绍,指出满瓶颈Steiner树就是在已知图中找一颗树S,使给定的点集在S中的点都为叶子,且最大的边权值最小,然后给出满瓶颈Steiner树的定义,利用分解,转化,组合的思想,给出求解满瓶颈Steiner树问题的一个多项式算法,证明算法正确性,说明该算法的时间复杂性,最后给出相应的数值例子,说明算法正确性.     

扩展Steiner树问题的选址应用研究

提出扩展Steiner树问题的选址模型,给出了该模型基于最小生成树的启发式算法.在此基础上,分析了一个居民点只能与一家连锁店相关联的选址问题,并用算例验证了该选址方案的可行性.     

改进的时延约束Steiner树算法

针对现有时延约束Steiner树算法时间复杂度较高以及生成的组播树代价较高的问题,提出了一种改进的时延约束Steiner树算法.该算法采用Dijkstra算法路径递增的基本思想和链路共享的方法,在快速搜索阶段,依次搜索到当前树有最小可行代价的节点,将目的节点通过最小可行代价路径加入组播树;在异常处理阶段,将遗漏的目的节点通过最小时延路径加入组播树,进而生成满足时延约束的Steiner树.理论分析和实验结果表明,与同类算法相比,该算法能够以较低的时间复杂度,取得较好的组播树代价.     

基于范数下的反瓶颈Steiner树问题

讨论了在l1范数下的反瓶颈Steiner树问题.对于给定的一个可行解,修改带限制的边权使其成为瓶颈Steiner树问题的最优解,并且在l1范数下边权的修改费用最小.讨论了最优目标值的范围,在此基础上给出了一个求解反瓶颈Steiner问题的多项式时间算法.     

一种修复网络拓扑的Steiner树移动控制算法

针对无线Ad Hoc网络中拓扑修复成功率低、节点移动开销大的问题,提出了一种Steiner树移动控制算法(SMC).采用三近似最少Steiner点算法建立一棵包含网络节点和Steiner点的Steiner树,然后将引入的Steiner点作为节点移动的目的点,选择并调度一些节点移动到这些Stei-ner点上,最后更新网络拓扑,迭代执行算法直到建立一个连通的网络拓扑.仿真结果表明,与基于分区最小生成树的移动控制算法相比,SMC算法不仅修复网络拓扑的成功率可达到100%,而且还显著降低了节点移动开销,其中节点移动总距离减小了37%~45%,节点移动总数减少了9%~29%.     

分簇式ad hoc多播路由的超图法

在大规模的ad hoc网络中,设计分簇式路由算法可以解决节点数目增长带来的可扩展性问题.给出分簇式多播算法的超图模型,提出基于Steiner超树模型的ad hoc多播路由的集中式算法和分布式算法,并对两种算法的复杂度和通信开销做出分析.     

扩展Steiner树问题的选址应用研究

提出扩展Steiner树问题的选址模型，给出了该模型基于最小生成树的启发式算法。在此基础上，分析了一个居民点只能与一家连锁店相关联的选址问题，并用算例验证了该选址方案的可行性。     

关于满Steiner树问题的一个近似算法

满Steiner树问题(TST)是求解一个正则点都是叶子的最小Steiner树问题.Fabio Viduani Martinez等人给出了此问题的近似算法,它的性能比为2ρ-ρ/(3ρ-2)≈2.52,而目前求解Steiner树问题的近似算法的性能比,最小值约为1.550.对满Steiner树问题给出了一个近似算法,并将它的性能比改进为2ρ-3ρ/(6ρ-2)≈2.463.     

启发式进货规划求解Steiner树问题

求解Steiner树对通信网络点对多点路由优化问题有重要意义,已被证明是NP－complete的。通过把图形简化技术、进货规划方法和KMB启发式上结合,提出了一种求解Steiner树问题的新方法,提高了算法的效率,仿真结果表明,本算法是有效的,性能优于传统的启发式算法。     

Steiner最小树问题及其应用

Steiner最小树问题是一个历史悠久的经典的组合优化问题,由于应用广泛,多年来一直受到研究者的广泛关注。介绍了各种Steiner树问题及其求解算法和实际应用。