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

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

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

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

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

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

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

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

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

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

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

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

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

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

模糊最小树分析

连通无向网络中各条边的权值在实际问题中往往都不能用一个确切的权值表示,通常具有模糊性.把模糊数学的理论和方法引入连通无向网络来求最小树,并运用模糊数学的方法来表征网络的边长,提出了模糊最小树概念,建立了模糊环境下合适的无向连通网络最小树的数学模型,然后用模糊最佳树算法对模型进行了分析.最后以城市架设通信网络为应用实例给出了该方法在实例应用中具体的解决方案和决策手段.实验数据表明该方法是有效的.     

X结构下VLSI多层绕障Steiner最小树算法

Steiner最小树作为VLSI布线的基础模型,应进一步考虑到X结构、障碍物、多层等条件,文中基于粒子群优化提出了多层绕障X结构Steiner最小树算法.首先引入边变换操作以改变布线树的拓扑,使其具有较强的绕障能力;为了避免边变换操作带来的布线树环路问题,结合并查集策略设计新的操作算子;为了保证布线边不违反约束,提出一个与绕障情况及通孔数相关的惩罚函数策略,从而优化了多层布线中布线总代价这一最重要的目标.实验结果表明,相对于同类算法,该算法在布线总代价的优化能力上是最强的.     

ACO-Steiner: Ant Colony Optimization Based Rectilinear Steiner Minimal Tree Algorithm

The rectilinear Steiner minimal tree （RSMT） problem is one of the fundamental problems in physical design, especially in routing, which is known to be NP-complete. This paper presents an algorithm, called ACO-Steiner, for RSMT construction based on ant colony optimization （ACO）. An RSMT is constructed with ants＇ movements in Hanan grid, and then the constraint of Hanan grid is broken to accelerate ants＇ movements to improve the performance of the algorithm. This algorithm has been implemented on a Sun workstation with Unix operating system and the results have been compared with the fastest exact RSMT algorithm, GeoSteiner 3.1 and a recent heuristic using batched greedy triple construction （BGTC）. Experimental results show that ACO-Steiner can get a short running time and keep the high performance. Furthermore, it is Mso found that the ACO-Steiner can be easily extended to be used to some other problems, such as rectilinear Steiner minimal tree avoiding obstacles, and congestion reduction in global routing.     

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

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

G-Tree:基于引力指向技术减少拐弯的Steiner树算法

提出一种基于引力指向技术、以减少拐弯数为目标的最小直角Steiner树构造算法G-Tree.利用一个节点受到其他节点的引力来决定它的移动方向,并采用引力加权以考虑减少拐弯数,生成Steiner树后对拐弯数进行了进一步优化.减少拐弯数有助于在布线阶段减少可能的通孔,从而增强电路的可靠性和可制造性.实验结果表明,G-Tree算法在减少布线树的拐弯数方面有明显的效果.     

Improved computation of plane Steiner Minimal Trees

ASteiner Minimal Tree (SMT) for a given setA = {a ₁,...,a _n } in the plane is a tree which interconnects these points and whose total length, i.e., the sum of lengths of the branches, is minimum. To achieve the minimum, the tree may contain other points (Steiner points) besidesa ₁,...,a _n . Various improvements are presented to an earlier computer program of the authors for plane SMTs. These changes have radically reduced machine times. The existing program was limited in application to aboutn = 30, while the innovations have facilitated solution of many randomly generated 100-point problems in reasonable processing times.This work was supported by the Canadian Natural Sciences and Engineering Council under Grant Numbers A-7544 and A-7558.     

基于非hanan点的时延约束最小斯坦那树生成方法

介绍了一个基于非hanan点的时延约束最小斯坦那树生成方法,该方法引入非hanan点的概念,可以得到长度费用优化较好的布线树.     

Manhattan空间有障碍的最短路径和3-Steiner树算法

在VLSI设计中,多点互连是物理设计阶段的关键问题之一,而互连的点数等于2或大于2分别对应于Manhattan空间上有障碍时的最短路径问题和最小Steiner树问题,显然前者是后者的基础.连接图是研究最短路径问题的有效工具,已有的典型连接图包括基于轨迹的GC和GT以及基于自由区的GF和GG.工作包括3个方面:设计并分析了在各种连接图上实现动态的点对之间的最短路径查询算法;分析了在各个连接图上构造3-Steiner树的算法,对于已有的GC上的3-Steiner算法,将其Steiner顶点的候选集合规模从O((e+p)2)降低到了O((t+p)2),其中e,t,p分别表示边数、障碍极边数和顶点数;设计了在GG上的3-Steiner树构造算法,其平均情况时间复杂度只有(θ)(t).     

基于MPH的时延约束Steiner树算法

为了在时延约束条件下进一步优化组播树代价,并降低算法计算复杂度,研究了时延受限的Steiner树问题.分析了MPH(minimum path heuristic)算法的计算复杂度;在此基础上设计了一个时延约束Steiner树算法DCMPH(delay constrained MPH)用于构造时延约束最小代价组播树.该算法中每个目的结点通过与当前组播树有最小代价的路径加入组播树;若时延不满足要求,则通过合并最小时延SPT(shortest path tree)树进而产生一个满足时延约束的最小代价组播树.仿真实验表明,DCMPH算法生成的组播树在保证时延要求的情况下,与同类算法相比取得了很好的代价性能和较低的计算复杂度.     

Steiner minimal trees for a class of zigzag lines

Sets of points for which the Steiner minimal tree is known, are available only for some very special cases. This paper describes the Steiner minimal tree for a set of points forming the vertices of special zigzag lines.