【摘 要】
：
经典斯坦纳树问题在超大规模集成电路设计、计算机网络设计、IC芯片路由、无线通讯网络规划以及重建生命演化树等多个领域都有非常重要的应用,近年来各个领域中新的应用需要
论文部分内容阅读
经典斯坦纳树问题在超大规模集成电路设计、计算机网络设计、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)对上述算法进行实现,当给定点集数目和斯坦纳点数目不断变化时展示新算法的高效性。最后总结本论文的主要工作,并且展望下一阶段关于斯坦纳树问题的研究重点。
其他文献
在中国经济高速发展和人民日益提高的物资生活水平下,人们消费水平的提高和对产品的高追求迫使企业不得不对产业进行升级,早期传统行业过多的投入和转型的困境使生产与当前的
目前我国正处于新常态下的“转型期”,各行业面临着新的机遇和挑战。私募证券基金,是我国资本市场上的一股新生力量。笔者在工作中发现,很多私募基金存在着战略管理问题,本文
在最近的近十年里,很多发展中国家致力于促进智能电网的建设与发展。应用智能电网相比传统电网,可以通过用户用电行为辨识算法来判断用户的用电模式并进行分类,对实现需求响应和电价制定具有重要意义。针对K均值算法中用电数据特征选取策略问题,本文提出了一种考虑特征间相关关系的迭代型特征优选策略。首先基于DBI指标对不同特征组合下的K均值聚类效果来作为特征选取的标准;然后,建立特征优选模型,通过实验将备选特征优
随着互联网相关技术的快速发展,在以微博、淘宝等为代表的新型自媒体上,用户自由地在网络平台上表述自己的观点。评论观点不仅是用户选购产品或讨论时事的参考依据,也是收集
最近几年,随着物联网(Internet of Things,IoT)快速的进入到各个行业中,传感器网络(Wireless Sensor Networks,WSNs)作为IoT发展的一个重要推动者,基本都是依靠电池充电的,但
随着社会经济飞速发展,我国各项基础设施建设一路高歌猛进,产值规模不断扩张,但是建筑施工安全管理方面自动化程度仍然较低,施工现场脚手架和施工人员状态实时监测、风险状态评价和信息综合管理困难。因此,研发集现场检测设备和智能风险监测软件于一体的施工现场智能网联监测系统具有重要现实意义。论文在对建筑工程施工安全管理的研究基础上,通过施工现场风险源辨识,构建脚手架及施工人员风险评价指标体系,并设计出一套基于
社会治理是实现社会稳定运行的方式方法和动态过程。社会治理伴随着人类社会的产生而出现,随着社会的发展而发展。无论是古代社会、亚细亚社会还是殖民社会,亦或是市民社会,
组合优化领域最经典的NP-困难问题之一,点覆盖问题,它指的是用最少的点来覆盖图中的所有的边.后来,在2010年Bresar等人对此问题进行了推广,提出了 k-路点覆盖问题(MVCPk),即
党的十八大以来,以习近平总书记为核心的党中央越来越重视我国足球事业的发展,2015年教育部首次在“国培计划”中添加“校园足球骨干教师国家级专项培训”这一子项目,力图通过国家层面的培训帮助中小学体育教师提高足球教学能力,促进校园足球的发展。自培训实施以来,培训效果不佳的情况日益凸显。问题的出现吸引了专家学者的关注,但关于校园足球骨干教师培训的系统性研究到目前为止依然稀缺,大多数学者只是将校园足球骨干
开发人员和其他涉众在软件开发过程中需要不断对需求、环境、设计等做出各种假设。然而,这些假设条件通常是隐式的且未被记录,导致开发人员常常忽略软件开发中已提出和制定的假设条件。同样的信息在某种环境下可能是假设条件,而在另一环境下可能是完全不同类型的制品。除非涉众以特定方式明确表达假设条件信息,否则难以在不了解上下文的情况下判断该信息是否是假设条件。因此,缺乏使用哪些术语和语言模式来表达假设条件的相关知