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

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

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

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

Creative Activity and the Development of Consciousness:A Discussion With Piaget and Rudolf Steiner

This study aims to discuss the possibility of becoming conscious of certain aspects of one’s own existence through creative activity.The discussion involves Piagetian constructivism and Steiner’s ideas about human development and is justified by the contribution of creative activity to the development of autonomy,according to Piaget,and to the development of an ethical individuality,according to Steiner.The participation of adults in sessions of creative process,as well as the questions posed after this activity,asking for the relationships between what they created and their life,is evidence of practices favourable to increasing the grasping of consciousness of self and of the process of developing an ethical individuality.

基于动态粒子群优化的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 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-设计之一。

单圈图的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最小树问题,为组合优化中的NP难题,因此合理的方法是寻找启发式算法。该文给出了两种智能优化算法——模拟退火法和蚂蚁算法。首先概述智能优化算法并将平面划分成网格,然后分别介绍两种算法的原理及实现过程,最后通过一系列计算实验,测试了算法的运行性能,获得了较好的效果。

基于Steiner树的层次型无线传感器网络安全组播协议

在基于查询的无线传感器网络中,组播技术的应用可大幅减少传感器节点的能量消耗,延长节点寿命。针对大型无线传感器网络组播协议性能不高,且易遭受攻击等问题,提出了基于Steiner树的层次型无线传感器网络安全组播协议。该协议主要运用Steiner树与分簇网络的思想,将Steiner树的高效性与簇的高扩展性相结合,提高了无线传感器网络组播效率,均衡了网络能量消耗,延长了网络生命周期,并在此基础上加入安全通信机制,以抵御各种网络攻击并确保组播数据的安全性、完整性与可验证性。最后通过理论证明及模拟实验表明本协议适用于大规模无线传感器网络,具有较低能耗及较高安全性。

基于自适应PSO和混合转换策略的X结构Steiner最小树算法

X结构Steiner最小树(XSMT)是非曼哈顿结构总体布线算法中多端线网的最佳连接模型,属于NP难问题.文中基于混合转换策略和自适应粒子群优化算法,提出XSMT构造算法.首先设计有效的混合转换策略,扩大算法寻优空间,提高算法收敛效率.为了满足粒子编码的健全性,算法的更新方式引入带并查集策略的交叉和变异算子,同时采取自适应调整学习因子的策略,加快粒子群优化算法的收敛速度.实验表明,文中算法能得到较好的XSMT求解方案,获得多种不同拓扑的XSMTs,有利于VLSI总体布线阶段的拥挤度优化.

延边地区朝鲜族正常成人Steiner分析法正常值的建立

目的建立中国延边地区朝鲜族正常成人Steiner分析法的正常值。方法选择72名延边地区朝鲜族正常成人拍摄正中位X线头颅定位侧位片,应用华正头影测量系统得出Steiner分析法的数据。将延边地区朝鲜族正常成人Steiner分析法的测量均值与韩国首尔同年龄组正常成人Steiner分析法测量均值进行比较。结果1)建立了延边地区朝鲜族正常成人头影测量的Steiner分析法的正常值、标准差和臂章分析图值。2)在测量项目中,只有1-NB角和GoGn-SN角存在性别上的差异,1-NB角男大于女,GoGn-SN角女大于男(P<0.05)。3)延边地区朝鲜族与韩国正常成人相比,除Po-NB和女性1-NB角两项指标无统计学差异外,其余测量指标均有统计学差异(P<0.05)。结论延边地区朝鲜族正常成人牙颌颅面结构具有性别差异和地区特点。

Steiner Tree问题的研究进展

Steiner树问题是经典的NP难解问题,在计算机网络布局、电路设计以及生物网络等领域都有很多应用。随着参数计算理论的发展,已经证明了无向图和有向图中的Steiner树问题都是固定参数可解的(FPT)。介绍了无向图和有向图中Steiner树问题的近似算法和参数算法,分析了一些特殊Steiner树问题的研究现状,还讨论了顶点加权Steiner树问题的研究进展。最后,提出了该问题的进一步研究方向。

欧氏Steiner最优树的快速算法

针对欧氏平面内连接固定原点的最小树长问题,即欧氏Steiner最优树问题,给出了插入算法、递增优化算法、遗传算法等三种快速算法,并在微机上予以实现。经大量实例测试和结果比较,获得了满意的效果。

一种改进的Steiner树启发式算法

最小Steiner树问题是NP完全问题,关于Steiner问题的启发式算法的研究具有重要理论和实际意义。本文在 MPH算法的基础上,对于经过某些关键节点的短路径优先考虑,提出了KBMPH算法,从而实现更多链路的共享。在随机网络上的仿真结果表明,极大多数情况下,在准Steiner树的网络费用上KBMPH算法优于MPH算法,KBMPH算法的复杂度为)(3nO。

Manhattan空间有障碍的最短路径和3-Steiner树算法

在VLSI设计中,多点互连是物理设计阶段的关键问题之一,而互连的点数等于2或大于2分别对应于Manhattan空间上有障碍时的最短路径问题和最小Steiner树问题,显然前者是后者的基础.连接图是研究最短路径问题的有效工具,已有的典型连接图包括基于轨迹的GC和GT以及基于自由区的GF和GG.工作包括3个方面:设计并分析了在各种连接图上实现动态的点对之间的最短路径查询算法;分析了在各个连接图上构造3-Steiner树的算法,对于已有的GC上的3-Steiner算法,将其Steiner顶点的候选集合规模从O((e+p)2)降低到了O((t+p)2),其中e,t,p分别表示边数、障碍极边数和顶点数;设计了在GG上的3-Steiner树构造算法,其平均情况时间复杂度只有Q(t).

基于虚拟Steiner树的无线传感器网络组播随机路由协议研究

针对基于树的组播路由协议中组播树鲁棒性不好,扩展能力差的特点,又结合无线传感器网络自身能量、计算、存储能力有限的特点,提出了基于虚拟Steiner树的组播随机路由协议VMRRP(Virtual-steiner-tree based Multicast Random Routing Protocol)。该协议的随机路由思想,使得组播树中源节点到各个组成员节点的路径是动态变化的,与GMP(Geographic Multicast Routing)协议相比,增加了组播树的鲁棒性,也均衡了网络能量,增加了网络生命周期,并通过NS-2仿真试验得到了验证。

基于MPH的时延约束Steiner树算法

为了在时延约束条件下进一步优化组播树代价,并降低算法计算复杂度,研究了时延受限的Steiner树问题.分析了MPH(minimum path heuristic)算法的计算复杂度;在此基础上设计了一个时延约束Steiner树算法DCMPH(delay-constrained MPH)用于构造时延约束最小代价组播树.该算法中每个目的结点通过与当前组播树有最小代价的路径加入组播树;若时延不满足要求,则通过合并最小时延SPT(shortest path tree)树进而产生一个满足时延约束的最小代价组播树.仿真实验表明,DCMPH算法生成的组播树在保证时延要求的情况下,与同类算法相比取得了很好的代价性能和较低的计算复杂度.

基于Steiner最小树相似模拟裂纹扩展与能量传播的机理

采矿工程中上覆岩层裂纹扩展及其分布规律一直是研究的难点,直接影响井下工作高效开展及安全,对于高瓦斯矿井还涉及到瓦斯抽采效率提高问题。基于Steiner最小树模型建立裂纹拓展与能量传播的关系,指出裂纹的贯通拓展是沿着耗能最小而最快释放能量的路径。并建立相似模型试验中的真实裂隙与数学裂隙模型,将问题定义为约束型的Steiner树问题。覆岩破坏形式遵循基于四点以离层裂隙为主导的模型。进一步开展室内三轴加载试验,表明理论和真实破裂角与赋存深度的关系并不明显。从力学机理上分析,局部岩石的破坏面可以由摩尔库仑准则解释,而从能量角度分析,众多不同岩性破裂面组合而成的路径也是最优路径。最后揭示了岩层移动角公式参数的内在涵义,指出修正公式是煤炭地下开采上覆不同部分岩层裂隙拓展的有机统一,是Steiner最小树原理的直接体现。

基于最优加权Steiner树的枢纽型物流中心选址问题

为了满足近年来物流运输业快速发展的需要,促进物流中转运输网络的合理化建设,研究了枢纽型物流中心的功能和选址原则,详细分析了影响枢纽型物流中心选址的各种因素,提出了基于结点带权的欧氏Steiner最优树的枢纽型物流中心选址方案。针对该方案设计了相应的智能优化算法,并进行了具体的程序实现。借助该方案不仅可以使总的运输成本最小,而且能够在无需事先确定备选点的数量和位置的情况下实现同时确定枢纽型物流中心的数量及位置的目标。最后以长三角地区枢纽型物流中心的建设问题为背景,对各种数据进行了仔细的分析比较,从中确定若干区域作为物流服务需求点集,并将各种因素的综合效用作为物流需求点的权值,对上述算法进行了有效性验证。

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

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

基于混合离散粒子群优化的Slew约束下X结构Steiner最小树算法

Steiner最小树是超大规模集成电路中布线阶段的最佳模型,进一步考虑能够有效防止信号失真的电压转换速率(Slew)约束这一个更为贴近实际芯片设计模型和更具线长优化能力的X结构,首次提出基于混合离散粒子群优化的Slew约束下X结构Steiner最小树算法.首先,为了避免频繁的Slew约束计算,提出了高效的预处理策略,并且提出一种能够有效考虑Slew约束的针对性的惩罚机制.其次,为了能够有效求解该离散问题,基于遗传算子重新设计了粒子群优化算法的离散更新机制,并提出一种更适合遗传算子的引脚对编码方式.然后,为了进一步优化布线树的长度,提出一种有效的精炼策略.最终,提出一种混合修正策略以完全满足Slew约束.实验表明,所提算法可完全满足电压转换速率约束并取得同类工作中最佳的布线结果.