单圈图的Steiner k-general Wiener指数

对于连通图G,当3≤k≤n-2时,图G的Steiner k-general Wiener指数定义为SW_(k)^(m)(G)=∑S■V(G)|S|=kd^(m)(S),(m≥1),其中d(S)表示点集S的Steiner距离,即图G中包含点集S的最小连通子树的边数.给出了单圈图的SW_(k)^(m)(G)下界,并得到对应的极图.

广义欧几里德Steiner问题的研究与进展

广义欧几里德Steiner问题是指确定连接平面上一组给定点的满足特定连通性要求的最短网络的问题。本文主要介绍了此问题的研究与进展,在建立了求给定平面点集的最短U-连通(或边连通)生成网络的整数规划模型的基础上,证明了文献[13]中所给的一个例子是错误的,并提出了一些关于广义Steiner问题的进一步研究的问题。

奖励-收集Steiner树问题的精确算法

奖励-收集Steiner树问题是图的Steiner最小树问题的衍生,同时也是组合优化中的NP-hard问题。首先,提出该问题的数学性质并给出证明,利用数学性质能降低该问题的规模;其次,基于该问题的数学性质设计出上下界子算法、降阶子算法和回溯子算法,通过上下界子算法和降阶子算法可以降低该问题解空间的规模,从而缩短回溯子算法的搜索时间,进而降低求解该问题最优解的时间;最后,应用案例分析、算例分析以及算法分析与对比表明,所设计的算法不仅可以求出该问题的最优解,而且比没有考虑该问题数学性质的一般回溯算法的时间复杂度更低。

Steiner树优化问题的算法研究综述

最优Steiner树问题(Steiner tree problem,STP)是一个经典的组合优化问题,许多工程问题都可以归结为最优Steiner树问题。STP被广泛应用于通信网络、电路设计、VLSI设计等领域。然而,STP是典型的NP难问题,还没有多项式时间的精确算法求解该问题。目前,求解该问题的算法主要集中在基于启发式的近似算法、智能优化算法、信息传播算法等,并取得了很好的效果。在不同规模的网络中,基于传统遗传算法给出一种叶交叉机制(leaf crossover,LC),使用该机制的算法性能表现更好。通过对这些算法的原理、性能、精度等方面进行梳理,归纳出算法的优缺点,并指出STP的研究方向和算法设计路径,对于相关问题的研究有指导意义。

基于动态粒子群优化的X结构Steiner最小树算法

Steiner最小树(SMT)是总体布线的最佳连接模型,其构造是1个NP-难问题。粒子群优化(PSO)算法在解决NP-难问题中具有良好的表现,而PSO算法中种群的拓扑结构及搜索信息的传递机制对其性能有着很大的影响。1个适用于具体问题的种群拓扑结构对算法性能的提升极为显著。因此,利用PSO求解总体布线问题需要根据具体布线问题的特性来选择合适的粒子拓扑结构策略,以提升PSO的性能。提出基于动态PSO的X结构Steiner最小树(XSMT)算法以解决总体布线问题。首先,设计动态子群与信息交换策略,对种群进行子群划分,引入信息交换的概念,让子群在保持独立性的同时与其他子群进行信息交换,增加子群多样性;其次,设计粒子学习与变异策略,通过设置子群中粒子的学习对象使子群趋向于全局最优,并选择每个子群中适应度值最好的粒子进行变异,使粒子更易于跳出局部最优;最后,设计从多群局部学习过渡到单群全局学习策略,使算法在迭代次数到达阈值之后从局部学习过渡到全局学习,使得粒子在较优拓扑结构的基础上内部连接以获得更好的线长优化率。实验结果表明,与现有的2种R结构SMT(RSMT)算法相比,所提算法在优化线长方面分别优化了10.25%、8.24%;与现有的3种XSMT算法相比,该算法在优化线长方面分别优化了2.44%、1.46%、0.48%,验证了算法的有效性。

域上Steiner扩张的代数性质(英文)

讨论了Steiner列的结构 ,得到了Steiner扩张的一些性质 ,并推出每个Steiner列 {sn}中 ,任意圆是可以尺规作出的。

区传递Steiner t-设计与散在单群

研究具有某种高度对称性的t-设计及其自同构群的分类问题是代数组合学的重要课题之一。目前关于旗传递Steiner t-设计的分类问题已被Huber解决。然而当设计的自同构群的旗传递性减弱为区传递时,研究结果更加丰富,工作也更加困难。利用有限单群分类定理及2-传递置换群的分类结果,解决了自同构群为散在单群的区传递Steiner t-设计的分类问题,并证明了:设D=(P,E)为非平凡Steiner t-设计且G≤Aut(D)为点本原群,若G的基柱Soc(G)为散在单群,则G区传递作用在D上当且仅当G旗传递作用在D上,且D为已知的5种旗传递Steiner t-设计之一。

圈C_n的k-Steiner Wiener指数和超k-Steiner Wiener指数

点集S的Steiner距离d(S)是指包含子集S的最小连通子图的边数即d(S)=min{|E(H)|:S■V(H),H是G的连通子图}.2016年,李学良,毛亚平和Gutman提出了k-Steiner Wiener指数SW k(G)和超k-Steiner Wiener指数SWW k(G)的概念,SW k(G)=∑S■V(G),|S|=k d(S)SWWk(G)=1/2∑S■V(G),|S|=k d(S)+1/2∑S■V(G),|S|=k d(S)2.文章利用k-Hosoya多项式给出了圈C n的k-Steiner Wiener指数和超k-Steiner Wiener指数.

已知拓扑下的4度Steiner树算法

设Ｎ为平面上２ｎ个固定点的集合，Ｍ为ｎ－２个可动点的集合，Ｅ为连接这些点的边的集合（也称作拓扑）．设Ｅ为点集Ｖ上的满４度Ｓｔｅｉｎｅｒ拓扑（满Ｓｔｅｉｎｅｒ拓扑也就是满足固定点的度为１，可动点的度为４的树的拓扑），Ｈ（Ｅ）为包含Ｅ在内的所有Ｅ的退化拓扑的集合．文中构造了计算拓扑属于Ｈ（Ｅ）的４度Ｓｔｅｉｎｅｒ树算法，并证明了算法的时间复杂性是Ｏ（ｎ２）．

基于最小生成树的Steiner最小树生成算法

提出了基于最小生成树的Steiner最小树的生成算法,分析了该算法的时间复杂性为O(nlogn)。

约束Steiner最小树问题

本文首先提出了一个约束Ｓｔｅｉｎｅｒ最小树问题，设欧氏平面上直线Ｌ的一侧有ｎ个点，记点集为Ｎ，现要在Ｌ上找一点Ｐ，使关于Ｎ∪（Ｐ）的Ｓｔｅｉｎｅｒ树长度最小，文章解决了ｎ＝２及ｎ＝３的情形。

带圆周约束的Steiner树问题

本文首先考虑了带圆周约束的Ｓｔｅｉｎｅｒ树问题．设欧氏平面上有一圆，平面上有ｎ个点，所成点集为Ｎ，该问题是要在圆周上找一点Ｐ，使Ｎ∪｛Ｐ｝这ｎ＋１个点的Ｓｔｅｉｎｅｒ树之长度达到最短．本文对于ｎ＝２的情形给出解．另一方面，鉴于问题的复杂性为ＮＰ－Ｃ，作者提出了一个近似解，并证明了近似解的性能比为３／２．

关于对偶Steiner多项式的根的注记

受凸体的Steiner多项式的启发,定义了星体的对偶Steiner多项式,并利用对偶Aleksandrov-Fenchel不等式讨论了对偶Steiner多项式的根.进而,得到了关于对偶Steiner多项式的根的一些不等式,这些不等式恰好是关于Steiner多项式的根的不等式的对偶形式.

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

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

λ5-geometry中的Steiner树问题( )

首先研究了λ5-geometry中4个点的Steiner最小树的某些特性,然后证明了对于λ5-geometry中的给定点集P,必有P的一个Steiner最小树,其Stein-er点在P的前2n/3代格点中.

若干情形分组和覆盖Steiner问题的算法

综合论述了理论计算机科学领域中两个密切相关的NP-困难问题:分组Steiner问题和覆盖Steiner问题的不同解决途径,并就其若干特殊情形设计了近似比更好的近似算法。

Steiner三元系与拟群

对Steiner三元系的同构问题进行讨论,定义了Steiner循环有序三元系,并对Steiner循环有序三元系的存在性及其与拟群代数结构的关系等问题进行了研究.

斯坦纳(Steiner)比猜想

17世纪初,法国数学家费尔马(Fermat)曾提出一个有趣的几何问题: 求平面上一点至给定三角形三顶点距离和最小。 这个问题后由麦森(Mersenne)带到意大利。 1640年前后,对于已给三角形三内角皆小于120°的情形。

完全二部图的超k-Steiner Wiener指数

文章利用Hosoya多项式和组合恒等式给出了完全二部图Km,n的超k-Steiner Wiener指数的计算公式.

欧氏Steiner最小树问题的智能优化算法

欧氏平面内连接固定原点的最小树长问题,即欧氏Steiner最小树问题,为组合优化中的NP难题,因此合理的方法是寻找启发式算法。该文给出了两种智能优化算法——模拟退火法和蚂蚁算法。首先概述智能优化算法并将平面划分成网格,然后分别介绍两种算法的原理及实现过程,最后通过一系列计算实验,测试了算法的运行性能,获得了较好的效果。