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

摘要

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