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

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

节点加权的Steiner树问题的降阶回溯算法

节点加权的Steiner树问题是组合优化中一个经典的NP-hard问题,现有算法研究该问题时存在时间复杂性高或无法得到最优解的缺点。针对现有算法的不足,提出了一个基于降阶技术的回溯算法。首先研究该问题的数学性质,利用数学性质对该问题进行降阶以缩小问题的规模;接着提出上界子算法和下界子算法,利用上下界子算法对该问题的解空间树进行剪枝,提高搜索效率;最后利用上下界子算法和数学性质设计了一个回溯算法求解该问题。示例分析以及实验的结果表明,该算法不仅时间复杂性较低而且可以得到问题的最优解。     

图的steiner最小树问题及其求解

斯坦纳树问题是组合优化学科中的一个问题。属于NP-难问题,即无法在多项式时间内得到最优解。本文主要讨论了图的steiner最小树问题,并给出了近似算法,该算法是在破圈法的基础上进行了改进,并且引用了agent的思想。最后对算法进行了分析。     

物流网络中节点带权的Steiner最小树的参数算法

通过优化物流的运输网络,可以有效地降低物流成本。集中配送的物流网络优化问题可以转换成求解节点带权的Steiner最小树问题,这是一个NP-hard问题。运用参数理论,提出一种新的启发式解决算法P-NSMT。算法的思想是：首先尽可能只利用终端节点构造一棵连通的最小生成树,然后逐步向树中添加能减少生成树总权值的Steiner节点,最终生成一棵节点总数不超过参数k的Steiner最小树。实验表明,与同类型其他算法相比,P-NSMT算法具有更好的准确性和时间效率,特别适应于网络规模大、终端配送节点数目较少的物流网络。     

欧氏Steiner最小树问题的智能优化算法

欧氏平面内连接固定原点的最小树长问题，即欧氏Steiner最小树问题，为组合优化中的NP难题，因此合理的方法是寻找启发式算法。该文给出了两种智能优化算法——模拟退火法和蚂蚁算法。首先概述智能优化算法并将中面划分成网格，然后分别介绍两种算法的原理及实现过程，最后通过一系列计算实验，测试了算法的运行性能，获得了较好的效果。     

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

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

图的steiner最小树问题及其求解

斯坦纳树问题是组合优化学科中的一个问题。属于NP-难问题,即无法在多项式时间内得到最优解。本文主要讨论了图的steiner最小树问题,并给出了近似算法,该算法是在破圈法的基础上进行了改进,并且引用了agent的思想。最后对算法进行了分析。     

有约束竞争选址问题的降阶回溯算法

有约束竞争选址问题是组合优化中一个经典的NP-hard问题,现有算法研究该问题时或是无法求得最优解或是求解速度慢.针对现有算法的缺点,首先在这个经典问题的基础上进行修改,构建了一个新的数学模型;接着对该模型的数学性质进行研究,并在数学性质的基础上提出了上下界算法和降阶子算法对问题进行降阶,达到了缩减问题搜索解空间的目的,降阶的过程中既有单个的降阶,也有成批的降阶;然后在前面的基础上设计了一个回溯子算法来求解问题的最优解;最后通过两个示例分析更清楚地阐述该算法的原理,结果证明该算法可以较快求得最优解.     

矩形Steiner最小树布线灵活度

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

TST问题的降阶回溯算法

考虑Terminal Steiner Tree(TST)问题中特殊结点及其关联边之间的关系、结点之间的权值比较、可行解的连通性等几个方面,提出该问题的相关数学性质,判断问题中结点与边是否一定在或一定不在最优解中;利用上下界子算法对降阶回溯算法的解空间进行剪枝,加快了算法求解问题的速率,最后通过算法复杂度分析证明算法的有效性。     

Steiner Tree问题的研究进展

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

多参数最小支撑树问题的复杂性和算法

建立了多参数最小支撑树问题（ＲＭＳＴ）的模型,并证明该问题是ＮＰ－完全的。利用经典Ｇｒｅｅｄｙ算法,给出了该问题的一个近似算法,并分析了该近似算法的性能比,证明了所给出的界是紧的。     

Approximations for a Bottleneck Steiner Tree Problem

Abstract. In the design of wireless communication networks, due to a budget limit, suppose we could put totally n+k stations in the plane. However, n of them must be located at given points. Of course, one would like to have the distance between stations as small as possible. The problem is how to choose locations for other k stations to minimize the longest distance between stations. This problem is NP-hard. We show that if NP \neq P , no polynomial-time approximation for the problem in the rectilinear plane has a performance ratio less than 2 and no polynomial-time approximation for the problem in the Euclidean plane has a performance ratio less than \sqrt 2 and that there exists a polynomial-time approximation with performance ratio 2 for the problem in both the rectilinear plane and the Euclidean plane.     

求解多目标最小生成树问题的改进算法

多目标最小生成树问题是典型的NP问题,Zhou和Gen提出了一种用于计数多目标最小生成树问题的所有非劣最优最小生成树的算法,但该算法无法保证能够找到所有非劣最优最小生成树.针对此问题,提出一种改进的计数算法,并定性说明改进算法能够找到问题的所有非劣最优最小生成树.改进算法在进行子树剔除时增加了一些条件.模拟实验结果表明,改进后的计数算法能够找到所有的非劣最优解.这也说明该算法具有应用的潜力.