计算机辅助设计与图形学学报
計算機輔助設計與圖形學學報
계산궤보조설계여도형학학보
JOURNAL OF COMPUTER-AIDED DESIGN & COMPUTER GRAPHICS
2005年
2期
223-229
,共7页
杨旸%经彤%洪先龙%朱祺%王垠
楊旸%經彤%洪先龍%硃祺%王垠
양양%경동%홍선룡%주기%왕은
布线%最小直角Steiner树%障碍%多端点线网
佈線%最小直角Steiner樹%障礙%多耑點線網
포선%최소직각Steiner수%장애%다단점선망
首先将所有障碍视为不存在,构造初始Steiner树、连接线网所有端点,可采用已有的无障碍Steiner树算法来实现.然后考虑障碍的影响,改造所构造的初始Steiner树:找到初始Steiner树与障碍的相交点,重布某些树边,使它们绕过障碍,并尽量保持树长较短;进一步地,加入预处理和后期处理措施,以更好地处理特殊线网并使算法的结果更优.该算法能够处理多个障碍的情况,并能适应多种形状的障碍;同时,算法有较高的效率,其复杂度为O(mn),其中,m和n分别是障碍个数和线网端点数.该算法已经在SUN工作站、Unix上利用C语言编程实现,并进行了MCNC电路测试.测试结果表明:文中算法得到的树长结果仅与最优值平均相差5.31%,且算法的执行时间保持在1s以内.
首先將所有障礙視為不存在,構造初始Steiner樹、連接線網所有耑點,可採用已有的無障礙Steiner樹算法來實現.然後攷慮障礙的影響,改造所構造的初始Steiner樹:找到初始Steiner樹與障礙的相交點,重佈某些樹邊,使它們繞過障礙,併儘量保持樹長較短;進一步地,加入預處理和後期處理措施,以更好地處理特殊線網併使算法的結果更優.該算法能夠處理多箇障礙的情況,併能適應多種形狀的障礙;同時,算法有較高的效率,其複雜度為O(mn),其中,m和n分彆是障礙箇數和線網耑點數.該算法已經在SUN工作站、Unix上利用C語言編程實現,併進行瞭MCNC電路測試.測試結果錶明:文中算法得到的樹長結果僅與最優值平均相差5.31%,且算法的執行時間保持在1s以內.
수선장소유장애시위불존재,구조초시Steiner수、련접선망소유단점,가채용이유적무장애Steiner수산법래실현.연후고필장애적영향,개조소구조적초시Steiner수:조도초시Steiner수여장애적상교점,중포모사수변,사타문요과장애,병진량보지수장교단;진일보지,가입예처리화후기처리조시,이경호지처리특수선망병사산법적결과경우.해산법능구처리다개장애적정황,병능괄응다충형상적장애;동시,산법유교고적효솔,기복잡도위O(mn),기중,m화n분별시장애개수화선망단점수.해산법이경재SUN공작참、Unix상이용C어언편정실현,병진행료MCNC전로측시.측시결과표명:문중산법득도적수장결과부여최우치평균상차5.31%,차산법적집행시간보지재1s이내.
