矩形Steiner最小树布线灵活度

矩形Steiner最小树(RSMT)的布线灵活度影响其结构变形能力,直接影响芯片布线的收敛性.文中从树边形态、结构固有变形和拓扑变形3方面对线网的RSMT的布线灵活度进行刻画,给出了更能反映RSMT结构变形能力的计算模型.针对布线灵活度的"瓶颈"问题,提出了拥挤驱动的RSMT布线灵活度挖掘算法:根据树形的最短布线路径布线可能情况,定义了树边的布线灵活度;进而考虑RSMT结构中所有树边布线灵活度的组合情况和RSMT拓扑的变形性,得到RSMT布线灵活度.实验结果表明:将计算模型应用到拥挤驱动的RSMT布线灵活度挖掘算法,良好地改善了布线拥挤;将该挖掘算法应用到FastRoute4.1总体布线算法中,能够缩短14%的运行时间.

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

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

度约束欧氏Steiner最小树问题及其求解

在欧氏Steiner最小树的基础上,对每个正则点加上了度约束限制,提出了度约束欧氏Steiner最小树问题,分析了该问题的特性,给出了该问题的模拟退火和蚂蚁算法求解过程,并使用Delphi语言编程,在Windows XP平台上运行通过.通过大量算例的计算结果验证了该问题的实用性及算法的有效性.

基于最小Steiner树的关键词查询方法

在关系数据库中,关键词查询无需用户学习查询语言和数据库模式相关知识,而且有效地扩大了查询范围.采用元组图描述关系数据库中元组关系,可使关键词查询问题转化为元组图的最小Steiner树求解问题.本文提出元组图上基于相似度的边权重计算方法,使边权重能够反映元组与关键词相似度的大小.然后,鉴于最小Steiner树求解问题是NP-完全问题,提出按照贪心策略执行Dijkstra算法的最小Steiner树较优解求解算法.最后,通过实验对算法进行了分析和验证.

基于最小Steiner树的无线传感器网络数据融合算法

能源有效性是无线传感器网络(WSN)路由算法设计首要考虑的问题,可以通过数据融合合并冗余数据而有效地节约网络能耗。WSN数据融合可以看作是寻找覆盖源节点和Sink节点的最小Steiner树(MST)问题。文章提出了一种MAX-MIN蚂蚁系统算法和自适应蚁群系统算法相结合的MST构造算法(MMACS),在此基础上,提出了一种基于MST的WSN数据融合算法(DAMST),该算法采用定向扩散的机制进行兴趣散布;利用MMACS算法构造MST,源节点的数据发送到构造好的MST上,经过融合后传输到Sink节点,减少了网络中传输的数据量。通过与其它算法比较,仿真表明DAMST算法降低了网络总能耗和平均时延,延长了网络生存时间。

Steiner最小树问题的量子蚁群算法

Steiner最小树问题是组合优化中一个经典的NP难题,本文在蚁群算法的基础上结合量子计算提出一种求解欧氏Steiner最小树问题的量子蚁群算法.将量子比特、量子逻辑门以及Grover量子算法引入到蚁群算法中去,有效提高了算法的全局搜索能力,搜索速度也有显著的提高.一系列数据实例计算与比较表明,量子蚁群算法较蚁群算法在Steiner最小树问题的求解上具有更好的性能.

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

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

考虑障碍的多端点最小直角Steiner树构造算法

首先将所有障碍视为不存在 ,构造初始Steiner树、连接线网所有端点 ,可采用已有的无障碍Steiner树算法来实现 然后考虑障碍的影响 ,改造所构造的初始Steiner树 :找到初始Steiner树与障碍的相交点 ,重布某些树边 ,使它们绕过障碍 ,并尽量保持树长较短 ;进一步地 ,加入预处理和后期处理措施 ,以更好地处理特殊线网并使算法的结果更优 该算法能够处理多个障碍的情况 ,并能适应多种形状的障碍 ;同时 ,算法有较高的效率 ,其复杂度为O(mn) ,其中 ,m和n分别是障碍个数和线网端点数 该算法已经在SUN工作站、Unix上利用C语言编程实现 ,并进行了MCNC电路测试 测试结果表明 :文中算法得到的树长结果仅与最优值平均相差 5. 31% ,且算法的执行时间保持在

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

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

图的Steiner最小树问题的混合遗传算法

图的Steiner最小树问题是经典的组合优化问题,在通信网络和电路设计中有广泛应用。文中在遗传算法的基础上,对交叉率pc和变异率pm采用自适应过程,构造一种新的确定pc和pm的公式,有效解决了参数选取对最终结果的影响问题。再与模拟退火算法相结合,提出了一种解决Steiner最小树问题的混合遗传算法。该算法克服了遗传算法易早熟和收敛性能差的缺点,有效地增强了算法的进化能力。通过对OR-Library的部分实例进行计算结果表明,在大多数情况下混合遗传算法比遗传算法有更好的性能。

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

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

图的Steiner最小树问题的降阶回溯算法

图的Steiner最小树问题是经典的组合优化问题,是一个NP难题,在不同的领域有着广泛的应用。研究该问题的部分数学性质,在此基础上给出了该问题的初步降阶方法和下界子方法,形成一个新的回溯算法。该算法具有较低的时间复杂度,还给出了应用实例及其分析。

约束Steiner最小树问题

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

Steiner最小树问题及其应用

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

关于Steiner最小树问题

在本刊第二卷第二期上,我们曾发表了黄光明的《最短网络》一文,对Steiner最小树问题在当时的发展情况作了一些介绍。最近由于他与堵丁柱共同解决了Gilbert和Pallak在1968年所提出的一个猜想,不少读者对于这一问题产生了兴趣。为此,我们组写了这篇文章,目的在于使读者对这一问题的历史和连带产生的问题以及目前的发展状况有一较确切的和较全面的了解。

求解绝对值距离Steiner最小树的改进元胞蚂蚁算法

绝对值距离Steiner最小树问题是在集成电路布线等领域应用广泛的属于NP难的经典组合优化问题,由于该问题的搜索空间与元胞自动机的结构相似,设计了求解绝对值距离Steiner最小树问题的改进的元胞蚂蚁算法。经大量数据实验表明,该算法要比最小生成树平均改进15%,优于多数已有的基于最小生成树的近似算法,验证了算法的实用性。

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

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

遗传算法在最小Steiner树问题中的应用研究

简单介绍了最小生成树和最小Steiner生成树的概念，通过实例（有线通讯网络问题）提出了一种求解最小Steiner生成树问题的遗传算法。试验结果表明，该算法能够收敛到全局近似最优解。

遗传算法在最小steiner树问题中的应用

在对遗传算法、最小生成树和最小steiner生成树的概念作简单介绍之后,给出了一种改进后的求解最小steiner生成树问题的遗传算法。通过实例通信网络构建的仿真实验,说明改进后的算法能够更好地收敛到局部近似最优解,并分析了算法的优缺点。

约束Steiner最小树问题的近似解

本文首先给出约束Steiner最小树问题的一个近似解。然后讨论了当n=2或3时近似解的性能比，其中n=2时，文中所给的界为紧的。