导读:本文包含了斯坦纳树论文开题报告文献综述及选题提纲参考文献，主要关键词:分区双连通,无线传感器网络,节点移动,斯坦纳树
斯坦纳树论文文献综述
张晶,喻小惠,黄云明[1]（2019）在《斯坦纳树和凸多边形的WSN分区双连通恢复》一文中研究指出针对无线传感器网络分区在恢复连通后仍然容错不足的问题,提出斯坦纳树和凸多边形的分区双连通恢复方法.首先,以距离为依据选取现有叶子节点来促使少数未连通的离散节点统一成区;然后,将分区抽象成点后枚举出所有的非退化型四边形,进而将计算得到的四边形中的两个斯坦纳点与4个顶点连接构造斯坦纳边部署中继节点,使分区实现单连通;最后,利用格雷厄姆凸壳算法选取抽象点中的凸壳顶点连接,形成凸多边形实现分区的双连通,并对第2轮连通路径上的中继节点实施休眠唤醒机制.在保证关键节点二次失效不会使网络再次瘫痪的基础上,简化网络结构并降低数据通信延迟.通过仿真,将所提出方案与利用最小斯坦纳树优化中继节点布局的分布式算法(DORMS)和1C-SpriderWeb算法进行对比,对比结果表明所提出方案可减少中继节点的部署数量,延长网络寿命.(本文来源于《控制与决策》期刊2019年11期）
贾经纬[2]（2018）在《基于蚁群算法的并行最小斯坦纳树算法的研究》一文中研究指出最小斯坦纳树问题是图论中经典的NP-hard问题,它是诸多领域的基本问题之一。如组播路由问题在很多的研究中都被构建为最小代价组播树问题,即为最小斯坦纳树问题;超大规模集成电路的布线问题实质上也是最小斯坦纳树问题,等等。因此,对最小斯坦纳树问题的研究求解就显得尤为重要。对于NP-hard问题,解决问题所需的复杂度随着问题规模地增大而呈指数增长,人们无法保证在多项式时间内获得问题的精确解,而近似算法是在相对较低的计算成本下获得近似最优解的可行方式。蚁群算法是一种仿生学优化算法,其鲁棒性较强,具有隐含的并行搜索能力。国内外学者对于蚁群算法在最小斯坦纳树问题上的应用已经做了一定的研究,但是传统上的串行蚁群算法在速度上已经无法适应求解规模日益增大的斯坦纳树问题。因此,在蚁群算法基本原理已经明确的条件下,利用并行的平台和算法解决斯坦纳树问题是一个有潜力的研究方向。本文提出了一种蚁群优化算法来求解最小斯坦纳树,并利用局部搜索来优化求解结果。然后通过分析算法的特性,利用Gunrock图处理库对算法进行了并行化处理。蚁群算法的相关参数对算法的性能有很重要的影响,因此在对算法的测试中,本文首先通过对参数的粗调和微调分析了参数对于算法结果的影响,并给出了最优的参数组合。在最优参数组合下,对Stein Lib中用例的测试中,所有测试用例的平均解的平均误差率为1.09%,最优解的平均误差率为0.43%。对所有的测试结果,大部分结果的误差率都在2%以下,所有测试用例的结果误差率都在3.5%以内。通过与其它的蚁群算法相比较,本文提出的算法的求解质量要优于其它的蚁群算法,并且在保证近似率的情况下,本文的并行算法的求解速度比对应的串行算法平均快了1个数量级。通过与KMB算法相比较,本文提出的并行算法的求解质量比KMB算法平均提高了8%,在运行时间上比KMB算法平均快了2倍左右。(本文来源于《哈尔滨工业大学》期刊2018-06-01）
龙海明[3]（2017）在《基于GPU的近似最小斯坦纳树算法》一文中研究指出斯坦纳树问题是图论的一个经典的问题,在工业生产中具有广泛和重要的应用。传统的串行算法在速度上无法适应图规模日益增大的斯坦纳树问题。为了加速求解大规模的斯坦纳树问题,学术界开始尝试利用GPU来加速求解斯坦纳树问题。然而,目前对于GPU加速斯坦纳树问题的研究仍然较少,仍需进一步寻找适合于在GPU平台上并行求解图近似斯坦纳树问题的算法,以充分挖掘GPU的计算能力。VLSI布线设计是斯坦纳树问题的一个重要的应用方向。VLSI多端线网布线问题从数学上可抽象为斯坦纳树问题。随着集成电路规模的日渐增大,VLSI多端线网布线的图规模也在扩张。以往串行的VLSI布线算法在求解速度上逐渐跟不上工业界的需求。利用并行的平台和算法来进行VLSI多端线网布线具有很大的加速潜力。本文研究了GPU图加速框架Gunrock的基本原理,挖掘了串行求解斯坦纳树问题的Shrubbery算法中可并行加速的部分,并借助Gunrock,提出了并行度较高的Shrubbery-GPU算法。其中,并行求解向外的Voronoi diagram为Shrubbery-GPU算法的快速求解提供了重要的基础。对VLSI布线问题进行研究,抽象出VLSI多端线网布线问题的数学模型。将Shrubbery-GPU算法应用到求解VLSI多端线网布线问题。Shrubbery-GPU算法经实验证明对终端节点、顶点和边均为较大规模的斯坦纳树问题在保持与原Shrubbery相似的求解质量下取得了1至3个数量级的加速效果,并能很好地应用于VLSI多端线网布线上。更重要的是,Shrubbery-GPU算法对斯坦纳树问题的终端节点的数目不敏感,大部分测试数据在终端节点数目增大时求解时间反而呈现轻微的下降趋势。这使得Shrubbery-GPU算法的应用场景更加广泛。Shrubbery-GPU算法求得的斯坦纳树的解为近似最优,因此斯坦纳树的解仍然存在改进的空间。本文利用快速局部搜索来进一步提高Shrubbery-GPU算法的求解质量。快速局部搜索在Shrubbery-GPU算法的初始解基础上均改善了解的质量,在大规模的测试集上改善效果最为明显,代价改善了8%至12%。(本文来源于《哈尔滨工业大学》期刊2017-12-01）
王文成[4]（2017）在《平面上具有边长限制的斯坦纳树问题》一文中研究指出本文考虑平面上具有边长限制的斯坦纳树问题,其具体描述如下:在欧氏平面上给定n个终端点集合X= {r1,r2...,rn}及长度为L的材料若干,非负常数l及构建一个斯坦纳点费用c1,单位长度施工费用c2,购买单根材料费用c3。要在欧氏平面中构建一棵连结这n个终端点的斯坦纳树T,满足斯坦纳树T中每条边长度不超过l,目标是使得构建所需斯坦纳点的费用c1k1(T),施工费用c2∑e∈ET w(e)及购买材料费用c3k3(T)之和达到最小,即minT{c1k1(T)+c∑e∈ETw(e)c3fk3(T)},其中k1(T)表示构建斯坦纳树T所需斯坦纳点个数,k3(T)表示构建斯坦纳树T所需材料根数。本文设计了两个多项式时间近似算法AMST和Astar来解决该构建问题,其中算法AMST是解决该问题的4-近似算法,时间复杂度为O(n2),算法AStar是解决该问题的3-近似算法,时间复杂度为O(n3),这里n为终端点的个数。(本文来源于《云南大学》期刊2017-03-01）
杜海遥[5]（2017）在《基于斯坦纳树和粒子群算法的机电产品布线优化技术研究》一文中研究指出线缆组件的布局和装配质量直接影响机电产品的可靠性。布线设计是对线缆组件的结构和路径进行规划的过程,为提高复杂机电产品研发过程中线缆布线设计的效率与质量,本文以粒子群算法为基础,提出一种基于斯坦纳树的用于计算线缆拓扑结构及路径的智能化算法。并研究了基于Pro/Toolkit的参数化几何建模方法,实现了线缆组件的快速叁维造型,为产品全数字化样机的快速建立提供了技术途径。本文的主要工作如下:(1)提出了基于网格分割的叁维布线空间预处理技术。分析了布线算法和布线工艺约束对布线环境的要求。研究了基于产品模型的叁维布线离散空间描述方法,提出了待布线机电产品结构模型的非均匀离散化技术,包括基于模型OBB包围盒的空间网格分割面获取,以及空间离散点及其属性的获取。最终获得了表示布线环境的叁维数组。(2)研究了基于斯坦纳树和粒子群算法的布线优化方法。分析了基于斯坦纳树的布线问题,建立了基于斯坦纳树的布线问题优化模型,将布线问题转变为斯坦纳树的问题进行解决,并提出了符合布线实际的最小生成树算法。利用粒子群算法,对斯坦纳树问题进行求解,研究了粒子的初始化方式,粒子的更新和迭代方式。通过对某卫星内部进行布线,验证了所提算法的有效性。(3)研究了基于Pro/Toolkit的线缆组件参数化几何建模技术。分析了Creo环境下线缆组件的几何建模需求,给出了线缆组件参数化几何建模的流程,建立了线缆组件参数化信息模型,研究了线缆组件参数化模型的数据重构方法。然后提出了基于Pro/Toolkit的线缆组件自动几何建模方法。通过实例验证了几何建模方法的可行性。(本文来源于《南京航空航天大学》期刊2017-03-01）
李子茂,李晓丹[6]（2016）在《网格空间瓶颈斯坦纳树问题快速近似（英文）》一文中研究指出指出了瓶颈斯坦纳树问题要求寻找一棵用至多k个斯坦纳点将n个点连接起来使得此斯坦纳树之最长边最短的斯坦纳树,该问题在VLSI、无线通讯网络和生命演化树重建等领域都有应用.Du和Wang证明网格空间瓶颈斯坦纳树问题是NP-Hard,不存在近似性能比低于2的多项式时间解决方案,并且提出一个近似性能比为2的多项式时间近似算法,算法的实际时间复杂度为O(nlog2n+kn+k2).通过引入二叉堆和斐波那契堆使算法的时间复杂度分别改进到了O(nlog2n+klog2n)和摊还时间O(nlog2n+klog2n).该改进可直接应用于欧几里得平面的瓶颈斯坦纳树2-近似算法.(本文来源于《中南民族大学学报(自然科学版)》期刊2016年03期）
韩翔宇,刘涤尘,廖清芬,贾骏,朱正[7]（2016）在《斯坦纳树模型在含DG配电网规划中的应用》一文中研究指出不确定性分布式电源的接入,给配电网规划带来新的挑战。首先将含分布式电源的配电网规划归纳为求解斯坦纳树问题,提出了一种新的配电网规划建模方法。其次通过DG供电分区的划定,将分区内的负荷节点处理为一个不接DG的负荷节点,消除DG对配电网规划的影响。针对斯坦纳树问题传统解法求解时间会随着斯坦纳点的规模成倍增加的缺陷,采用一种改进的粒子群优化(PSO)算法解决斯坦纳树N-P完全问题。结合54节点算例并与传统方法计算结果比较,验证了该方法的有效性。(本文来源于《电力系统及其自动化学报》期刊2016年06期）
李晓丹[8]（2016）在《欧氏平面快速k-瓶颈斯坦纳树近似算法》一文中研究指出瓶颈k-Steiner树问题描述如下:给定n个点和一个正整数k,寻找一棵Steiner树用至多k个Steiner点将n个点连接起来,使得此Steiner树的最长边最短。L.Wang和D.-Z.Du证明了适用于欧几里得平面瓶颈斯坦纳树算法的近似性能比为2,并且给出了一个适用于该问题时间复杂度为(nlogn+kn)的算法,在欧几里得平面上和近似性能比为2的前提下,通过引入最大堆和斐波那契堆分别对该算法进行优化,优化后算法的时间复杂度分别达到(nlogn+klogn)和(nlogn+k),优化后的算法在现实中可以更好地应用。(本文来源于《电脑编程技巧与维护》期刊2016年06期）
秦宁宁,吴德恩,余颖华[9]（2016）在《基于叁角形斯坦纳树的分区连通性恢复算法》一文中研究指出无线传感器网络中的节点由于自身能量的消耗,及外部因素影响会导致节点出现大规模的失效,从而把无线传感器网络分割成几个独立的不能相互通信的分区。为恢复网络,重建分区之间的通信链路,提出基于叁角形斯坦纳树连通恢复算法。该算法首先利用传统算法实现分区连通,然后通过构建叁角形斯坦纳树以减少部署的中继节点数量。与现有的一些算法相比,该方法形成的网络拓扑不仅减少了部署中继节点的数量,能够使分区重新连通,而且能够减少网络通信的能量消耗。实验结果表明,所提方法相对于传统算法在构建网络拓扑时更加有效。(本文来源于《传感技术学报》期刊2016年03期）
李晓丹[10]（2016）在《k-瓶颈斯坦纳树快速近似算法》一文中研究指出经典斯坦纳树问题在超大规模集成电路设计、计算机网络设计、IC芯片路由、无线通讯网络规划以及重建生命演化树等多个领域都有非常重要的应用,近年来各个领域中新的应用需要对经典斯坦纳树问题进行适当修改使之更具应用价值,因此对经典斯坦纳树变种问题的研究亦具有重要的意义。目前,对经典斯坦纳树变种问题的研究主要表现在两方面,1):k-瓶颈斯坦纳树问题;2):最大边长度限定、寻找包含斯坦纳点数目最少的斯坦纳树问题。本文主要是对网格空间和欧几里得平面的k-瓶颈斯坦纳树问题进行研究,具体内容如下:(1)从斯坦纳树问题的基本理论着手,详细说明斯坦纳树问题的定义,斯坦纳树算法的实际应用,斯坦纳树的变种问题。给出L.Wang和D-Z.Du的近似性能比为2的多项式时间近似算法,并详细分析该近似算法的时间复杂度。(2)对L.Wang和D-Z.Du算法的时间复杂度进行改进。提出近似性能比为2的k-瓶颈斯坦纳树算法的优化方案,分别使用最大堆和斐波那契堆对该算法进行优化,分析优化后算法的时间复杂度,将时间复杂度由原来的O(nlogn+kn+k2)分别降低到O(nlogn+klogn)和摊还时间O(nlogn+klogn)。(3)对上述算法进行实现,当给定点集数目和斯坦纳点数目不断变化时展示新算法的高效性。最后总结本论文的主要工作,并且展望下一阶段关于斯坦纳树问题的研究重点。(本文来源于《中南民族大学》期刊2016-03-01）
斯坦纳树论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
最小斯坦纳树问题是图论中经典的NP-hard问题,它是诸多领域的基本问题之一。如组播路由问题在很多的研究中都被构建为最小代价组播树问题,即为最小斯坦纳树问题;超大规模集成电路的布线问题实质上也是最小斯坦纳树问题,等等。因此,对最小斯坦纳树问题的研究求解就显得尤为重要。对于NP-hard问题,解决问题所需的复杂度随着问题规模地增大而呈指数增长,人们无法保证在多项式时间内获得问题的精确解,而近似算法是在相对较低的计算成本下获得近似最优解的可行方式。蚁群算法是一种仿生学优化算法,其鲁棒性较强,具有隐含的并行搜索能力。国内外学者对于蚁群算法在最小斯坦纳树问题上的应用已经做了一定的研究,但是传统上的串行蚁群算法在速度上已经无法适应求解规模日益增大的斯坦纳树问题。因此,在蚁群算法基本原理已经明确的条件下,利用并行的平台和算法解决斯坦纳树问题是一个有潜力的研究方向。本文提出了一种蚁群优化算法来求解最小斯坦纳树,并利用局部搜索来优化求解结果。然后通过分析算法的特性,利用Gunrock图处理库对算法进行了并行化处理。蚁群算法的相关参数对算法的性能有很重要的影响,因此在对算法的测试中,本文首先通过对参数的粗调和微调分析了参数对于算法结果的影响,并给出了最优的参数组合。在最优参数组合下,对Stein Lib中用例的测试中,所有测试用例的平均解的平均误差率为1.09%,最优解的平均误差率为0.43%。对所有的测试结果,大部分结果的误差率都在2%以下,所有测试用例的结果误差率都在3.5%以内。通过与其它的蚁群算法相比较,本文提出的算法的求解质量要优于其它的蚁群算法,并且在保证近似率的情况下,本文的并行算法的求解速度比对应的串行算法平均快了1个数量级。通过与KMB算法相比较,本文提出的并行算法的求解质量比KMB算法平均提高了8%,在运行时间上比KMB算法平均快了2倍左右。
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
斯坦纳树论文参考文献
[1].张晶,喻小惠,黄云明.斯坦纳树和凸多边形的WSN分区双连通恢复[J].控制与决策.2019
[2].贾经纬.基于蚁群算法的并行最小斯坦纳树算法的研究[D].哈尔滨工业大学.2018
[3].龙海明.基于GPU的近似最小斯坦纳树算法[D].哈尔滨工业大学.2017
[4].王文成.平面上具有边长限制的斯坦纳树问题[D].云南大学.2017
[5].杜海遥.基于斯坦纳树和粒子群算法的机电产品布线优化技术研究[D].南京航空航天大学.2017
[6].李子茂,李晓丹.网格空间瓶颈斯坦纳树问题快速近似（英文）[J].中南民族大学学报(自然科学版).2016
[7].韩翔宇,刘涤尘,廖清芬,贾骏,朱正.斯坦纳树模型在含DG配电网规划中的应用[J].电力系统及其自动化学报.2016
[8].李晓丹.欧氏平面快速k-瓶颈斯坦纳树近似算法[J].电脑编程技巧与维护.2016
[9].秦宁宁,吴德恩,余颖华.基于叁角形斯坦纳树的分区连通性恢复算法[J].传感技术学报.2016
[10].李晓丹.k-瓶颈斯坦纳树快速近似算法[D].中南民族大学.2016