检索结果-南通市图书馆

基于二进制粒子群算法求解steiner最小树问题

在线全文

学校读者我要写书评

暂无评论

基于二进制粒子群算法求解Steiner最小树问题

作者：张娟敏兰州交通大学

学位级别：硕士

steiner最小生成树是经典组合优化的NP难问题.在现实生活中,诸多问题都可以转化为steiner最小树问题.比如:垃圾处理厂的最佳位置、用尽可能少的点来监控大型网络、无线网络节点设置问题、最佳网络物流、集成电路缺陷的修复等.目前,Stei... 详细信息

steiner最小生成树是经典组合优化的NP难问题.在现实生活中,诸多问题都可以转化为steiner最小树问题.比如:垃圾处理厂的最佳位置、用尽可能少的点来监控大型网络、无线网络节点设置问题、最佳网络物流、集成电路缺陷的修复等.目前,steiner最小树问题的应用已经有较大的发展,主要是使用蚁群算法、遗传算法、粒子群算法、模拟退火算法等来解决steiner最小树问题,但是,基于二进制粒子群算法和遗传算法、二进制粒子群算法和聚类算法求解此问题的研究较少.因此,将这些算法相结合求解steiner最小树问题具有一定的研究意义.论文主要引入了二进制粒子群算法、遗传算法和k-means聚类算法,在这三种算法结合的基础上,将网络电缆铺设的具体问题转化为steiner最小树问题进行求解,得到实际问题的最优解,证明了其实用性和有效性,验证了此算法是可行的.论文的主要研究内容如下:(1)对基于各类算法求解的steiner最小生成树(主要研究绝对值距离steiner最小生成树)问题进行了现状分析,叙述了论文的研究内容,目的及意义,并且梳理了最小生成树和最小steiner生成树的相关概念及性质,阐述了二进制粒子群算法、蚁群算法和聚类算法的基本步骤和流程.(2)将二进制粒子群算法和遗传算法相结合应用于steiner最小生成树问题.首先,在二进制粒子群算法中,速度更新与基本的粒子群算法相似,位置更新则是引入Sigmoid函数;其次,粒子的选择和编码则是把矩形区域放缩在[0,1]?[0,1]的单位面积正方形上,将矩形区域内任意一点的横坐标和纵坐标放缩,计算出编码的长度和适应度函数;最后,利用二进制粒子群算法为steiner最小生成树问题设计算法程序,通过实例证明此算法是可行的.在此基础上引入k-means聚类算法,先对数据点进行聚类分析,然后在每类中找到最佳的steiner点,再通过反复迭代,最终找到最优的绝对值距离steiner最小生成树和steiner点,通过实例说明了这两种算法相结合是可以实施的.(3)根据已知数据,分别减少或增加点的个数,将已知点数进行调整,然后确定steiner点的个数,最后得到计算结果,并计算出steiner比.将两种不同算法steiner比进行比较,通过图像对比两种解法可以发现,第二种将聚类算法和二进制粒子群算法结合起来得到的steiner最小树更佳,而且稳定性更强,应用于解决绝对值steiner最小树问题更合理.

关键词： steiner最小树组合优化二进制粒子群算法聚类

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

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

煤炭学报 2015年第3期40卷 541-547页

作者：薛东杰周宏伟任伟光栗东平中国矿业大学(北京)力学与建筑工程学院北京100083

采矿工程中上覆岩层裂纹扩展及其分布规律一直是研究的难点,直接影响井下工作高效开展及安全,对于高瓦斯矿井还涉及到瓦斯抽采效率提高问题。基于steiner最小树模型建立裂纹拓展与能量传播的关系,指出裂纹的贯通拓展是沿着耗能最小而最... 详细信息

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

关键词：上覆岩层裂纹 steiner最小树能量最优路径

考虑布线资源松弛的X结构steiner最小树算法

在线全文

学校读者我要写书评

暂无评论

模式识别与人工智能 2020年第5期33卷 401-412页

作者：汤浩刘耿耿郭文忠陈国龙福州大学数学与计算机科学学院福州350116 福州大学福建省网络计算与智能信息处理重点实验室福州350116 福州大学空间数据挖掘与信息共享教育部重点实验室福州350108

为了进一步考虑X结构,并充分利用障碍内可用布线资源,文中提出考虑布线资源松弛的X结构steiner最小树算法.为了能够求解离散问题,在粒子的更新操作中引入交叉算子和变异算子.通过构建查找表,为整个算法流程提供快速的信息查询.提出角点... 详细信息

为了进一步考虑X结构,并充分利用障碍内可用布线资源,文中提出考虑布线资源松弛的X结构steiner最小树算法.为了能够求解离散问题,在粒子的更新操作中引入交叉算子和变异算子.通过构建查找表,为整个算法流程提供快速的信息查询.提出角点选取策略,通过引入一些障碍角点,使粒子满足约束.最后构建精炼策略,进一步提高最终布线树的质量.实验表明,文中算法充分利用障碍内可用布线资源,有效缩短总布线长度,取得较佳的总布线长度.

关键词： steiner最小树 X结构布线粒子群优化角点选取精炼策略

在线全文

学校读者我要写书评

暂无评论

steiner最小树问题及其应用

科学技术与工程 2008年第15期8卷 4238-4245,4257页

作者：张瑾马良上海理工大学管理学院

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

关键词： steiner最小树精确算法启发式算法应用

基于高维空间典型样本steiner最小树覆盖模型的一类分类算法

在线全文

学校读者我要写书评

暂无评论

信号处理 2011年第6期27卷 874-882页

作者：胡正平路亮许成谦燕山大学信息科学与工程学院秦皇岛066004

最小生成树数据描述方法在刻画高维空间样本点分布时,将所有图形的边作为新增虚拟样本以提供同类样本分布描述,这种描述存在分支多覆盖模型复杂,且局部覆盖不够合理的问题。针对该问题,依据特征空间中同类样本分布的连续性规律,提出基... 详细信息

最小生成树数据描述方法在刻画高维空间样本点分布时,将所有图形的边作为新增虚拟样本以提供同类样本分布描述,这种描述存在分支多覆盖模型复杂,且局部覆盖不够合理的问题。针对该问题,依据特征空间中同类样本分布的连续性规律,提出基于高维空间典型样本steiner最小树覆盖模型的一类分类算法,该算法首先对目标类训练集进行样本修剪,去除冗余信息和噪声信息,选择最具代表性的样本作为训练集,然后对保留的典型样本构建steiner最小树覆盖模型。算法分析和仿真实验结果表明,相比最小生成树数据描述,文中提出的方法能在较低覆盖模型复杂度的前提下更合理的描述目标类样本空间分布,构建更合理的覆盖模型,在分类正确率和适用样本规模上都表现出一定的优越性。

关键词：一类分类器高维空间最小生成树 steiner最小树

在线全文

学校读者我要写书评

暂无评论

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

上海理工大学学报 2012年第5期34卷 461-465页

作者：熊小华刘艳芳宁爱兵上海第二工业大学计算机与信息学院上海201209 上海理工大学管理学院上海200093

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

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

关键词：竞争决策算法 steiner最小树图降阶

系列平行图上带时间约束的steiner最小树问题

在线全文

学校读者我要写书评

暂无评论

高校应用数学学报（A辑） 2008年第1期23卷 30-34页

作者：陈光亭杭州电子科技大学运筹与控制研究所浙江杭州310018

对一类特殊系列平行图上带有时间约束的steiner最小树问题,证明了其复杂性为NPC,并给出了一个完全多项式时间近似方案.

关键词： steiner最小树系列平行图多项式时间近似方案

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

在线全文

学校读者我要写书评

暂无评论

测绘信息与工程 2008年第3期33卷 17-18页

作者：夏兰芳胡鹏白轶多武汉大学资源与环境科学学院武汉市珞喻路129号430079 武汉大学地理信息系统教育部重点实验室

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

关键词： Delaunay三角网最小生成树 steiner最小树完全steiner树

在线全文

学校读者我要写书评

暂无评论

图的steiner最小树构建及其布线应用

图的Steiner最小树构建及其布线应用

作者：董君复旦大学

学位级别：硕士

随着集成电路工艺制造技术的迅速发展,芯片的特征尺寸不断减少,互连线的结构变得越来越复杂。互连线的RC延时已经成为了芯片的主要延时,极大地影响着芯片的性能。针对传统的Manhattan互连结构受限于布线走向只能水平、竖直两个方向、无... 详细信息

随着集成电路工艺制造技术的迅速发展,芯片的特征尺寸不断减少,互连线的结构变得越来越复杂。互连线的RC延时已经成为了芯片的主要延时,极大地影响着芯片的性能。针对传统的Manhattan互连结构受限于布线走向只能水平、竖直两个方向、无法充分利用布线空间资源而造成互连线的延时难以被进一步优化,产生了一系列新型的非直角的互连结构,尤其是X互连结构因其减少线长的潜力而引起了广泛的研究兴趣。本文主要研究X互连结构的快速启发式的布线算法,将实际非常复杂的X互连结构的布线问题简化为构建绕过障碍物的八叉steiner最小树(OAOSMT)的计算几何问题。通过研究学习国内外相关学术成果,本文提出了构建图的steiner最小树(GSMT)的新启发式算法,并运用该算法和几类简单的几何变换来实现绕过障碍物的八叉steiner最小树的构建。针对经典的图的steiner最小树问题,本文提出了包含四步骤的新启发式算法。首先对原始输入图进行连通子图的分解并简化,来减少求解问题的规模。然后在每个连通子图中按照三源最短路径扩展的思想来构建steiner树。接着利用steiner点插入和边变换的操作来进一步优化连通子图的steiner树。最后,合并各个子图中的steiner树来获得原始图完整的steiner最小树。实验结果表明,该算法相比传统的GSMT启发式算法,能获得更高质量的steiner树,67%的测试例子获得的steiner树跟最优steiner树相比误差不超过1%。本文将此GSMT的求解方法应用到X型互连结构的布线问题中,提出了构建绕过障碍物的八叉steiner最小树(OAOSMT)的新启发式算法。首先引入改进型Escape图的概念,然后将构建绕过障碍物的直角steiner最小树问题(OARSMT)转化为改进型Escape图的GSMT问题并求解。最后在OARSMT的基础上,引入了5类简单的几何变换来快速得到用于X型互连结构的OAOSMT。实验结果表明,本文提出的构建OAOSMT的新启发式算法,获得的OAOSMT相比OARSMT,总线长能减少8%～17%,初步验证了X型互连结构减少线长的潜力。

关键词： X互连结构布线算法 steiner最小树几何变换