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

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

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

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

约束最小支撑树问题

主要研究两类约束最小支撑树问题,即点约束和边约束最小支撑树问题.点约束最小支撑树问题主要研究了点v不是叶子和点v是叶子两个具体约束问题,边约束最小支撑树问题的约束条件分别为包含给定边e0和不包含给定边e0,对上述问题分别给出了一些基本定理和算法.     

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

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

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

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

基于电势的最优加权Steiner树蚂蚁算法及其选址应用

在传统欧氏Steiner树的基础上,提出加权Steiner最优树模型,适用于求解必须考虑结点权值情况下的最短路问题.借用电场理论中电势的概念给出了模型的蚂蚁算法实现,并以某大型电子商务企业物流中心选址问题为例,验证了模型的实用性及算法的有效性.     

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

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

可分拟满Steiner树的结构与生成算法

本文给出可分拟满Ｓｔｅｉｎｅｒ树的结构性质及生成算法，利用此算法可直接构造出具有这类结构的Ｓｔｅｉｎｅｒ最小树。     

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

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

最小r元树算法

给出了最小r元树的两种算法及复杂性分析。     

基于层次分析法与加权Steiner树问题的物流配送中心选址研究

物流配送中心一般是在备选点已知的情况下进行选址的。对于备选点的选取,选用层次分析法解决;对于配送中心地址的选取,选用图的Steiner树问题解决,并给出该问题的基于多Agent系统的启发式算法。在此基础上,分析和实现了电子商务环境下物流配送中心的选址问题,并通过示例验证了该选址模型的可行性。     

度约束欧氏Steiner最小树问题及其求解

在欧氏Steiner最小树的基础上,对每个正则点加上了度约束限制,提出了度约束欧氏Steiner最小树问题,分析了该问题的特性,给出了该问题的模拟退火和蚂蚁算法求解过程,并使用Delphi语言编程,在Windows XP平台上运行通过．通过大量算例的计算结果验证了该问题的实用性及算法的有效性．     

八角形斯坦纳树问题的文化基因算法

针对多端线网互连问题,提出以超大规模集成电路物理设计中布线阶段应用较多的斯坦纳树为切入点,采用一种基于种群的全局搜索和基于个体的局部启发式搜索相结合的文化基因算法,对八角形斯坦纳树的结构进行优化,从而进一步缩减线长. 使用Prim算法预处理取得初始种群,并重新修改了原本的文化基因的编码以及相关操作,以便可以处理八角形斯坦纳树构建这一离散问题,利用八角形结构,使其能在全局范围内,快速收敛并全局寻优. 实验结果表明,所提算法能获得较好拓扑的八角形斯坦纳树,快速得到多端线网最优或者较优的布线结果,缩减布线的线长.     

欧氏Steiner最小树的Delaunay三角网混合智能求解方法

欧氏Steiner最小树问题是组合优化中一个经典的NP难题,在许多实际问题中有着广泛的应用.由于使用普通智能算法求解较大规模问题时,极易陷入拓扑结构的局部最优,因此,基于Delaunay三角网技术并结合智能算法的有关思想,设计了一种改进的混合型智能求解方法,可大幅度提高算法在寻找更好拓扑结构上的有效性.算法在Matlab环境下编程实现,经大量STEINLIB中的标准数据实例测试和验证,获得了满意的效果,为求解较大规模的欧氏Steiner最小树问题提供了新的有效方法.     

一类度约束最小生成树问题的Dijkstra算法

度约束最小生成树问题是网络设计和优化中的一个NP难题。结合该问题的特征,基于Dijkstra算法的基本思想,提出了一种求解网络G关于指定节点的最大度最小生成树的新算法。该算法在保证指定节点最大度的前提下,每次通过选取剩余边中权最小的边加入当前网络,最终得到网络G关于指定节点的最大度最小生成树。同时对算法的复杂度进行了分析。最后通过与其他算法的仿真比较和算例,表明了新算法的有效性。     

图的Steiner最小树的竞争决策算法

图的Steiner最小树问题是一个著名的NP难题,在通讯网络、VLSI等工程实践中有着重要的应用.在分析图的Steiner最小树问题数学性质的基础上,提出了图的Steiner最小树的竞争决策算法.为了验证算法的有效性,求解了OR-Library中的基准问题,测试结果表明了算法具有较好的求解效果.     

基于进化规划的网络多目标路由算法

多目标路由问题要求极小化网络带宽资源消耗 ,它与图论中 NP完全的 Steiner问题等价 ,不存在多项式时间算法 ,只能采用近似算法或启发式算法 .进化算法是一类有效求解优化问题的新算法 .应用进化算法中的进化规划方法 ,求解 Steiner问题 ,提出了一种新的多目标路由算法 .仿真结果显示 ,该算法性能高于启发式方法     

基于遗传优化的WSNs多源单汇路由算法

针对无线传感器网络中的多源单汇路由问题,综合考虑无线传感器网络中链路带宽、延迟和路径节点最小剩余能量三种度量,建立了多源单汇路由问题的系统模型,将其转化为求解多约束最小Steiner树问题,已知该问题是NP难的问题,给出了基于遗传优化的求解算法,采用基于备选路径集的整数序列编码表示一棵生成树,设计相应的交叉和变异算子,以及对非法染色体进行修复的机制,最后在遗传算法的计算过程中选择合理的适应度函数,找到一棵满足多约束的能耗趋于最小且状态稳定Steiner树.理论分析和数值试验结果表明所提出的遗传求解算法收敛速度快、可靠性高,为无线传感器网络中的多源单汇路由提供了一种新的有效途径.