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

An Efficient 2-Step Heuristics for Rectilinear Steiner Minimal Tree Construction among Obstacles

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

A primary tree is first constructed without considering obstacles. Intersections of the primary tree edges with obstacles are found out and relevant parts of the primary tree are reconnected to keep clear of obstacles while the total length of the tree being shortest. Moreover, a preprocessing and post-processing are added into the second step to tackle some special treatments and improve the solution quality. The heuristics can deal with multi-obstacle and obstacles of diversified shapes with O(mn) complexity, where m is the number of obstacles and n is the number of terminals. Experimental tests on MCNC benchmarks show that the algorithm can get good results on wire length, its average redundancy compared with minimal trees is 5.31% and the runtime for all cases is within 1 second.