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

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

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

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

基于遗传算法的通讯网络最佳Steiner树构造

提出了一种解决Steiner最小树问题的自适应遗传算法,将Steiner最小树问题转化成一个组合优化问题,并对部分初始种群的构造给出了一种试探选择方法.通过对通讯网络Steiner最小树问题的实例仿真分析,表明算法能有效地跳出局部极小值并快速地收敛于全局最优值.将其推广到考虑建站费用的极小树问题上,取得了很好的近似解.     

针对VLSI布线的多层X结构斯坦纳最小树构建算法

考虑到粒子群优化算法具有非常出色的全局优化能力,针对X结构布线问题的复杂性提出了X结构下的多层Steiner最小树构建算法.实验结果表明,该算法可以在合理的时间内取得优异的布线解.     

Steiner最小树问题及其应用

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

一类平面折线图的Steiner最小树

本文介绍了Steiner问题中的主要课题,特别是在特殊的平面点集上构造Steiner最小树的研究的主要结果。对本人在一类平面拆线图上构造Steiner最小树方面的一些工作做了介绍与总结。     

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

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

K度Steiner问题

给定平面上n个固定点 (称为正则点 )的集合N和m =n - 2k- 2 个可动点 (称为Steiner点 )的集合M ,其中k( 3≤k≤n)是确定的正整数 要求互联点集V =N∪M的网络的拓扑在正则点的度为 1 ,Steiner点的度不超过k ,这种网络称为k度网络 确定m个Steiner点的位置 ,使互联这n m个点的k度网络总长度最短 显然这个最短的k度网络一定是树 ,我们称这个树为k度Steiner最小树 (kDSMT) ,并称这个问题为k度Steiner问题 本文得到了kDSMT的一些结构特征 ,并提出了一些有待进一步研究的问题     

改进的时延约束Steiner树算法

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

一种基于最小路径的多播路由优化算法

信息物理融合系统(Cyber-Physical Systems,CPS)底层是传感器、控制器和执行器等异构节点构成的无线自组网络,不同节点之间需要通过通信网络传送给感兴趣目标节点,传统的无线自组织网络一般采用单播或广播技术,但是这些往往实时性不高,通信开销大,不利于在CPS中受限节点间通信.该文针对信息物理融合系统中无线多播路由问题构建网络模型,演化为最小路径问题,数学模型为约束Steiner最小树问题,并针对该NP难问题通过启发式算法求解,再通过贪婪思想构建一种最小路径多播路由算法.最后通过与uCast以及SenCast等经典的多播路由算法仿真比较,得出其算法在实时性以及能耗等方面性能优异.     

基于Logistic回归模型和凝聚函数的多示例学习算法

实时多媒体网络中,带延迟与延迟抖动约束的斯坦利树问题是一个研究热点.这种带约束的斯坦利树被证明是NP-完全问题.提出了一种基于禁忌搜索的带延迟与延迟抖动约束最小代价组播路由算法.实验结果表明,该算法对于实际网络是有效的.这种方法使得IP组播把数据同时发送到组成员时有效地利用了网络资源.

Abstract：

The delay and delay variation-bounded Steiner tree problem is animportant multicast routing issue in real-time multimedia networks.Such a constrained Steiner tree problem is known to be NP-complete.A multicast routing algorithm is presented,which is based on tabu search to produce routing trees having a minimal network cost under delay and delay variation constraints.The approach makes IP multicast utilize resources efficiently in delivering data to a group of members simultaneously.     

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

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

最短路算法(dijstra算法)的研究

Dijstra标号算法是求从一点到网络其它各点之间最短路的重要算法,而最小生成树是求网络各点之间相互连接的整体代价最小的算法,两者之间算法过程以及思路都不同。然而,本文对这两个算法进行研究,发现这两种算法的本质是一致的。接着对算法进行推广,一种综合算法,并应用到组播路径构造上,经对许多事例分析,发现该算法不仅很好地解决了无约束组播和有时延约束组播的近似最优解的问题,同时对部分有时延和时延抖动组合约束问题也能进行快速求解,且复杂度不超过O(kmn2)。     

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

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

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

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

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

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

E^n空间中Steiner树的性质与极值

将平面上名的Steiner树问题推广到n维欧氏空间E^n中，得到了单形中Steiner点的一些重要性质以及一些加权几何不等式。     

求解满瓶颈Steiner树

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